Interprétation combinatoire ?
Bonjour
Peut-on espérer une interprétation combinatoire de la formule suivante, valable pour $n\in\N$ ? $$\sum\limits_{k=0}^n\binom{k+n}{k}2^{n-k}=2^{2n}$$ Merci pour votre aide.
Peut-on espérer une interprétation combinatoire de la formule suivante, valable pour $n\in\N$ ? $$\sum\limits_{k=0}^n\binom{k+n}{k}2^{n-k}=2^{2n}$$ Merci pour votre aide.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Oui on peut espérer une interprétation combinatoire, mais je ne peux pas te dire laquelle.
Je suis sérieux. Graham, Knuth, Patashnik (Concrete Mathematics) parlent de ton identité page 167 (section 5.1) et mentionnent dans la marge :
There's a nice combinatorial proof of this formula
Avec comme référence : Tamas Lengyel ``A combinatorial identity and the word series'', SIAM Review 35 (1993), 294-297
Je viens de trouver un lien sur un pdf. J'espère que cela fonctionne.
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=0643475149EE69FCC8EECE1737B2FDD1?doi=10.1.1.12.5&rep=rep1&type=pdf
A nice combinatorial proof : nice, quelle chance tu as.
Bon courage à toi.
- la liste des indices des $n$ premières composantes nulles $\rightarrow$ $\binom{k+n}{n}$ choix possibles,
- les valeurs de chacune des $n-k$ dernières composantes $\rightarrow$ $2^{n-k}$ choix possibles.
Finalement
Super. Je me doutais bien que j'apprendrais quelque chose. C'est un peu pour cela que je t'ai répondu (c'est pas bien) !
Je reformule la chose en terme de parties $E \subset \{0,1, \cdots, 2n\}$. Ton ensemble $\E$ est donc l'ensemble des parties de cardinal $\le n$ i.e. de cardinal $i$ avec $0 \le i \le n$. C'est la variable P ci-dessous (sorry pour le nom P).
Ensuite la fonction de nom UvDose qui associe à un $k$ vérifiant $0 \le k \le n$ la famille des $E$ de $\E$ vérifiant ta propriété. C.a.d.
$$
n+k \notin E, \qquad \#\big( \{0..n+k\} \cap \overline E\big) = n+1 \qquad\qquad
\hbox {$\overline E$ le complémentaire de $E$ dans $\{0,1, \cdots, 2n\}$}
$$
Peut-être qu'avec cette formulation (équivalente à la tienne), le dénombrement est un peu plus difficile.
Mais il fallait bien que je fasse joujou. Merci.
En fait, il n'est pas plus difficile de donner une interprétation combinatoire de l'égalité $(\natural)$ en utilisant exactement le même argument que pour $(\star)$. Je suis le conseil de Claude en raisonnant en termes de parties.
Preuve : si $A\in\mathcal{E}_{j,m}$, notons $Z(A)$ le $(j+1)$-ième élément dans la liste des éléments de $A$ classés par ordre croissant. On a $Z(A)=k+j$ avec $k\in[\![0;m-j]\!]$. Un élément $A$ de $\mathcal{E}_{j,m}$ tel que $Z(A)=k+j$ est caractérisé par :
- l'ensemble des $j$ éléments de $A$ strictement inférieurs à $k+j$ $\longrightarrow$ $\binom{k+j}{j}$ choix possibles,
- la donnée de $A\cap[\![j+k+1;m]\!]$ $\longrightarrow$ $2^{m-j-k}$ choix possibles.
D'où
$\hookrightarrow$ Revenons à l'égalité $(\natural)$. La bijection de $\mathcal{P}([\![0;p+q]\!])$ dans lui même, qui à $A$ associe son complémentaire dans $[\![0;p+q]\!]$, envoie $\mathcal{P}([\![0;p+q]\!])\backslash\mathcal{E}_{p,p+q}$ sur $\mathcal{E}_{q,p+q}$, donc