Inscription / Connexion Nouveau Sujet
Dénombrements
Soit E un ensemble à n éléments
Partie A : partitions de E ne contenant que des paires ; on note a_p le nombre de partitions de E en p paires.
On suppose p 
2. Montrer que a_p = (2p - 1) a_(p-1)
En déduire a_p en fonction de p.
Partie B : nombre de partitions de E = {x_1, x_2, ..., x_n} ne contenant que des singletons ou des paires
On suppose n 3. En distinguant les partitions où x_n appartient à un singleton et celles où il appartient à une paire, montrer que : b_n = b_(n-1) + (n - 1) b_(n-2)
On suppose n pair et on pose n = 2p
Montrer que b_2p = 
(de i=0 à p) (2i parmi 2p) a_(p-i) ; on pourra dénombrer les partitions en fonction du nombre de leurs singletons.
On suppose n impair : n = 2p + 1 (p entier naturel).
Etablir une formule analogue donnant b_(2p+1)
Partie C : Soit p_n le nombre total de partitions de E en partie non vides. On convient que p_0 = 1.
Montrer que : p_n = (de k=1 à n) ((k-1) parmi (n-1)) p(n-k) = (de k=0 à n-1) (k parmi (n-1)) p_k.
Voila, j'ai un exercice avec des questions qui me posent souci... Un petit coup de pouce serait donc le bienvenu !
Merci d'avance.
Pardon, j'ai oublié de signaler ceci : on suppose que n est pair et on pose n = 2p (p entier naturel).
si ta partition contient p doubletons alors il te faut choisir 2 p éléments de E que tu partages en p paires puis il reste ... le reste...
pour partitionner ton ensemble à n =2p considère tes n-2 premiers éléments +les 2 derniers
tu as ap-1 façons de partitionner tes n-2 éléments
maintenant combien de façons as-tu de prendre ces n-2 premiers éléments: (2p-1) façons de permuter l'un des 2 derniers avec l'un des 2p-2 premiers
attention il faudra être plus rigoureux avec ma demo (je pense qu'il faut considérer peut-être le dernier élément)
pour ap en fonction de p écris tes p égalités pour p=2,3,,...p puis multiplie les entres elles membre à membre et simplifie
a_p en fonction de p c'est bon ;
mais finalement pour la question précédente, on a 2p-1 façons de permuter l'un des deux derniers éléments, mais on a alors 2p-2 façons de permuter le dernier ?... donc la formule serait a_p = (2p-2)(2p-1)a_(p-1), ce qui n'est pas le cas...
non car quand tu as permuté l'avant dernier le dernier formera une paire avec le nouveau avant dernier...
tu l'auras donc donc bien aparier avec tous les autres
Je ne comprends pas bien : si j'ai par exemple x_1 x_2 x_3 x_4, je peux mettre x_5 avant x_1, entre x_1 et x_2, entre x_2 et x_3, entre x_3 et x_4 ou après x_4. J'obtiens ainsi 2 nouvelles paires et un singleton. Donc j'ai bien 5 choix pour x_5 (i.e. l'avant dernier).
Je peux mettre x_6 (le dernier) avec le singleton restant, mais je peux aussi le mettre avec n'importe quel autre élément de sorte à créer de nouvelles paires (doubletons). J'ai donc alors 6 choix pour placer x_6, non?
notons y et z les 2 derniers éléments (qui forment une dernière paire) et a et b 2 éléments qui forment la première (par exemple) paire
quand tu as fait toutes tes paires avec les 2p-2 premiers éléments alors:
pour chacune des paires tu peux permuter y avec l'un des 2 éléments ce qui te fait 2p-2 solutions
et idem avec z qui va te donner les mêmes solutions
mais quand tu permutes y et z avec les 2 éléments d'une même paire tu obtiens la même partition donc il faut retrancher 1 solution double...
Ok merci, je vais creuser ça !
Une idée pour la partie B ? je suis vraiment pas à l'aise avec cet exo...
il faut faire la même chose
considère ton ensemble à n=2p éléments que tu as partitionné en paires ou singleton puis rajoute tes éléments a et b et compte...
si n=2p tu ajoutes un élément donc forcément tu as un singleton puis si tu rajoutes un élément alors ça redevient pair
Oui mais ce n'est pas parce que j'ai un nombre pair d'éléments que j'ai forcément que des doubletons ; je peux toujours avoir des singletons...
va voir le topic "partition DM"
Perroquet a donné toutes les réponses et très claires .....mais faut chercher!!!!
Bon ben je suis toujours bloqué à la deuxième question de la partie B... Si quelqu'un peut m'aider ce serait très gentil... !
Annuler
connectez vous
algèbre en post-bac