Coeff. binomial : démo avec formule de Pascal

waldstein · January 2016

Bonjour à tous,

Voilà une question dont l'intérêt m'échappe (dites-moi si je me trompe mais on cherche à démontrer une définition, non ? C'est idiot, non ? ^^)
Mais je dois y répondre :

En utilisant la formule de Pascal, démontrer :
$\forall n \in \mathbb{N}, \forall p \in \mathbb{N}, p \leq n, {n \choose p} = \dfrac {n!}{p!(n-p)!}$

Je soupçonne une récurrence mais sur quoi ? Sur p ? Sur n ? Récurrence forte ?

Merci d'avance.

P. · January 2016

${n \choose p}$ dans ce contexte est surement defini comme le nombre de parties de taille $p$ dans un ensemble de taille $n$.

waldstein · January 2016

Oui, en effet.
Mais du coup, je pars sur une récurrence ?

waldstein · January 2016

Je bloque vraiment, pour le coup...

Utilisateur anonyme · January 2016

pourquoi une récurrence ??? en calcul froidement direct, à partir de $\displaystyle{\binom{n+1}{p+1}=\binom{n}{p}+\binom{n}{p+1}}$ ...

P. · January 2016

Si tu veux. Mais compter le nombre de suites de longueur $p$ d'objets differents pris parmi un ensemble de taille $n$ se fait sans recurrence et donne $n\times (n-1)\times \cdots\times (n-p+1)$. Si tu identifies deux suites lorsque elles contiennent les memes objets, tu n'as qu'a diviser leur nombre par $p!$ et tu obtiens ainsi
$${n \choose p}=\frac{n(n-1)\ldots(n-p+1)}{p!}=\frac{n!}{p!(n-p)!}.$$

waldstein · January 2016

Oui, ça c'est la démonstration habituelle. On divise le nombre d'arrangements par le nombre de permutations possibles.
Mais ici, on me demande de le démontrer à partir de la relation de Pascal...

waldstein · January 2016

ezmaths : mon froid calcul s'arrête à :

$\binom{n}{p}=\binom{n+1}{p+1}- \binom{n}{p+1}$

Et à moins de raisonner avec une division par (p+1)! des arrangements pour trouver les membres de droite, je ne vois pas. De plus c'est complètement idiot puisque c'est un raisonnement qu'on peut faire directement pour p parmi n, pas besoin de s'encombrer de la relation de Pascal !

P. · January 2016

Alors il te faut montrer la formule dont part ezmath...appelee formule de Pascal. Cela se fait ainsi. Tu partages l'ensemble des parties de taille $p+1$ de l'ensemble de taille $n+1$ en deux categories

A) Ceux qui contiennent $n+1$: il y en a ${n \choose p}$

Ceux qui ne contiennent pas $n+1$ : il y en a ${n \choose p+1}.$

Ton hypothese de recurrence devient alors supposons que pour tout $p\in [0,n]$ on ait ${n \choose p}=\frac{n!}{p!(n-p)!)}.$ La formule de Pascal te permet d'etendre cela a $n+1.$ Si tu veux la note maximale, fais attention aux valeurs extremes de $p=0$ et $p=n.$

GaBuZoMeu · January 2016

Pourquoi voulez-vous empêcher waldstein de faire une récurrence sur $n$, en utilisant la formule de Pascal pour l'étape de récurrence ?
(Bon, waldstein, il vaudrait mieux que tu corriges la coquille dans ta formule avant de la démontrer).

waldstein · January 2016

Ah oui, il y avait une coquille ^^ C'est réglé.

waldstein · January 2016

Oh, la note maximale, ça ne me concerne pas !
J'aide une amie avec ses devoirs de prépa ECE. Pour moi, c'est du passé (enfin j'ai fait MP, du coup le dénombrement et les probas c'est pas ma tasse de thé...)

Voilà, c'est mon hypothèse. C'est donc une récurrence forte.

Initialisation : $\binom{0}{0}=1=\frac{0!}{0!0!}$

Soit $n \in\mathbb{N}$ vérifiant l'hypothèse de récurrence et $p<n$ (on a donc $p+1 \leq n$)

$\binom{n}{p}+\binom{n}{p+1}=\frac{n!}{p!(n-p)!}+\frac{n!}{(p+1)!(n-p-1)!}$ par hypothèse de récurrence
$\binom{n+1}{p+1}=\frac{(n+1)!}{(p+1)![(n+1)-(p+1)]!}$ En mettant au même dénominateur et en appliquant la relation de Pascal.

Pour $p=n$ pas besoin de la relation de Pascal, c'est évident.

C'est bon ?

bisam · January 2016

À ma connaissance, le dénombrement n'a jamais déserté le programme de Math Sup... et désormais les probas l'ont rejoint.

waldstein · January 2016

Hum... Tu dis peut-être vrai !
Sûrement en fait ^^
Mais c'était il y a sept ans, pour moi. Ça commence à faire !
C'est une bonne chose d'avoir intégré les probas au programme de MP

noix de totos · January 2016

Waldstein a écrit:

C'est une bonne chose d'avoir intégré les probas au programme de MP

C'est une moins bonne chose que, pour ce faire, on ait été obligé de virer les séries de Fourier...

curiosity · January 2016

Plus de SF du tout en prépa ???

Rescassol · January 2016

Bonjour,

Bah, c'était de la Science Fiction.

Cordialement,

Rescassol

Samuel DM · January 2016

Et pourtant le chapitre sur les espaces préhilbertiens mentionne les familles orthonormées, l'égalité de Parseval, l'inégalité de Bessel, Cauchy-Schwarz, le théorème de Pythagore etc... On dirait que l'on s'est étalé sur la ligne d'arrivée en enlevant Fourier !

Chaurien · January 2016

Pour en revenir à la question initiale, il me semble que la notion de départ est celle des $k$-arrangements d'un $n$-ensemble, qui sont les $k$-suites injectives d'un $n$-ensemble, ou les applications injectives d'un $k$-ensemble dans un $n$-ensemble. Il semble qu'ils aient disparu des écrans-radar, et je le déplore. Leur nombre se notait $A_{n}^{k}$, aujourd'hui plutôt $(n)_{k}$, et ce nombre est : $n(n-1)...(n-k+1)$ (démonstration immédiate). Avec $A_{n}^{0}=(n)_{0}=1$ (une seule application dans ce cas, l'application vide, qui est injective).
Il est à noter que si $k>n$, la formule précédente donne $A_{n}^{k}=(n)_{k}=0$, ce qui est la bonne valeur puisqu'alors il n'y a pas de telles applications-suites injectives, et quand il n'y a pas de quelque chose, c'est qu'il y en a $0$. Ainsi, la formule $A_{n}^{k}=(n)_{k}=n(n-1)...(n-k+1)$ est vraie de tout $n \in \mathbb{N}$ et de tout $k \in \mathbb{N}$.

Par définition le nombre de $k$-parties d'un $n$-ensemble est désigné par : $(_{k}^{n})$. Pour chaque $k$-partie $X$ d'un $n$-ensemble $E$, le nombre de $k$-suites injectives de $E$ dont l'ensemble-image est $X$ est : $(k)_{k}=k!$ (permutations de $X$). Il en résulte : $k!(_{k}^{n})=(n)_{k}$, ou : $(_{k}^{n})=\frac{(n)_{k}}{k!}$ (principe des bergers).

Telle est comme j'ai déjà dit, la meilleure formule que nos élèves devraient mémoriser : $(_{k}^{n})=\frac{n(n-1)...(n-k+1)}{k!}$, avec : $(_{0}^{n})=1$, car elle est vraie de tout $n \in \mathbb{N}$ et de tout $k \in \mathbb{N}$.

Maintenant, dans le cas particulier où $0\leq k\leq n$, on a : $(_{k}^{n})=\frac{n!}{k!(n-k)!}$, formule - hélas ! - préférée de nos élèves sans doute en raison de son caractère "compact", mais qui n'est pas la meilleure. Comme j'ai dit aussi, regardez comment s'énonce l'identité de convolution de Vandernonde si vous supposez que le symbole $(_{k}^{n})$ est défini seulement si $0\leq k\leq n$, et bon courage.

Bonne soirée.
F. Ch.

Chaurien · January 2016

Autre démonstration combinatoire.
En associant à chaque partie d'un $n$-ensemble $E$ sa fonction caractéristique, on voit que, si $0\leq k\leq n$, alors $(_{k}^{n})$ est le nombre de $n$-suites de $1$ et de $0$ avec $k$ termes égaux à $1$ et $n-k$ termes égaux à $0$.
C'est donc le nombres de mots (= suites) de $n$ lettres formés avec deux lettres $A$ et $B$, comprenant $k$ fois la lettre $A$ et $n-k$ fois la lettre $B$. Si l'on distingue les lettres $A$ et $B$ en les affectant d'indices : $A_1, A_2,...,A_k$ et $B_1,B_2,..., B_{n-k}$, alors le nombre de ces mots est le nombre de permutations des $n$ lettres ainsi distinguées, c'est donc $n!$. Si maintenant on considère des classes regroupant ces mots où les lettres $A$ sont en mêmes positions et ne diffèrent que par les indices, l'effectif de chacune de ces classes est le nombre de permutations des lettres indicées $A_1, A_2,...,A_k$, c'est donc $k!$. Et de même pour la lettre $B$. Le nombre de mots avec lettres non indicées est donc : $(_{k}^{n})=\frac{n!}{k!(n-k)!}$ (principe des bergers).

On en déduit le nombre de trajets sur un quadrillage, qui est un coefficient binomial, car chacun de ces trajets peut se représenter par uns suite de termes ayant chacun deux valeurs possibles, la direction à emprunter chaque fois.

Ceci se généralise aux permutations avec répétitions. Le nombre de mots de $n$ lettres formés avec les $q$ lettres $L_1, L_2,...,L_q$, avec $n_i$ fois la lettre $L_i$, avec $n_{1}+n_{2}+...+n_{q}=n$, est : $(_{n_{1},n_{2},...,n_{q}}^{~~~~~~~n})=\frac{n!}{n_{1}!n_{2}!...n_{q}!}$.

Bonne journée.
F. Ch.

Chaurien · January 2016

Et pour contribuer aux remarques générales ci-dessus, je dirai qu'il est bon que les élèves de prépas étudient le Calcul des Probabilités, mais le programme de Math. Sup., qui concerne les probabilités sur un ensemble fini, pourrait plutôt être étudié en Terminale, à la place de la loi normale ou de la loi exponentielle, qui ne peuvent être traitées convenablement puisqu'on ne connaît pas les intégrales généralisées à ce niveau et il est bien clair qu'on ne peut les aborder que plus tard. Cet enseignement des probabilités sur un ensemble fini existait en Terminale C, D, E il y a trente ans.

Sous le prétexte de l'introduction de ces probabilités, on a supprimé en Math Spé. les suites de Cauchy, les séries de Fourier, les intégrales multiples, les espaces préhilbertiens complexes, les formes quadratiques, presque tout sur les courbes, et j'en passe. Alors qu'on se pique d'interdisciplinarité on a coupé les ponts avec les sciences physiques. Programmes signés Gribouille.

Ceci pour les Probabilités, mais pour la Combinatoire c'est une autre question, elle a toujours été une parente pauvre des programmes de mathématiques, même en prépa-HEC. Elle n'a jamais été considérée comme une discipline mathématique à part entière, mais un appendice des Probabilités. On trouve très peu de questions spécifiquement combinatoires dans les problèmes de concours.

Et même ici, j'ai eu du mal à retrouver ce fil de discussion, car il a été placé dans le forum "probabilités", alors qu'il n'y a rien de probabiliste dans son contenu !

Bonne journée ce nonobstant,
F. Ch.

Coeff. binomial : démo avec formule de Pascal

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 34