[capes] leçon 3 : coef binomiaux

Bonjour
Je suis en train de faire la leçon 3 du capes sur les coefficients binomiaux, il y a deux démos qui m'ennuient.
J'ai mis une proposition sur les C(n,k).
J'ai :
1) C(n,p)=C(n,n-p)
2) C(n+1,p+1)=n+1/p+1 * C(n,p)
3) C(n+1,p+1)=C(n,p)+C(n,p+1)

J'ai montré ces 3 formules avec les factorielles, donc par le calcul, mais j'aimerais avoir une autre preuve par le dénombrement, mais je ne suis pas trop à l'aise.
Pour le 1), par exemple, je voulais considérer une fonction entre l'ensemble des parties de cardinal p et celui des parties de cardinal (n-p), en associant à une partie son complémentaire.
Et je devrais montrer que cette fonction est bijective, est-ce que mon raisonnement est bon ?

Auriez vous des idées pour le 2) et 3) ?
Peut-être qu'une preuve est suffisante, mais je me dis que le jury peut très bien demander une preuve avec peu de calcul..
Séverine

Réponses

  • salut,
    pour 1) c'est cela.
    pour 2) je ne vois pas l'intérêt de cette formule.
    pour 3), on montre C(n,p)=C(n-1,p)+C(n-1,p-1)
    on considère l'ensemble E à n élmts. On effectue une partition des parties de E à p élmts. On choisit un élmt x fixé.
    alors un ensemble de la partition peut être rangé selon deux cas:
    * Il ne contient pas x: ce sont des parties à p élmts pris parmi n-1 élmts de E différents de x, donc il y en a C(n-1,p)
    * Il contient x: ce sont des parties obtenues en ajoutant x aux parties à p-1 élmts choisis parmi n-1 élmts distincts de x. Il y en a C(n-1,p-1)
    d'où le résultat.
  • Merci JeroM,
    je me sers de la formule 2 pour montrer le théorème de Fermat si mes souvenirs sont bons.
    Pour le 1), comment montrerais tu la bijection ? JE ne suis pas sure de ce que j'ai fait.
    Séverine
  • La formule 2 s'utilise aussi dans le calcul de l'espérance et de la variance d'une variable aléatoire suivant une loi binomiale.
    Cette formule se prête bien aussi à une programmation récursive du calcul des coefficients du binôme.
  • bonjour Séverine,

    comme interprétation combinatoire de la formule
    $$C_n^p=\frac{n}{p}\,C_{n-1}^{p-1}$$
    je suggère qu'on choisisse d'abord $p$ éléments parmi $n$ (soit donc $C_n^p$ choix possibles) puis qu'on en choisisse un parmi ces p éléments, soit donc finalement $p\,C_n^p$ possibilités. Comme il revient au même de choisir un élement parmi $n$ puis de choisir les $p-1$ élements qui l'accompagnent parmi les $n-1$ restants (soit $C_{n-1}^{p-1}$ choix), ceci donne $n\,C_{n-1}^{p-1}$ possibilités. Bilan :
    $$p\,C_n^p=n\,C_{n-1}^{p-1}$$
    Cette formule est utile, comme l'a dit guiguiche, pour calculer l'espérance d'une loi binomiale.

    Par ailleurs (pour ta leçon), sans même parler des proba, il y a des milliards d'exercices possibles utilisant les $C_n^p$ et/ou la formule du binôme. Exemples :
    - formule d'inversion de Pascal et application au dénombrement des surjections.
    - formule de Vandermonde
    - calculer
    $$\sum_{k=0}^n\,(-1)^k\,C_n^k\,k^p$$
    ($p$ entier fixé $\leq n$).
    - calculer
    $$\sum_{k=0}^n\,C_n^k\,\frac{(-1)^k}{k+1}$$
    etc...
  • Pour l'espérance de la loi binomiale, ne pas oublier la méthode de la "fonction génératrice": on développe, par la formule du binôme, la fonction: F(x)=(px+q)^n. Le calcul de F'(1) donne l'espérance et le calcul de F"(1) permet d'obtenir la variance
  • oui RAJ, bien entendu, utiliser la fct génératrice est évidemment <I>beaucoup </I> plus rapide qu'une solution "directe" (calcul de la somme des kp(X=k)), mais, c'était juste pour citer une application possible de la formule.<BR>
  • Oui, ou bien la génératrice $\displaystyle {f(x) = \sum_{k=0}^{n} \binom {n,k} (pe^x)^k (1-p)^{n_k} = (pe^x + 1 - p)^n}$, et $E(X) = f'(0)$, alors que $E(X^2) = f''(0)$.

    La formule 2 de Séverine sert par exemple en arithmétique sur Petit Fermat comme elle l'a dit, ou, plus exactement, à établir l'outil suivant qui sert dans petit Fermat : si $n > 1$ est entier et $1 \leqslant k < n$ est entier, alors $\displaystyle {\frac {n}{pgcd(n,k)} \mid \binom {n,k}$.

    Borde.
  • Oui, ou bien la génératrice $\displaystyle {f(x) = \sum_{k=0}^{n} \binom {n,k} (pe^x)^k (1-p)^{n-k} = (pe^x + 1 - p)^n}$, et $E(X) = f'(0)$, alors que $E(X^2) = f''(0)$.

    La formule 2 de Séverine sert par exemple en arithmétique sur Petit Fermat comme elle l'a dit, ou, plus exactement, à établir l'outil suivant qui sert dans petit Fermat : si $n > 1$ est entier et $1 \leqslant k < n$ est entier, alors $\displaystyle {\frac {n}{pgcd(n,k)} \mid \binom {n,k}}$.

    Borde.
  • Oui, ou bien la génératrice $\displaystyle {f(x) = \sum_{k=0}^{n} \binom {n}{k} (pe^x)^k (1-p)^{n-k} = (pe^x + 1 - p)^n}$, et $E(X) = f'(0)$, alors que $E(X^2) = f''(0)$.

    La formule 2 de Séverine sert par exemple en arithmétique sur Petit Fermat comme elle l'a dit, ou, plus exactement, à établir l'outil suivant qui sert dans petit Fermat : si $n > 1$ est entier et $1 \leqslant k < n$ est entier, alors $\displaystyle {\frac {n}{pgcd(n,k)} \mid \binom {n}{k}}$.

    Borde (doublon...).
  • séverine,
    je reviens sur ton "problème" de bijection pour établir $C_n^p=C_n^{n-p}$ : il me paraît aller de soi que l'application qui, à toute partie à $p$ élements d'un ensemble $E$ à $n$ éléments associe son complémentaire, est une bijection de $\mathcal{P}_p$ sur $\mathcal{P}_{n-p}$ ($\mathcal{P}_p$= ensemble des parties de $E$ à $p$ éléments), puisque, de façon générale, l'application $\varphi $ qui, à une partie d'un ensemble $\Omega $ quelconque (fini ou non) associe son complémentaire dans $E$ est une bijection de $\mathcal{P}(\Omega )$ sur lui-même (évident puisque $\varphi \circ \varphi =\text{Id}_\Omega $).
    La seule chose à ajouter, c'est que le complémentaire d'une partie à $p$ éléments dans un ensemble à $n$ éléments a $n-p$ éléments... ce qui peut se démontrer bien entendu, mais je ne sais pas s'il est vraiment nécessaire de remonter jusque là... et si tu es vraiment obligée de détailler les propriétés très élémentaires de cardinalité des ensembles finis.
  • séverine,
    je reviens sur ton "problème" de bijection pour établir $C_n^p=C_n^{n-p}$ : il me paraît aller de soi que l'application qui, à toute partie à $p$ élements d'un ensemble $E$ à $n$ éléments associe son complémentaire, est une bijection de $\mathcal{P}_p$ sur $\mathcal{P}_{n-p}$ ($\mathcal{P}_p$= ensemble des parties de $E$ à $p$ éléments), puisque, de façon générale, l'application $\varphi $ qui, à une partie d'un ensemble $\Omega $ quelconque (fini ou non) associe son complémentaire dans $\Omega $ est une bijection de $\mathcal{P}(\Omega )$ sur lui-même (évident puisque $\varphi \circ \varphi =\text{Id}_\Omega $).
    La seule chose à ajouter, c'est que le complémentaire d'une partie à $p$ éléments dans un ensemble à $n$ éléments a $n-p$ éléments... ce qui peut se démontrer bien entendu, mais je ne sais pas s'il est vraiment nécessaire de remonter jusque là... et si tu es vraiment obligée de détailler les propriétés très élémentaires de cardinalité des ensembles finis.
  • Séverine puisque tu passes le capes, en TS on préfère plutôt la démonstration ensembliste que la démo avec l'expression explicite des coefficients binomiaux... d'ailleurs c'est ce que j'ai demandé à ma dernière interro.
    Tu peux prolonger avec $\binom{n-2}{k-2}+2\binom{n-2}{k-1}+\binom{n-2}{k}=\binom{n}{k}$ soit en partant du c, soit directement comme en c en fixant deux éléments a et b. Intérêt : aucun.
  • si un aimable modérateur pouvait, dans mon message ci-dessus, remplacer le
    $\varphi \circ \varphi =\text{Id}_\Omega $ par un $\varphi \circ \varphi =\text{Id}_{\mathcal{P}(\Omega )}$, j'ai honte...
    merci.
  • Merci beaucoup pour ces interventions.
    J'ai encore quelques questions.
    Dans la leçon 6 sur :
    Variables aléatoires réelles dont l'ensemble des valeurs est fini, loi de probabilité, espérance mathématique, variance, exemples.

    Faut il parler des sommes de variables aléatoires ?
    Comment expliquer concrètement ce que représente la variance ?

    Séverine
  • La loi binomiale se présente naturellement comme une somme de v.a. de Bernoulli: S=X(1)+..+X(i)+..+X(n), avec X(i)=1 en cas de succès à l'épreuve i et X(i)=0 en cas d'échec. C'est aussi une méthode pour calculer l'espérance et la variance de S.
    Mais attention aux pièges. Il faut pouvoir montrer que l'espérance d'une somme est la somme des espérances et la même chose pour la variance (dans le cas de v.a. indépendantes).
    La variance mesure les écarts à la moyenne, donc la dispersion des résultats. Dans le cas de la loi binomiale il est intéressant d'étudier la variance en fonction de p.
  • Merci beaucoup pour ces interventions.
    J'ai encore quelques questions.
    Dans la leçon 6 sur :
    Variables aléatoires réelles dont l'ensemble des valeurs est fini, loi de probabilité, espérance mathématique, variance, exemples.

    Faut il parler des sommes de variables aléatoires ?
    Comment expliquer concrètement ce que représente la variance ?

    Séverine
  • En reprenant les notations de RAJ, tu peux aussi regarder l'espérance et la variance de S_n/n (fréquence de succés), regarder la limite à l'infini et conclure comme il faut.

    Pour la variance tu peux aussi regarder la fonction $x \mapsto \frac {1}{n} \sum {(x-x_i)}^2$ et regarder le minimum.
Connectez-vous ou Inscrivez-vous pour répondre.