Interprétation combinatoire ?

uvdose

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.

claude quitté

Bonjour uvdose,
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.

uvdose

Chouette ! Merci Claude !

uvdose

Voilà finalement comment procéder : soit $\mathcal{E}$ (resp. $\mathcal{E}'$) l'ensemble des éléments de $\{0;1\}^{[\![0;2n]\!]}$ dont au moins $n+1$ composantes sont nulles (resp. non nulles). Il est clair que

$\{0;1\}^{[\![0;2n]\!]}=\mathcal{E}\sqcup\mathcal{E}'$ et $\text{Card}(\mathcal{E})=\text{Card}(\mathcal{E}')\;\;(\star)$

Si $u\in\mathcal{E}$, notons $Z(u)$ l'indice de la $(n+1)$-ième composante nulle de $u$ ; on a $Z(u)=k+n$ avec $k\in[\![0;n]\!]$. Un élément $u$ de $\mathcal{E}$ tel que $Z(u)=k+n$ est caractérisé par :
- 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

$\text{Card}(\mathcal{E})=\sum\limits_{k=0}^{n}\text{Card}\{u\in\mathcal{E}\,,\,Z(u)=n+k\}=\sum\limits_{k=0}^{n}\binom{k+n}{n}2^{n-k}$ ,

d'où, d'après $(\star)$ : $\sum\limits_{k=0}^{n}\binom{k+n}{n}2^{n-k}=2^{2n}$.

claude quitté

$\def\E{\mathcal E}$@uvdose
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\}$}
$$

> B := Binomial ;
> n := 5 ;                                                                         
> // Parties de {0..2*n} de cardinal <= n
> P := &join [Subsets({0..2*n},i) : i in [0..n]] ;                                 
> #P = 2^(2*n) ;
1024 = 1024
> 
> // Complementaire de E dans {0..2*n}
> C := func < E | {0..2*n} diff E > ;
> 
> // k in {0..n} --> {E : E in P tel que n+k notin E et {0..n+k} /\ C(E) est de cardinal n+1}
> UvDose := func < k | [E : E in P | n+k notin E and #({0..n+k} meet C(E)) eq n+1] > ;       
> 
> [#UvDose(k) : k in [0..n]] ;
[ 32, 96, 168, 224, 252, 252 ]
> [B(n+k,n)*2^(n-k) : k in [0..n]] ;                                                         
[ 32, 96, 168, 224, 252, 252 ]

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.

P.

(tu)

uvdose

En fait, je me suis posé la question initiale en tombant sur l'énoncé du Concours Général 1985 (voir ce fil ouvert par Chaurien pour obtenir le sujet), dans lequel on demandait de prouver l'égalité, valable pour $p\in\N$ et $q\in\N$ :

$\sum\limits_{k=0}^p\binom{k+q}{k}2^{p-k}+\sum\limits_{k=0}^q\binom{k+p}{k}2^{q-k}=2^{p+q+1}\;$ $\;(\natural)$

(La formule initiale correspond au cas où $p=q=n$.)

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.

Lemme a écrit:

Soient deux entiers $j$ et $m$ tels que $0\leqslant j\leqslant m$.
Le cardinal de l'ensemble $\mathcal{E}_{j,m}$ des parties de $[\![0;m]\!]$ qui contiennent au moins $j+1$ éléments est égal à $\sum\limits_{k=0}^{m-j}\binom{k+j}{j}2^{m-j-k}$.

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ù

$\text{Card}(\mathcal{E}_{j,m})=\sum\limits_{k=0}^{m-j}\text{Card}\{A\in\mathcal{E}_{j,m}\,,\,Z(A)=k+j\}=\sum\limits_{k=0}^{m-j}\binom{k+j}{j}2^{m-j-k}$.

$\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

$\text{Card}\left[\mathcal{P}([\![0;p+q]\!])\right]=\text{Card}\left(\mathcal{E}_{q,p+q}\right)+\text{Card}\left(\mathcal{E}_{p,p+q}\right)$

soit

$2^{p+q+1}=\sum\limits_{k=0}^p\binom{k+q}{k}2^{p-k}+\sum\limits_{k=0}^q\binom{k+p}{k}2^{q-k}$.

jandri

J'avais proposé une solution il y a dix mois dans ce fil.