Tu aurais pu la poster dans une heure ou deux, que je prenne le temps de bosser un peu sur ma thèse entre-deux

Bon, par pur manque d'autodiscipline, j'entame cette énigme.

Résultat essentiel : avec [latex]P(E)[/latex] l'ensemble des parties de [latex]E[/latex], c'est-à-dire l'ensemble de tous les sous-ensembles de [latex]E[/latex], on a [latex]Card (P(E)) = 2^n[/latex] (facile à prouver).

En entrant plus dans le détail : comme il y a [latex]\binom{n}{k}[/latex] façons de choisir [latex]k[/latex] éléments parmi [latex]n[/latex], il y a autant de sous-ensembles différents et de cardinal [latex]k[/latex] d'un ensemble de cardinal [latex]n[/latex]. En sommant sur [latex]k[/latex], on obtient le [latex]2^n[/latex] ci-dessus.

Voici donc tous les ensembles [latex]B[/latex] que l'on peut choisir, et pour un ensemble [latex]B[/latex] de cardinal [latex]k[/latex], on peut créer [latex]2^k[/latex] sous-ensembles [latex]A[/latex] de [latex]B[/latex]. Et voici la belle formule qui débarque, et qui donne le nombre [latex]C_n[/latex] de couples d'ensemble [latex](A,B)[/latex] respectant l'énoncé que l'on peut créer en fonction de [latex]n[/latex] :
[TeX]C_n = \sum_{k=0}^n \binom{n}{k} 2^k[/TeX]
Euh... Peut-on calculer ça d'une façon pas trop moche ? Ouais, avec Wolfram|Alpha

Pour n=10, je tape :

sum binomial[10,k]*2^k, k=0 to 10

Et il me répond 59049, qui est validé par la case réponse

Là aussi, il y a de la bonne explosion de valeurs dans l'air :

5     -> 243
10    -> 59049
15    -> 14348907
20    -> 3486784401
25    -> 847288609443
30    -> 205891132094649

On commence par fixer un ensemble B de X éléments
Combien y a t'il de sous-ensembles de B ayant Y éléments ?
C'est par définition le nombre d'arrangement C(X,Y), qui vaut X! / [(X-Y)! Y!]

Donc, combien y a t'il de sous-ensembles de B à X éléments, toutes tailles confondues ?
C'est la somme pour Y allant de 0 à X des C(X,Y), qui vaut 2^X (chose qu'on démontre aisément en déroulant le binôme de Newton de (1+1)^X)

Chaque ensemble B de X éléments peut être couplé à 2^X sous ensembles, mais combien y-a-t'il d'ensembles B de X éléments ?
Pareil, c'est le nombre d'arrangement C(N,X), qui vaut N! / [(N-X)! X!]

=> Le nombre de couples (A,B) pour un ensemble B à X éléments est
2^X * N! / [(N-X)! X!]

=> Le nombre de couples (A,B) pour toutes les tailles de B est donc défini par la formule suivante:
[TeX]\sum_{X=0}^N{\frac{2^XN!}{(N-X)! X!}}[/TeX]
Oh, stupeur, encore un binôme de Newton !!
[TeX]\sum_{X=0}^N{\frac{2^XN!}{(N-X)! X!}}=\\
\sum_{X=0}^NC_n^X 2^X 1^{(N-X)}=\\
(2+1)^N = 3^N
[/TeX]
Pour un ensemble E à n éléments, on a donc 3^n paires différentes d'ensembles (A,B) telles que E contient B qui contient A
(Pour n=10, la réponse est 59.049)

Joli exercice et jolie formule. Je n'ose dire simple mais élégant.

Un ensemble de n éléments à [latex]2^n[/latex] sous-ensembles.

Un ensemble à n éléments a [latex]C_n^k[/latex] sous-ensembles à k éléments. Or chacun de ces sous-ensembles a lui-même [latex]2^k[/latex] sous-ensembles.

Il y a donc au total [latex]\sum_{k=0}^nC_n^k2^k[/latex] couples de la forme que l'on recherche.

Or cette expression est justement le développement du binome pour [latex](2+1)^n[/latex]. Il y en a donc [latex]3^n[/latex] .

Pour n=10, cela donne 59049, ce qui est validé par la case réponse.

Merci.

De plus à vu de nez, j'ai l'impression que ça se généralise très bien...

pour chaque ensemble de cardinal [latex]n[/latex], il y a [latex]2^n[/latex] parties, ou sous ensembles. Et en particulier, il y a [latex]C_n^i=\frac{n!}{i! (n-i)!}[/latex] parties de cardinal [latex]i[/latex]

Donc pour chaque B de cardinal [latex]i[/latex] dans E (de cardinal [latex]n[/latex]), il y a encore [latex]2^i[/latex] A differents dedans, d'ou la formule
[TeX]\sum_{i=0}^n C_n^i 2^i=\sum_{i=0}^n C_n^i 2^i 1^{n-i} = 3^n[/TeX]
pour 10 cela donne 59049.

Une autre facon plus elegante de voir le probleme est de dire que prendre un couple (A,B), c'est, pour chaque element de E, choisir s'il est :
-dans A et B
-dans A
-dans aucun des deux
d'ou directement la reponse [latex]3^n[/latex]

Bravo a tous ceux qui ont déjà trouvé.
Bravo supplémentaire à rivas pour avoir flairé la généralisation et grand bravo a Scarta pour l'avoir démontré. Et de deux manière s'il vous plait !!

Donc exercice supplémentaire :

Soit m un entier, combien y a-t-il de m-uplets (A1, A2, ...,Am) de parties de E tels que A1 c A2 c ... c Am

Pour la question bonus, je dirais [latex](m+1)^n[/latex].

Désolé, je suis plutôt très mauvais en LaTeX, aussi, j'ai préféré faire une image. En même temps ça limitera l'accès serveur (même si ça augmente de 2.65 Ko l'espace serveur utilisé)

Pour la question 1, avec :
- E ensemble de taille n
- B sous-ensemble de E de taille i
- A sous-ensemble de B de taille k

Je pense que le nombre de couples d'ensembles (A, B) est :

(Si quelqu'un veut me donner la formule LaTeX, ça serait avec plaisir )


Pour la question 2, je pense qu'en imbriquant selon la formule précédente, on peut trouver la réponse.

EDIT 20:06 :
Tiens c'est rigolo, en cherchant la réponse pour n=10 (qui est 59049) avec un célèbre tableur, et afin de me confirmer dans ma réponse, je m'aperçois qu'il est question de la somme des termes de la n-ième ligne du triangle de Pascal multipliés par des puissances de 2. C'est quand même génial les mathématiques
Je vais tâcher de généraliser avec ces découvertes, mais je ne promets rien.

Bravo a tous.

La réponse est bien (k+1)^n  soit 3^n  dans le cas particulier de la question 1
Beaucoup de démo qui utilisent le binôme de Newton (la manière que j'ai utilisée aussi)
La démo de Vasimolo et de McFlambi est une révélation
Bravo et merci a vous deux

srx c'est de quels niveaux vos énigmes... T-T

C'est possible de mettre le niveau entre crochets ? Parce que bon celle-là pas question que je l'aborde, mais d'autres je ne sais jamais pas trop ^^ Bref j'ai l'impression qu'ici on ne poste pas bcp d'énigmes abordables :S

Merci MthS pour la formule LaTeX (et merci également à McFlambi qui est passé par MP)