Nombre de sous-ensembles
Bonjour,
par curiosité je me suis posé la question suivante : étant donné l'ensemble $E=\{2,3,\ldots,N\}$, on cherche des sous-ensembles $S=\{a_1,a_2,\ldots,a_k\}$ de $E$ formés uniquement d'éléments deux à deux premiers entre eux, i.e., pgcd$(a_i,a_j)=1$ pour $i\neq j$. Par exemple en prenant que des nombres premiers pour les $a_i$ on a une réponse. En cherchant sur internet, il me semble que c'est un problème difficile pour dénombrer tous ces sous-ensembles $S$. J'ai trouvé un article de Calkin et Granville (pièce jointe) qui ont complétement résolu la question. Je n'ai pas compris leur résultat, je ne suis pas spécialiste en Combinatoire. Est-ce-que quelqu'un peut me dire par exemple avec $N=2019$ et $k=15$ quel est le nombre des sous-ensembles $S$. Merci.
Cordialement.
par curiosité je me suis posé la question suivante : étant donné l'ensemble $E=\{2,3,\ldots,N\}$, on cherche des sous-ensembles $S=\{a_1,a_2,\ldots,a_k\}$ de $E$ formés uniquement d'éléments deux à deux premiers entre eux, i.e., pgcd$(a_i,a_j)=1$ pour $i\neq j$. Par exemple en prenant que des nombres premiers pour les $a_i$ on a une réponse. En cherchant sur internet, il me semble que c'est un problème difficile pour dénombrer tous ces sous-ensembles $S$. J'ai trouvé un article de Calkin et Granville (pièce jointe) qui ont complétement résolu la question. Je n'ai pas compris leur résultat, je ne suis pas spécialiste en Combinatoire. Est-ce-que quelqu'un peut me dire par exemple avec $N=2019$ et $k=15$ quel est le nombre des sous-ensembles $S$. Merci.
Cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Cordialement,
Yan2