Coefficient binomial de Gauss

En mathématiques, les coefficients binomiaux de Gauss ou coefficients q-binomiaux ou encore q-polynômes de Gauss sont des q -analogues des coefficients binomiaux, introduits par C. F. Gauss en 1808 ^[1].

Le coefficient q-binomial, écrit ${\displaystyle {\binom {n}{k}}_{q}}$ ou ${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}_{q}}$, est un polynôme en ${\displaystyle q}$ à coefficients entiers, qui donne, lorsque ${\displaystyle q}$ est une puissance de nombre premier, le nombre de sous-espaces vectoriels de dimension ${\displaystyle k}$ d'un espace vectoriel de dimension ${\displaystyle n}$ sur un corps fini à ${\displaystyle q}$ éléments.

Définition algébrique

Les coefficients binomiaux de Gauss sont définis pour ${\displaystyle n}$ et ${\displaystyle k}$ entiers naturels et ${\displaystyle q}$ différent de 1 par^[2] :

${\displaystyle {n \choose k}_{q}={\begin{cases}{\dfrac {(1-q^{n})(1-q^{n-1})\cdots (1-q^{n-k+1})}{(1-q)(1-q^{2})\cdots (1-q^{k})}}={\dfrac {(q^{n}-1)(q^{n}-q)(q^{n}-q^{2})\dots (q^{n}-q^{k-1})}{(q^{k}-1)(q^{k}-q)(q^{k}-q^{2})\dots (q^{k}-q^{k-1})}}&\ {\textrm {si}}\ k\leqslant n\\[4pt]0&\ {\textrm {si}}\ k>n\end{cases}}}$

Pour ${\displaystyle k=0}$, la valeur est 1 car le numérateur et le dénominateur sont tous deux des produits vides.

Bien que la première formule semble donner une fonction rationnelle en ${\displaystyle q}$, elle désigne en fait un polynôme en ${\displaystyle q}$ de degré ${\displaystyle k(n-k)}$ (la division est exacte dans ${\displaystyle \mathbb {Z} [q]}$).

Tous les facteurs au numérateur et au dénominateur sont divisibles par ${\displaystyle 1-q}$, avec comme quotient le q-analogue :

${\displaystyle [k]_{q}=\sum _{0\leq i<k}q^{i}=1+q+q^{2}+\cdots +q^{k-1}={\begin{cases}{\dfrac {1-q^{k}}{1-q}}&{\text{pour}}&q\neq 1\\[3pt]k&{\text{pour}}&q=1\end{cases}}}$.

La division de ces facteurs donne la formule équivalente :

${\displaystyle {n \choose k}_{q}={\frac {[n]_{q}[n-1]_{q}\cdots [n-k+1]_{q}}{[1]_{q}[2]_{q}\cdots [k]_{q}}}\quad (k\leqslant n)}$

ce qui met en évidence le fait que la substitution ${\displaystyle q=1}$ dans ${\textstyle {\binom {n}{k}}_{q}}$ donne le coefficient binomial ordinaire ${\textstyle {\binom {n}{k}}.}$

En termes de q-factorielles ${\displaystyle n!_{q}=[1]_{q}[2]_{q}\cdots [n]_{q}}$, la formule peut être écrite comme suit :

${\displaystyle {n \choose k}_{q}={\frac {n!_{q}}{k!_{q}\,(n-k)!_{q}}}\quad (k\leqslant n)}$,

forme compacte (souvent donnée comme première définition), qui cache cependant la présence de facteurs communs au numérateur et au dénominateur.

Cette forme rend évidente la symétrie ${\textstyle {\binom {n}{k}}_{q}={\binom {n}{n-k}}_{q}}$ pour ${\displaystyle k\leqslant n}$ .

Contrairement au coefficient binomial ordinaire, le coefficient binomial de Gauss a une limite finie quand ${\displaystyle n\rightarrow \infty }$, pour ${\displaystyle |q|<1}$ :

${\displaystyle {\infty \choose k}_{q}=\lim _{n\rightarrow \infty }{n \choose k}_{q}={\frac {1}{k!_{q}\,(1-q)^{k}}}={\frac {1}{(1-q)(1-q^{2})\cdots (1-q^{k})}}}$.

Exemples

${\displaystyle {0 \choose 0}_{q}={1 \choose 0}_{q}={1 \choose 1}_{q}={n \choose n}_{q}=1\;;}$

${\displaystyle {n \choose 1}_{q}={\frac {1-q^{n}}{1-q}}=1+q+\cdots +q^{n-1}\;;}$

${\displaystyle {3 \choose 2}_{q}={\frac {(1-q^{3})(1-q^{2})}{(1-q)(1-q^{2})}}=1+q+q^{2}\;;}$

${\displaystyle {4 \choose 2}_{q}={\frac {(1-q^{4})(1-q^{3})}{(1-q)(1-q^{2})}}=(1+q^{2})(1+q+q^{2})=1+q+2q^{2}+q^{3}+q^{4}\;;}$

${\displaystyle {6 \choose 2}_{q}={\frac {(1-q^{6})(1-q^{5})}{(1-q)(1-q^{2})}}=(1+q^{2}+q^{4})(1+q+q^{2}+q^{3}+q^{4})=1+q+2q^{2}+2q^{3}+3q^{4}+2q^{5}+2q^{6}+q^{7}+q^{8}\;;}$

${\displaystyle {2n \choose 2}_{q}={\frac {(1-q^{2n})(1-q^{2n-1})}{(1-q)(1-q^{2})}}=(1+q^{2}+q^{4}+\cdots +q^{2n-2})(1+q+q^{2}+\cdots +q^{2n-2})\;;}$

${\displaystyle {2n+1 \choose 2}_{q}={\frac {(1-q^{2n+1})(1-q^{2n})}{(1-q)(1-q^{2})}}=(1+q+q^{2}+\cdots +q^{2n})(1+q^{2}+\cdots +q^{2n-2}).}$

La plupart des logiciels de calcul formel ont des fonctions pour calculer les q-binomiaux, par exemple :

• q_binomial(n, k) dans SageMath ;
• QBinomial(n,k,q) dans Maple (avec le package QDifferenceEquations) ;
• QBinomial[n,k,q] dans Mathematica.

Relations de récurrence

Avec les définitions ci-dessus, on montre :

${\displaystyle {n \choose k}_{q}={\frac {1-q^{n}}{1-q^{k}}}{n-1 \choose k-1}_{q}={\frac {[n]_{q}}{[k]_{q}}}{n-1 \choose k-1}_{q}}$,

Cette égalité est la q-analogue de la formule du pion pour les coefficients binomiaux classiques.

Avec la formule ${\displaystyle {n \choose k}_{q}={\frac {1-q^{n}}{1-q^{n-k}}}{n-1 \choose k}_{q}}$, on déduit les relations q-analogues de la relation de Pascal :

${\displaystyle {n \choose k}_{q}=q^{k}{n-1 \choose k}_{q}+{n-1 \choose k-1}_{q}}$

et

${\displaystyle {n \choose k}_{q}={n-1 \choose k}_{q}+q^{n-k}{n-1 \choose k-1}_{q}}$.

Ces relations montrent, par récurrence, que les coefficients q-binomiaux sont bien des polynômes à coefficients entiers en ${\displaystyle q}$.

q-analogue du triangle de Pascal

Le triangle des coefficients binomiaux de Gauss, q-analogue du triangle de Pascal, se construit grâce aux relations précédentes :

${\displaystyle n=0}$									1
${\displaystyle n=1}$								1		1
${\displaystyle n=2}$							1		1+q		1
${\displaystyle n=3}$						1		1+q+q2		1+q+q2		1
${\displaystyle n=4}$					1		1+q+q2+q3		1+q+2q2+q3+q4		1+q+q2+q3		1

Pour q =2, il forme la suite A022166 de l'OEIS ; pour les entiers q suivants jusqu'à 24, les numéros des références se succèdent de 1 en 1 ; pour q=-2 : suite A015109 de l'OEIS et suivantes jusqu'à q=-24.

Autres références de l'OEIS concernant le q-triangle de Pascal :

• suite A008967 de l'OEIS et suite A219237 de l'OEIS donnant la succession des coefficients des polynômes des colonnes 2 et 4 : ${\displaystyle {\binom {n-2}{2}}_{q}}$ et ${\displaystyle {\binom {n+4}{4}}_{q}}$.
• suite A083906 de l'OEIS donnant les coefficients de la somme de chaque ligne.
• suite A089789 de l'OEIS donnant le nombre de facteurs irréductibles de ${\displaystyle {\binom {n}{k}}_{q}}$.

Définitions combinatoires

Nombre de combinaisons présentant un nombre d'inversions donné

Le coefficient binomial ordinaire ${\displaystyle {\tbinom {n}{k}}}$ compte les k-combinaisons obtenues à partir de ${\displaystyle n}$ éléments. Si l'on prend ces ${\displaystyle n}$ éléments comme les différentes positions de caractères dans un mot de longueur ${\displaystyle n}$, alors chaque k-combinaison correspond à un mot de longueur ${\displaystyle n}$ utilisant un alphabet de deux lettres, disons {0,1}, avec ${\displaystyle k}$ copies de la lettre 0 (indiquant les positions dans la combinaison choisie) et ${\displaystyle n-k}$ lettres 1 (pour les positions restantes).

Pour obtenir de ce modèle le coefficient binomial de Gauss ${\displaystyle {\tbinom {n}{k}}_{q}}$, il suffit de compter chaque mot avec un facteur ${\displaystyle q^{i}}$, où ${\displaystyle i}$ est le nombre d' "inversions" du mot : le nombre de paires de positions pour lesquelles la position la plus à gauche de la paire contient une lettre 1 et la position la plus à droite contient une lettre 0 dans le mot.

Par exemple, pour ${\displaystyle n=4,k=2}$, 0011 ne présente pas d'inversion, 0101 en présente une (en positions 2 et 3), 0110 et 1001 en présentent deux, 1010 en présente trois et 1100 en présente quatre. Cela correspond aux coefficients du polynôme en ${\displaystyle q}$ :

${\displaystyle {4 \choose 2}_{q}=1+q+2q^{2}+q^{3}+q^{4}.}$

D'une façon générale, si ${\displaystyle I(n,k,i)}$ est le nombre de mots binaires de ${\displaystyle n}$ lettres, contenant ${\displaystyle k}$ lettres 0, et présentant ${\displaystyle i}$ inversions, on a :

${\displaystyle {n \choose k}_{q}=\sum _{i=0}^{k(n-k)}I(n,k,i)q^{i}}$.

On démontre ceci à partir de la relation ${\displaystyle I(n,k,i)=I(n-1,k-1,i)+I(n-1,k,i-k)}$.

Une façon visuelle de comprendre cette définition consiste à associer à chaque mot un chemin à travers une grille rectangulaire de côtés de hauteur ${\displaystyle k}$ et de largeur ${\displaystyle n}$, du coin inférieur gauche au coin supérieur droit, en faisant un pas à droite pour chaque lettre 0 et un pas vers le haut pour chaque lettre 1. Le nombre d'inversions du mot est alors égal à l'aire de la partie du rectangle qui se trouve sous le chemin.

Dénombrements de rangements de boules dans des urnes ou de partitions d'entiers

Soit ${\displaystyle B(n,m,i)}$ le nombre de façons de lancer ${\displaystyle i}$ boules dans ${\displaystyle n}$ urnes indiscernables pouvant contenir ${\displaystyle m}$ boules au plus, ${\displaystyle i\leqslant nm}$.

Pour ${\displaystyle i\geqslant 1}$, ${\displaystyle B(n,m,i)}$ est donc aussi le nombre de partitions de l'entier ${\displaystyle i}$ en ${\displaystyle n}$ parties au plus, chacune des parties étant inférieure ou égale à ${\displaystyle m}$.

On montre qu'avec les notations précédentes, ${\displaystyle B(n,m,i)=I(n+m,n,i)}$.

Donc ${\displaystyle B(n,m,i)=[q^{i}]{n+m \choose n}_{q}}$ où ${\displaystyle [q^{i}]P}$ désigne le coefficient de ${\displaystyle q^{i}}$ dans le polynôme ${\displaystyle P}$.

Notons que par symétrie, ${\displaystyle B(n,m,i)=B(m,n,i)}$.

Nombre de sous-espaces vectoriels d'un espace vectoriel fini

Lorsque ${\displaystyle q}$ est une puissance de nombre premier, le nombre de sous-espaces vectoriels de dimension ${\displaystyle k}$ d'un espace vectoriel de dimension ${\displaystyle n}$ sur un corps fini à ${\displaystyle q}$ éléments est ${\displaystyle {n \choose k}_{q}}$^[3].

Donc le nombre de sous-espaces projectifs de dimension ${\displaystyle k}$ d'un espace projectif de dimension ${\displaystyle n}$ sur un corps fini à ${\displaystyle q}$ éléments est ${\displaystyle {n+1 \choose k+1}_{q}}$.

Parties à k éléments de {1,2,..,n}

Posons ${\displaystyle E_{n}=\{1,2,..,n\}}$ et pour une partie ${\displaystyle X}$, notons ${\displaystyle \Sigma (X)}$ sa somme ; alors^[4]:

${\displaystyle {\binom {n}{k}}_{q}=\sum _{\begin{matrix}X\subset E_{n}\\|X|=k\end{matrix}}{q^{\Sigma (X)-\Sigma (E_{k})}}}$.

q-analogue de la formule du binôme

Pour a et b réels ou complexes, on montre la formule q-analogue de la formule du binôme :

${\displaystyle \prod _{k=0}^{n-1}(a+q^{k}b)=\sum _{k=0}^{n}q^{k(k-1)/2}{n \choose k}_{q}a^{n-k}b^{k}}$, dénommée « formule du binôme de Gauss »^[4] .

On en déduit, pour ${\displaystyle |q|<1}$, le développement du produit infini  : ${\displaystyle \prod _{n=0}^{\infty }(1+q^{n}x)=1+\sum _{n=1}^{\infty }{\frac {q^{n(n-1)/2}}{(1-q)(1-q^{2})\cdots (1-q^{n})}}x^{n}}$ (première identité d'Euler).

Par exemple, pour ${\displaystyle q=1/2}$, ${\displaystyle x=1}$, on obtient ${\displaystyle \prod _{n=0}^{\infty }(1+{1 \over {2^{n}}})=1+\sum _{n=1}^{\infty }{\frac {2^{n}}{(2-1)(2^{2}-1)\cdots (2^{n}-1)}}}$, voir suite A081845 de l'OEIS.

Il existe aussi une formule q-analogue de la formule du binôme négatif, dénommée « formule du binôme de Heine »^[4] :

${\displaystyle \prod _{k=0}^{n-1}{\frac {1}{1-q^{k}x}}=\sum _{k=0}^{\infty }{n+k-1 \choose k}_{q}x^{k}}$ pour ${\displaystyle |x|<1}$.

dont on déduit :

${\displaystyle \prod _{n=0}^{\infty }{\frac {1}{1-q^{n}x}}=1+\sum _{n=1}^{\infty }{\frac {x^{n}}{(1-q)(1-q^{2})\cdots (1-q^{n})}}}$ pour ${\displaystyle |x|<1}$ et ${\displaystyle |q|<1}$ (deuxième identité d'Euler).

Par exemple, pour ${\displaystyle q=x=1/2}$, on obtient ${\displaystyle {\prod _{n=0}^{\infty }{\frac {1}{1-{1 \over {2^{n+1}}}}}}=1+\sum _{n=1}^{\infty }{\frac {2^{n(n-1)/2}}{(2-1)(2^{2}-1)\cdots (2^{n}-1)}}}$, voir suite A065446 de l'OEIS.

Autres relations entre coefficients q-binomiaux

q-analogue de la sommation en colonne

Par application du q-analogue de relation de Pascal, on obtient le q-analogue de la formule d'itération de Pascal^[1] :

${\displaystyle \sum _{i=p}^{n}q^{i-p}{\binom {i}{k}}_{q}={\binom {n+1}{k+1}}_{q}}$

q-analogue de l'identité de Vandermonde

Le q-analogue de l'identité de Vandermonde est^[4]

${\displaystyle {\binom {m+n}{k}}_{\!\!q}=\sum _{j}{\binom {m}{k-j}}_{\!\!q}{\binom {n}{j}}_{\!\!q}q^{j(m-k+j)}}$.

Sommation alternée d'une ligne

Pour une ligne paire^[1] :

${\displaystyle \sum _{k=0}^{2n}(-1)^{k}{\binom {2n}{k}}_{q}=(1-q)(1-q^{3})\cdots (1-q^{2n-1}).}$

Pour une ligne impaire (évident par la propriété de symétrie)^[1] :

${\displaystyle \sum _{k=0}^{2n+1}(-1)^{k}{\binom {2n+1}{k}}_{q}=0.}$

Étoile de David

D'après leur définition algébrique, les coefficients binomiaux de Gauss vérifient le théorème de l'étoile de David, deuxième énoncé.

Voir aussi

• q-analogue
• q-symbole de Pochhammer
• Espaces vectoriels finis
• Coefficients fibonomiaux

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Gaussian binomial coefficient » (voir la liste des auteurs).

• Portail des mathématiques