La somme de $C_p^k$
Bonjour ou bonsoir (voir l'heure)
Sur un livre Oral du CAPES, j'ai trouvé : $$
\sum_{k=p}^n C_k^p= C_{n+1}^{p+1}. \qquad (1)
$$ Puis suivi d'un super $Corollaire $ faisant la relation entre la relation (1) et les sommations classiques $\sum k,\ (p=1)$, $\sum k^2 ,\ (p=2) $ et $\sum k^3 ,\ (p=3)$.
1- Preuve simple de (1).
2- Le passage avec cette méthode, elle parait simple par rapport à la somme de télescopage.
Merci d'avance
Sur un livre Oral du CAPES, j'ai trouvé : $$
\sum_{k=p}^n C_k^p= C_{n+1}^{p+1}. \qquad (1)
$$ Puis suivi d'un super $Corollaire $ faisant la relation entre la relation (1) et les sommations classiques $\sum k,\ (p=1)$, $\sum k^2 ,\ (p=2) $ et $\sum k^3 ,\ (p=3)$.
1- Preuve simple de (1).
2- Le passage avec cette méthode, elle parait simple par rapport à la somme de télescopage.
Merci d'avance
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Merci pour la correction. Une démonstration combinatoire (ce sont celles que je préfère) :
Considérons une partie $A$ à $p+1$ éléments de $\{1,\ldots,n+1\}$. Soit $k+1$ le dernier élément de $A$. Alors $A\setminus \{k+1\}$ est une partie à $p$ éléments de $\{1,\ldots,k\}$ et ceci établit une bijection entre
1) l'ensemble des parties à $p+1$ éléments de $\{1,\ldots,n+1\}$
et
2) l'ensemble des couples $(k,B)$ où $k$ est un entier entre $p$ et $n$ et $B$ une partie à $p$ éléments de $\{1,\ldots,k\}$.
Ah, oui je vais la corriger
Voici une démonstration plus simple:
$C_{n+1}^{p+1}$ est le coefficient de $x^{p+1}$ dans le polynôme $p(x)=(x+1)^{n+1}$
tandis que le membre de gauche est le coefficient de $x^{p+1}$ dans le polynôme
$q(x)=x\sum_{k=0}^n (x+1)^ k $ mais $q(x)=(x+1)^{n+1}-1 =p(x)-1$.
Et tu confonds ta droite et ta gauche ?
Donc il n'y a rien de compliqué dans ma démonstration et elle est simple.
Ensuite concernant ta démonstration il faut dire qu'il faut faire un effort pour la comprendre car ça commence par "Considérons une partie A à p+1 éléments de {1,…,n+1}. Soit k+1 le dernier élément de A"
Peut être veux tu dire soit A une ..... tel que le plus grand éléments et k+1??
Alors pour k dans {p,...n} fixé, le nombre de parties A ayant pour plus grand élément k+1 est effectivement $C_{k}^p$ ,... ok mais bon en première lecture..
Et je vois que tu as tout de même compris la démonstration que j'ai faite ... en seconde lecture ;-)
Je ne dis pas que ta démonstration est très compliquée - je la comprends très bien. Je dis qu'elle n'a rien de plus simple que la démonstration combinatoire, et que pour moi la démonstration combinatoire est plus agréable. Peut-être es-tu mal à l'aise avec ce genre de démonstration combinatoire ?
Donc si tu désignes par $E$ l'ensemble des parties à $p+1$ éléments de $\{1,\ldots,n\}$, un élément $A$ de $E$ admet un plus grand élément que tu notes $k+1$ et les valeurs possibles de $k$ vont de $p$ à $n$.
Ainsi tu as une partition de $E=\cup _{k=p}^n E_k$ où $E_k$ désigne les parties de $\{1,\ldots,n\}$ à $p+1$ éléments dont le plus grand élément est $k+1. $
L'identité à démontrer vient donc de $card(E)=card(E_p)+\cdots+card(E_n).$
En tout cas, il faut que admettre que si tu mets ça dans ta copie, je ne sais pas si ton prof va comprendre ton idée tout de suite ton idée et je doute qu'il va faire l'effort que j'ai fait.
(:D
Si tu reformules de façon plus compliquée et moins compréhensible ce que j'ai écrit (en oubliant en particulier la bijection que j'ai explicitement écrite), c'est sûr que ça devient moins évident à voir.
En passant, le prof, c'est moi. ;-)
Tu commences par :
" Considérons une partie $A$ à $p+1$ éléments de $\{1,\ldots,n+1\}$. Soit $k+1$ le dernier
élément de $A$. "
Alors je me suis dit c'est quoi $k$? Quelle valeur peut prendre $k$ ? Qu'est-ce qu'un dernier élément de $A$ ?
Bref c'est pas engageant à lire la suite.
Peut-être, il veut dire le plus grand élément de $A$ ?
Du point de vue pédagogique, tu aurais pu soigner le début de la démonstration afin d'être compris plus vite.
Maintenant me dire que ''le plus grand élément de $A$ n'a pas de sens'' je reste perplexe.
Il vaut mieux tourner la page..
Après une accalmie et plusieurs relecture à partir de son 2), voici une explication combinatoire que n'importe quel esprit L1 peut accepter en première lecture (Tyoussef le confirmera ou le niera)
On prend la convention que $C_k^p=0$ si $p>k$, donc la formule à démontrer est $\sum_{k=0}^n C_k^p= C_{n+1}^{p+1}$
Imaginons les premiers $n + 1$ chiffres, écrits dans l’ordre sur le sable d'une plage.
Si on demande de combien de façons nous pouvons en choisir $p + 1$. La réponse est $C^{p+1}_{n+1}.$
Pour réaliser ces façons, on choisit d'abord le plus grand nombre, que je note par $g$ (comme gebrane). Ensuite, on choisit $p$ nombres, chacun inférieur à $g$, et il y a $C^p_{g-1}$ façons de le faire.
Puisque $g$ va de 1 à $n + 1$, $k = g-1$ va de 0 à $n $ donc $$ \sum_{k=0}^n C_k^p= C_{n+1}^{p+1}$$
Je rappelle ce que j'ai écrit : Je passe sur le "et" au lieu du "est". Mais le "tel que le plus grand élément est k+1" supposerait que l'entier $k$ ait été précédemment défini, ce qui n'est évidemment pas le cas. Donc oui, ta phrase n'a pas de sens et indique que tu n'avais pas compris ce que j'ai écrit. Ma phrase "Soit $k+1$ le dernier élément de $A$" définit l'entier $k$.
Si on se pique de donner des leçons, il vaut mieux ne pas déformer la réalité.
Peut-on retrouver ce résultat sans considérations ensemblistes, juste par le calcul avec la définiton des combinaisons et les factorielles ?
J'ai essayé mais je me suis un peu embourbé...
Dis-moi as-tu compris ma version combinatoire en première lecture ? :-D
[Gébrane, écris tes mots en entier. Merci. AD]
[AD j’étais sur un téléphone]
Je suppose que tu veux dire une démonstration purement par le calcul, c'est-à-dire uniquement en utilisant $$
C_k^p=\frac {k!}{(k-p)! p!}.
$$ Personnellement je ne pense pas où alors ce n'est pas facile. Mais c'est à voir.
Mais naturellement surtout pour un oral de Capes, il vaut mieux voir que $C_{n+1}^{p+1}$ est le nombre de parties de $p+1$ éléments d'un ensemble de $n+1$ éléments et que l'identité à démontrer est une directe conséquence du partitionnement de cette ensemble en les parties de $p+1$ éléments dont le plus grand élément est $k+1$ pour $k=p$ jusque $ n$.
Dans ce genre d'exercice (classique) on s'en sort souvent aussi très bien en utilisant le binôme de Newton (ce que j'ai proposé.)
Par le calcul "pur", quand c'est faisable, c'est un très bon exercice mais ce n'est pas toujours la meilleure voie.
Suite à ton message http://www.les-mathematiques.net/phorum/read.php?4,1846998,1847324#msg-1847324, un simple télescopage permet de conclure, mais je laisse un temps pour totem
Mise à jour: un télescopage ?? ah je ne l'ai pas vu !
@bd2017: en effet c'est ça que je veux dire .:-)
Mais je crois que tu as raison c'est sans doute irréaliste...enfin à mon niveau L2/3 en tout cas !
Maintenant tu l'as vu ce télescopage ? la formule se démontre en une seule ligne ( n'est ce pas Gabu?)
Suis-je dans la bonne direction ?
$$\sum_{k=p}^n C_k^p= \sum_{k=p}^n [C_{k+1}^{p+1}-C_{k}^{p+1}]=C_{n+1}^{p+1}-C_{p}^{p+1}=C_{n+1}^{p+1}$$
Bonjour, connais-tu d'autres exemples qui se résolvent par l'analyse combinatoire?
Merci d'avance
Et si on essaie cette égalité $\binom{2n}{n}=\sum\limits_{k=0}^n\binom{n}{k}^2$
Une récurrence la traite rapidement
$$A\longmapsto (|I\cap A|, I\cap A, J\setminus A)$$
est une bijection de l'ensemble des parties à $n$ éléments de $E$ sur l'ensemble des triplets $(k,B,C)$ où $k$ est un entier entre $0$ et $n$ et $B$ et $C$ des parties à $k$ éléments de $I$ et $J$ respectivement.
Je vais te lire, comprendre et profiter de ta disponibilité pour d'autre preuves combinatoires
Merci Cher Gabu
Tu peux toujours diviser tes $2n$ éléments en deux paquets de $n$ éléments. Pour piocher $n$ éléments parmi les $2n$ éléments, tu choisis $k$ éléments dans le premier paquet (pour $k$ allant de $0$ à $n$) et $n-k$ dans le deuxième paquet.
Personnellement je trouve toujours plus simple d'exprimer la solution par le binôme de Newton, i. e
$(1+x)^{2n}=(1+x)^n(1+x)^n=\sum_{j=0,...n} C_n^j x^j \sum_{k=0,...n}C_n^k x^{k}=\sum_{k,j=0,...n} C_n^j C_n^k x^{j+k}$ est de dire que l'identité correspond au coefficient de $x^n$ dont la version ensembliste est:
une partie de A de n éléments de l'ensemble $E={1,....2n}$ est constituée de k éléments de l'ensemble
E_1={1,....n} et de n-k éléments de l'ensemble $E_2={n,...,2n}$, k pouvant prendre les valeurs de 0 à n.
Ce qui fait que le nombre de telles parties vaut $\sum_{k=0}^n C_n^ k C_n^{n-k}=\sum_{k=0}^n (C_n ^k)^2.$
Je peux lui faire gentiment remarquer que l'argument algébrique n'est qu'un déguisement de la démonstration combinatoire.
Regardons combien de fois on récupère $x^ny^n$ en développant le produit de $2n$ facteurs
$$(x+y)(x+y)\cdots(x+y)$$
On sépare les $2n$ facteurs en un premier paquet de $n$ (mon ensemble $I$) et un deuxième paquet de $n$ (mon ensemble $J$). C'est la factorisation $(x+y)^{2n}=(x+y)^n(x+y)^n$.
Mon ensemble $A$ à $n$ éléments est l'ensemble des $n$ facteurs où on choisit $x$ ; on choisit $y$ dans les autres, ça fait une des façons d'obtenir $x^ny^n$.
$I\cap A$, c'est l'ensemble des facteurs du 1er paquet où on choisit $x$ ; ça donne $x^ky^{n-k}$. $J\setminus A$, c'est l'ensemble des facteurs du 2e paquet où on choisit $y$ ; ça fait $x^{n-k}y^k$.
Il n'y a pas de mystère : la formule du binôme, c'est la combinatoire du choix des facteurs.
J'ai compris, on m'a aidé que je comprenne avant que tu finisse ton roumain merci bb
Tu es très fort pour la recherche d'une bijection mais je me sens à l'aise dans le partitionnement ( exemple celui de bb)
donc d'un coté c'est $\sum_{k=0}^n C^k_nC^{n-k}_n=\sum_{k=0}^n C^k_nC^{k}_n$ et d'un autre coté $C^n_{2n}$
$$\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$$
PS que de l'analyse combinatoire sinon c'est relativement simple
Merci Gabu pour cette soirée combinatoire
Alors @gabuzomeu je te ferai gentiment remarquer je ne fais pas une copie de ta démonstration mais que simplement il s'avère que c'est équivalent et que je la formule cela plus simplement.
Je ne trouve pas vraiment utile de parler de bijection, cela complique la compréhension, alors qu'en fait la démonstration c'est ni plus ni moins que de dénombrer un ensemble en le partitionnant.
Maintenant c'est une affaire de goût.
Bon, gebrane, ton égalité je préfère la réécrire
$$\sum_{k=0}^{n}\binom{n+k}{n}\,2^{n-k}= \frac12\,2^{2n+1}\;.$$
Je vais interpréter cette égalité comme la trace d'une bijection entre ensembles se dénombrant de manière évidente. Toute l'histoire va se passer dans $E=\{1,\ldots,2n+1\}$.
L'ensemble de gauche est l'ensemble des triplets $(k,B,C)$ où :
1°) $k$ est un entier entre $0$ et $n$,
2°) $B$ est une partie à $n$ éléments de $\{1,\ldots,n+k\}$,
3°) $C$ est une partie quelconque de $\{n+k+2,\ldots,2n+1\}$.
L'ensemble de droite est l'ensemble des paires formées d'une partie de $E$ et de son complémentaire. Dans une telle paire, une des deux parties $A$ a au moins $n+1$ éléments, et l'autre $E\setminus A$ en a au plus $n$.
La bijection entre l'ensemble de gauche et celui de droite est assez claire :
$$(k,B,C)\longmapsto \{A,E\setminus A\} \quad\text{ où } A=B\cup\{n+k+1\}\cup C\;.$$
Pour préciser la bijection réciproque, il suffit de dire que $k$ est l'entier tel que $n+k+1$ est le $n+1$-ème élément de $A$ (pour que bd2017 comprenne bien, je précise que les éléments de $A$ sont rangés dans l'ordre croissant).
Comme d'habitude à lire à comprendre ( je vais y passer du temps)
Un grand merci
edit Merci aussi à lui ou elle pour son mp "The number of binary strings of length $2n+1$ with at least $n+1$ ones is clearly $2^{2n}$. For $k=0,1,2,\ldots,n$, the number of such strings whose $(n+1)$-st one is at the $(n+k+1)$-st position is $\binom{n+k}{k}\,2^{n-k}$. The claim is now evident"
edit je crois que je fais confusion entre nombre de Catalan et constante de Catalan ?
edit 2 j'ai compris ma confusion ( merci à toi mon ange gardien (tu) pour ton mp)
"Une confusion vient souvent d'une mal lecture ou interprétation".
Mon absence est due à une douleur de dos, je souhaite que tout le monde aille bien et que tout le monde soit en bonne santé
48 réponses n'est simple à lire et à examiner en un seul jour.
$@ GaBuZoMeu $
Cela tombe bien car je ne comprends pas ces combinatoires leurs [lorsqu'] ils sont écrits de cette manière c'est-à-dire le langage linguistique.
$@ gebrane$
Merci $gebrane$. Ouiii belle observation, tu as compris je travaille avec les maths du BAC et ceux de 1 année sauf quelque cours, je n'ai pas le doit, en ce moment.
Aurais-tu une démonstration combinatoire de \[ \forall n \in \N, \quad \sum_{k=0}^n k^3 = \Big( \sum_{k=0}^n k \Big)^2 \quad?
\] Si possible simple et pédagogique, hein ?
Amicalement,
e.v.
@ev : https://math.stackexchange.com/questions/95047/combinatorial-interpretation-of-sum-of-squares-cubes