Question sur les combinaisons

[Cyril]

Le garçon a 17 ans et vous prédisez qu'il n'aura jamais aucun talent mathématiques parce qu'il a du mal à comprendre un résultat (beaucoup de mal j'en conviens)? Vous vous prenez pour qui? Si vous étiez prof, pourquoi pas, mais venant de sup/spé qui n'ont pas prouvé grand chose, j'ai du mal à comprendre.
Pour l'auteur :
Je te conseille de travailler quelques exercices de dénombrement, ce genre de résultat se devine quand on a l'habitude (au delà de la preuve par le calcul quand on connaît la,formule).
Par exemple, si je tire une bille parmi n, que je la remet, et que j'en retire une autre, qu'elle est la proba d'avoir tiré deux fois la même?
Si mon prof mes des notes au pif (équiprobabilite) qu'elle est la proba que j'ai strictement plus que mon voisin?
Si je tire en même temps deux boules parmi n numérotées de 1 à n, qu'elle est la proba d'en tirer deux consécutives?

[Ellias42]

Le garçon a 17 ans et vous prédisez qu'il n'aura jamais aucun talent mathématiques parce qu'il a du mal à comprendre un résultat (beaucoup de mal j'en conviens)? Vous vous prenez pour qui? Si vous étiez prof, pourquoi pas, mais venant de sup/spé qui n'ont pas prouvé grand chose, j'ai du mal à comprendre.

Ca a déjà été dit et on est passé à autre chose, pas la peine d'en rajouter la dessus

[KGD]

Bon bah vas y demontre moi que les combinaisons de k éléments dans un ensemble à n éléments c'est n!/k!(n-k)!

Excusez moi, j'ai passé l'après-midi à chercher la démonstration de la formule, est-ce que quelqu'un pourrait me dire si celle-ci est correcte et s'il y aurait moyen de faire plus court:

SPOILER:

J'ai commencé par montrer par récurrence que le nombre de k-listes pour un ensemble E à n éléments était: $ \frac{n!}{(n-k)!} $:
. C'est clairement vrai pour k=0
. On suppose la proposition vérifiée pour k entre 0 et n-1. Pour i compris entre 0 et n on pose $ E_i $ l'ensemble des i-listes de E.
On définit sur $ E_{k+1} $ la relation $ a \sim b \Leftrightarrow a_{k+1} = b_{k+1} $.
C'est une relation d'équivalence et on note $ F_k = E_{k+1}/\sim $ et $ \~{a} $ la classe d'une k+1-liste a.
Soit a une k+1-liste, on définit $ f: \~{a} \to E_k $ par $ f(x) = (x_1,x_2,...,x_k) $. Elle est injective car si $ f(x)=f(y) $, alors pour tout i entre 1 et k, on a $ x_i=y_i $ or elles sont de la même classe d'équivalence donc on a aussi $ x_{k+1}=y_{k+1} $ donc $ x=y $. Elle est aussi surjective car pour toute k-liste $ (x_1,x_2,...,x_k) $, il suffit de prendre pour antécédent la liste $ (x_1,x_2,...,x_k,a_{k+1})\in \~{a} $. Il s'agit donc d'une bijection et on a donc pour tout $ a \in E_{k+1} $, $ |\~{a}| = |E_k| = \frac{n!}{(n-k)!} $ par hypothèse de récurrence. On montre ainsi au passage que toutes les classes d'équivalence sont équipotentes, il suffit donc pour conclure de compter les classes d'équivalence. Il y en a autant que de choix de k+1_ième élément, or les éléments d'une liste sont deux à deux distincts donc pour une k+1-liste a, on doit avoir $ a_{k+1}\in E-\{a_1,...,a_k\} $ qui comporte $ n-k $ éléments.
On a donc $ |E_{k+1}| = (n-k)|\~{a}| = \frac{n!}{(n-k-1)!} $, ce qui permet de conclure.

J'ai ensuite utilisé à peu près la même méthode pour montrer que le nombre de parties à k éléments était $ \frac{n!}{(n-k)!k!} $
On regroupe les k-listes qui ont les mêmes éléments avec la relation d'équivalence $ a \smile b \Leftrightarrow \exists \sigma\in Perm([[1,k]]) / (b_i)=(a_{\sigma(i)}) $ où $ Perm(X) $ désigne l'ensemble des permutations de X (elle est clairement réflexive, symétrique car l'inverse d'une permutation est une permutation, transitive puisque la composition de permutations est une permutation). On pose $ G_k = E_k/\smile $ et on note $ \u{a} $ la classe d'une k-liste a. Soit ensuite a une k-liste, on considère l'application $ f: \u{a} \to Perm([[1,k]]) $ qui à toute k-liste $ x \in \u{a} $ associe une permutation $ \sigma $ telle que $ (x_i)=(a_{\sigma(i)}) $. f est bijective d'inverse $ f^{-1}(\sigma) = (a_{\sigma(i)}) $ donc on a $ |\u{a}| = |Perm([[1,k]])| = k! $. Puisque toutes les classes sont équipotentes, on a: $ |E_k| = |\u{a}||G_k| $ d'où $ |G_k| = \frac{n!}{(n-k)!k!} $.
Il ne reste plus qu'à prouver que $ G_k $ est équipotent à l'ensemble des parties à k éléments grâce à l'application qui associe à la classe $ \u{a} $ la partie $ \{a_1,a_2,...,a_k\} $. Elle est injective puisque si deux listes ont la même image, alors elles ont les mêmes éléments et sont donc égales à permutation près et ont donc la même classe d'équivalence. Elle est aussi surjective puisque si $ \{x_1,x_2,...,x_k\} $ est une partie à k éléments, alors la classe de $ (x_1,x_2,...,x_k) $ en est un antécédent.
Le nombre de parties à k éléments est donc bien $ \frac{n!}{(n-k)!k!} $

[maroxe]

Je pense faire plus court dans le sens ou elle utilise une seule reccurence, mais toujours dans le meme esprit:
Pour prendre un ensemble de k+1 elements parmis n+1 (dont x fait parti), soit on prend x et on lui ajoute k elements, soit en choisit k+1 elements parmis les n restants. Le cas de k=0 etant trivial.
Cela donne la formule du binome, par une recurrence on verifie que la formule convient.
Apres il reste a formaliser tout ceci, mais j'ai le flemme de le faire