Nombre de couples

En appelant $u_n$ le nombre que tu cherches, on a $u_{n+1} = u_n + u_n + u_n$ me semble-t-il

À tout couple $(X,Y)$ de parties de $E$ telles que $X\subset Y\subset E$, on associe l'application $f$ de $E$ dans $\{0,1,2\}$ définie par :
$f(x)=0$ si $x\in X$, $f(x)=1$ si $x\in Y\backslash X$ et $f(x)=2$ si $x\in E\backslash Y$.
On définit ainsi une bijection de l'ensemble de ces couples sur l'ensemble des applications $f$ de $E$ dans $\{0,1,2\}$, lesquelles sont au nombre de $3^n$.:

Et mettre un "s" à couples SVP.

Pour la même raison, c'est aussi le cardinal de l'ensemble des couples $(X,Y)$ de parties disjointes.
Tout cela se généralise à des $p$-uplets d'ensembles.

P. tu m'as devancé (:P)

J'en profite pour proposer la généralisation immédiate, avec la même méthode, par récurrence, pour compter le nombre de $p$-uplets $X_1$, $\dots$, $X_p$ tel que $X_1\subset \cdots \subset X_p\subset X$.

Par récurrence, on va montrer que c'est $(1+p)^n$.

Pour $n=1$ c'est clair, il y a $2^n$ parties de $X$ donc autant de $1$-uplets inclus dans $X$ (si on est pas convaincu, réécrire $\sum_{i=1}^n\binom{n}{i}=2^n$) .

Supposons la propriété vraie au rang $p$ ; de la même façon que propose P., pour $|X_1|=k$, on applique la propriété de récurrence, et on trouve qu'il y a $(1+p)^k$ $p$-uplets inclus les un dans les autres possibles dans $X_1$ ; il y a $\binom{n}{k}$ façon de choisir $|X_1|=k$, soit en tout
\[\sum_{k=1}^n\binom{n}{k}(1+p)^k=(1+(p+1))^n\]
$p+1$-uplets de ce type ...

Sans vouloir rentrer dans un conflit méthodologique, je trouve pas vraiment que c'est plus simple ... bien au contraire!
De même que l'argument utilisé quand $p=2$, cela va "vite" (et encore) car les étapes intermédiaires (certes d'un niveau relativement facile, mais tout de même) sont omises :
"Un tel couple $X\subset Y$ revient à se donner" un étiquetage etc... : il faut montrer que c'est bien bijectif, ce qui est un peu fastidieux si on le fait vraiment...
Pour se ramener à compter le nombre de fonction de $E$ dans $\{0,1,2 \}$ (ce que tu omet aussi de dire), et qu'il faut finalement compter, et que l'on ne compte pas.
Sans compter que c'est fort peu visuel...

Pour le cas $p$, le temps de prouver que cette fonction est bien une bijection entre les $p$-uplets que l'on cherche et l'ensemble des fonction de $E$ dans $\{0,\dots,p \}$, on a fini le petit raisonnement combinatoire depuis belle lurette...

Après chacun son goût, et c'est toujours bien d'avoir plusieurs méthodes, mais je crois qu'un "bof" n'était pas vraiment légitime, d'autant plus que c'est justement les méthodes proposées pour $p=2$ qui m'ont poussées à chercher une solution plus naturelle...

Niazov, tu me sembles d'une mauvaise foi caractérisée.

La bijection ? J'en ai donné explicitement un sens dans mon message. L'autre, je ne l'ai pas donné tant il me semblait évident : $X_i=\{x\in X\mid f(x) < i\}$.
Compter le nombre de fonctions d'un ensemble à $n$ éléments dans un ensemble à $p+1$ éléments ? Tu te fiches de moi ?

Plus sérieusement : à partir du moment où le résultat s'exprime sous la forme $(p+1)^n$, il me semble que le dénombrement le plus lumineux consiste à mettre en évidence des fonctions d'un ensemble à $n$ éléments (ça tombe bien, on en a un sous la main) dans un ensemble à $p+1$ éléments.

Jacquot, bonne année !
Que penses-tu de mon argument esthétique : à partir du moment où le résultat d'un dénombrement est $q^n$, il est joli de faire apparaître des fonctions d'un ensemble à $n$ éléments dans un ensemble à $q$ éléments ?
On peut appliquer ce principe esthétique aux nombres de Catalan $\dfrac1{n+1}\displaystyle \binom{2n}{n}$ : comment traduire le dénombrement des parenthésages corrects en $n$ paires de parenthèses en un choix de $n$ parmi $2n$ acompagné d'un principe du berger pour des moutons à $n+1$ pattes ?

Ensuite, en parlant de mauvaise foi, sais-tu comment on montre proprement qu'une fonction est bijective ?
C'est en tout cas pas en balançant un prétendu inverse (qui te "semblais évident" ; si t'as des élèves, je les plains ...) ; il faut vérifier que c'est bien un inverse qui arrive dans le bon ensemble etc... à savoir prendre la peine de montrer que les $X_i$ possèdent la propriété d'emboîtement cherché (ça doit être "évident" aussi... à ce compte là on peut dire que $p^n$ est évident, la démo pouvant être faite de tête ...) ; que c'est injective/surjectif (évident, vous dis-je)...
Enfin, en quoi cette fonction $f$, qui à grand renfort de détails est bien à présent bijective, en quoi cela garanti que l'on obtient toutes les fonctions de $X$ dans $\{1,\dots, p\}$ ?
Bref, un raisonnement "lumineux", où il faut se convaincre à chaque étape que ça l'est ..
Ce qui me semble plus douteux, c'est en quoi cette fonction est naturelle? C'est un outil technique qui enlève toute la géométrie du problème initiale.. Trouver cela élégant, c'est une question de goût ... qui n'est pas le mien... désolé de pas être de ton avis...
Et le nombre de fonctions de $E$ dans $F$ : tout le monde sait de tête que c'est $|F|^{|E|}$? Personne dans sa scolarité n'a douté du sens de la puissance ? Si oui, ne faut-il pas refaire un petit argument combinatoire pour s'en assurer?
Et j'arrive au point clé : on a donc transposé ce problème dans le monde des fonctions (qui est, à mon sens une sophistication inutile, mais encore une fois, pourquoi pas, soyons ouvert d'esprit, contrairement à certains) pour en arriver à un problème de dénombrement desdites fonctions... au lieu de s'occuper de dénombrer directement, de manière constructive... je trouve cela très élégant en effet.

Enfin, un point intéressant complémentaire : "à partir du moment où le résultat d'un dénombrement est $q^n$, il est joli de faire apparaître des fonctions d'un ensemble à $n$ éléments dans un ensemble à $q$ éléments ?"
On n'en sait justement rien a priori que c'est $q^n$ ... Ce qu'une méthode plus constructive (comme celle de P., par exemple) permet de trouver sans idée a priori (la récurrence est en effet un simple "artifice" de présentation, l'itération apparaît naturellement dans la démonstration, qui est déjà en fait complète dans le cas $p=2$).

Voilà pour mon opinion. Je ne critique pas les autres méthodes, et sans doute chacun y trouvera un argument pour s'y plaire, mais en tout cas je m'abstiendrais de dire "bof" à une d'entre elles, je peux juste expliquer pourquoi celle de P. me semble peut-être plus naturelle...

Si il y a bien une mauvaise foi, c'est de la part de celui qui rédige à moitié sa solution et qui s'émerveille tout seul de sa "beauté".

Remarque hors-sujet*: $a^b$ est par définition l'unique cardinal $c$ tel que pour tout $X,Y: (card(X),card(Y))=(a,b)$ implique $card(X^Y) = c$ où $X^Y$ est l'ensemble des applications de $Y$ dans $X$.

* je dis ça pour les visiteurs de toute époque sur le fil (même quand on n'y pensera plus).

Pour un déroulé*** tapé rapidement mais, je pense sans trop d'erreurs de frappe voir http://www.les-mathematiques.net/phorum/read.php?16,1188969,1189085#msg-1189085

*** des définitions de toutes les maths (le début) à partir de "rien" (ie des axiomes)

@niazov, il n'y a pas de manière objective de hiérarchiser des raisonnements selon un critère d'esthétisme. Par contre, il n'est pas inutile de reconnaitre que FChaurien et GBMZ ont proposé une approche plus généralisable avec leur présentation: l'ensemble des $f\in (2^E)^F$ tels que $\forall x\in E: [i\in F\mapsto f(i)(x)]\in T$ est en bijection (évidente**) avec l'ensemble des $g\in (2^F)^E$ tels que $\forall x\in E: g(x)\in T$ et a donc comme cardinal $|T|^{|E|}$ (quand $T\subset 2^F$)

$$^{**}[x\mapsto (y\mapsto f(x)(y))] \mapsto [y\mapsto (x\mapsto f(x)(y))]$$

Niazov excuse-moi, au vu de ta réponse je doute finalement qu'il s'agisse de mauvaise foi.

@GaBuZoMeu : et au vu de la tienne, on s'oriente encore un peu plus sur la piste du snobisme ...

@niazov: je vais lire tes deux posts en détail et te répondre. Je n'ai pas compris ton surenchérissement (ton dernier post) inutile, puisque GBMZ te fait des excuses et te déclare de bonne foi.

@niazov

Bon, j'ai dû me taper la lecture de tous les posts car dans tes posts, tu te référais à d'autres posts, etc. Je te propose une réponse détaillée qui je l'espère répondra à tes interrogations sans être sujective.

1) D'abord rappelons que sur un forum où les gens viennent se détendre, ils ne postent pas forcément des preuves in extenso sans sauter d'étape. Tu mets en procès cette manifestation mais pourtant elle n'a rien de bien grave, ni de significative.

2) Sont en concurrence essentiellement (j'exclus la mienne, au 1er post, non détaillée) deux démarches, toutes mal écrites (disons résumées et trouvées "à la seconde" donc pas rédigée).

2.1) La première démarche est celle, introduite par P, continuée par toi, qui consiste à s'appuyer sur le binôme de Newton et à faire des récurrences.

2.2) La deuxième (par FChaurien et GBMZ) a consisté à identifier quel ensemble $E^F$ on dénombre, mais sans le dire de manière explicite, puisqu'ils ont tous deux directement "ressenti" comment coder l'ensemble d'arrivée.

3) Tu t'es engouffré dans la brèche légère des présentations de (2.2) en livrant plusieurs arguments, hélas peu robustes, car ils disparaitraient vite au vu d'une rédaction travaillée du coeur de ce qu'elle cherche à dire.

4) Tu ne peux pas défendre un résultat de la forme A=>B où A est la conjonction du binôme de Newton et de l'axiome de récurrence comme si tu défendais uniquement B. Tu t'es en effet référé à la problématique "pédagogique" pour cirtiquer 2.2, mais tu as omis de souligner avec autant de motivation les obstacles à l'évidence que constitue l'utilisation d'industrie technique pour aboutir ... au même résultat.

5) Tu commets une erreur: $card(A^B)=card(A)^{card(B)}$ est une définition (moyennant une preuve d'autre chose), il n'y a strictement rien à comprendre (à part que le cardinal de $A^B$ ne dépend que du couple $(card(A),card(B))$ )

Je continue au post suivant :-D (car je ne veux pas taper un post long pour rien si le fil est fermé avant que je livre la suite)

On ne fait jamais assez de publicité sur le fait que l'application de $\mathcal{P}(E)$ dans $\{0,1\}^E$ qui à $A$ associe son indicatrice est une bijection.

Une fois qu'on a intégré ça, on cherche $1_X$ et $1_Y$ tels que $1_X\le 1_Y$ et comprend vite qu'il faut et qu'il suffit que $(1_X,1_Y)$ ne prenne que les valeurs $(0,0)$, $(0,1)$ ou $(1,1)$.

Je paraphrase sans doute des choses déjà dites, mais au cas où...

9) Alors attention: je ne veux pas être tout critique, car tu mérites que soit reconnu ce que vous avez posté P et toi. Vos contributions sont autant de preuves d'égalités reliant le binôme de Newton à des expressions de la forme $x^y$.

Déjà, si $\left| E\right| =n$, le nombre de triplets $(A,B,C)$ de parties de $E$ telles que $A\subset B\cup C$ est $7^n$, si je ne me trompe. Ensuite faut voir.

L'inclusion-exclusion donne $3\times 7^n-3\times 6^n+5^n$.

snif, je suis vraiment bébéte...:-X:-X Je prends un exemple qui ne tombe pas dans le champ de ce que je voulais illustrer (piégé par le français!!!).

J'aurais dû demander $card(\{(A,B,C)\in P(E)^3 \mid A\subset (B\cup C)\}$ par exemple

Retour sur le problème posé.
..................................................................................................................................................................................
Quel est le nombre de triplets $(A,B,C)$ de parties d'un ensemble $E$ de cardinal $n$, telles que l'une de ces parties soit incluse dans la réunion des deux autres ? (Ce qui signifie : $A\subset B\cup C$ ou $B\subset C\cup A$ ou $ C\subset A\cup B$).
..................................................................................................................................................................................

Je note $\overline{X}$ le complémentaire dans $E$ d'une partie $X$ de $E$. Un triplet $(A,B,C) $ de parties de $E$ définit une pseudo-partition de $E$ en 8 pseudo-classes (je dis "pseudo" parce que ces parties peuvent être vides). Ces pseudo-classes sont : $A\cap B\cap C$, $ A\cap B\cap \overline{C}$, $A\cap \overline{B}\cap C$, $A\cap \overline{B}\cap \overline{C}$, ... et ainsi de suite jusqu'à $\overline{A}\cap \overline{B}\cap \overline{C}$. On peut les représenter sur un arbre. On peut aussi dessiner le diagramme d'Euler-Venn de ces trois ensembles $A$, $B$, $C$ dans $E$, on verra que $E$ est ainsi partagé en 8 zones correspondant à ces 8 pseudo-classes.

Numérotons ces pseudo-classes de 1 à 8. Un triplet $(A,B,C)$ de parties de $E$ est caractérisé par l'appartenance de chaque $x \in E$ à telle ou telle de ces pseudo-classes, autrement dit par une application de $E$ dans l'ensemble $\{1,2,...,8\}$. Le nombre de triplets $(A,B,C)$ de parties de $E$ est donc le nombre de ces applications, c'est $8^n$.
Vous me direz c'est évident, attendu que ce nombre est bien sûr : $\left| \mathfrak {P} (E)\times \mathfrak {P} (E)\times \mathfrak {P} (E)\right| =\left| \mathfrak {P} (E)\right| ^{3}=(2^{n})^{3}$.
Mais ça montre la pertinence de l'approche proposée.

Cherchons maintenant le nombre des triplets $(A,B,C)$ de parties de $E$ telles que : $A\subset B\cup C$. Alors il faut supprimer la pseudo-classe $A\cap \overline{B}\cap \overline{C}$. Le nombre de ces triplets est donc le nombre d'applications de $E$ dans un ensemble à 7 éléments, c'est $7^n$.

Même raisonnement pour le nombre des triplets $(A,B,C)$ de parties de $E$ telles que : $A\subset B\cup C$ et $B\subset C\cup A$. Il faut supprimer les pseudo-classes $A\cap \overline{B}\cap \overline{C}$ et $\overline{A}\cap B\cap \overline{C}$. Le nombre de ces triplets est donc le nombre d'applications de $E$ dans un ensemble à 6 éléments, c'est $6^n$.

Encore de même pour le nombre des triplets $(A,B,C)$ de parties de $E$ telles que : $A\subset B\cup C$ et $B\subset C\cup A$ et $C\subset A\cup B$. Il faut supprimer les pseudo-classes $A\cap \overline{B}\cap \overline{C}$ et $\overline{A}\cap B\cap \overline{C}$ et $\overline{A}\cap \overline{B}\cap C$. Le nombre de ces triplets est donc le nombre d'applications de $E$ dans un ensemble à 5 éléments, c'est $5^n$.

Comme dit GaBuZoMeu, on termine par le principe d'inclusion-exclusion (formule du crible) qui dit que si $X$, $Y$, $Z$ sont des ensembles finis, alors : $\left| X\cup Y\cup Z\right| =\left| X\right| +\left| Y\right| +\left| Z\right| -\left| X\cap Y\right| -\left| Y\cap Z\right| -\left| Z\cap X\right| +\left| X\cap Y\cap Z\right| $.
Ce qui conduit au résultat : $3\cdot 7^{n}-3\cdot 6^{n}+5^{n}$

Bonne journée.
F. Ch.

J'en profite pour connecter ce que j'ai répondu à niazov avec l'exercice que j'ai par erreur pas donné (beaucoup plus simple que celui résolu ci-dessus par FC que j'ai par erreur donné):

$card(\{(A,B,C)\in P(E)^3 \mid A\subset (B\cup C) \}) = $

$card(\{f\in (2^E) ^3 \mid \forall x\in E: f(0)(x)\leq max(f(1)(x),f(2)(x)) \}) = $

$card(\{g\in (2^3) ^E \mid \forall x\in E: g(x)(0)\leq max(g (x)(1),g(x)(2)) \}) = $

$card(\{g\in (2^3) ^E \mid \forall x\in E: g(x) \in D \}) = $

$card( D ) ^{card(E)} = 7^{card(E)}$

car $card( D ) =7$

Abréviation: $D:= \{w\in 2^3 \mid w(0)\leq max(w(1),w(2)) \}$

Rappel: $3=\{0;1;2\}$

Oui, « bien sûr ». Voici le code (le fichier était encore dans la poubelle...). Total bricolage.

\begin{tikzpicture}[x=.75cm]
\foreach \i in {1,2,3,4} {
  \draw[very thick,rounded corners=3pt] ({-\i*.2},{-\i*.15}) rectangle ({\i*2},{1+\i*.15});
}
\foreach \i in {1,2,3} {
  \draw ({(\i-1)*2+.65},{-\i*.15})--({(\i-1)*1.5+.65},{-1.}) node[below] {$X_\i$};
}
\draw ({(4-1)*2+.65},{-4*.15})--({(4-1)*1.5+.65},{-1.}) node[below] {$X$};
 \draw[blue] (1,.5) node {$Y_1$};
\foreach \i in {2,3,4} {
  \draw[blue,thick,rounded corners=3pt] ({(\i-1)*2+.2},{-(\i-1)*.15}) rectangle ({(\i-1)*2+1.8},{1+(\i-1)*.15});
  \draw[blue] ({(\i-1)*2+1},.5) node {$Y_\i$};
}
\end{tikzpicture}

Bonjour Educ,
Voici comment j'ai compris le dénombrement de P. :
Si $X\subset Y\subset E $, alors $X $ est une partie de $Y $ et on sait que le nombre de parties d'un ensemble de cardinal $k $ est $2^k $ .
D'autre part, il y a $C_n^k =\binom n k $ façons de choisir $k $ éléments parmi $n $.

Si l'on impose $card(Y)=k $, il y a donc $\C_n^k \times 2^k $ façons de réaliser la double inclusion $X\subset Y\subset E $
Mais le cardinal de $Y $ peut prendre toutes les valeurs entières comprises entre $0$ et $n $, donc le nombre total de manières de réaliser la double inclusion est $\displaystyle \sum_{k=0}^n C_n^k 2^k$ et là, on peut reconnaître le développement de $(2+1)^n$ selon la formule du binôme de Newton.