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 .

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

Définition algébrique

Les coefficients binomiaux de Gauss sont définis pour $n$ et $k$ entiers naturels et $q$ différent de 1 par :

${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 $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 $q$, elle désigne en fait un polynôme en $q$ de degré $k(n-k)$ (la division est exacte dans $\mathbb {Z} [q]$).

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

$[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 :

${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 $q=1$ dans ${\textstyle {\binom {n}{k}}_{q}}$ donne le coefficient binomial ordinaire ${\textstyle {\binom {n}{k}}.}$

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

${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 $k\leqslant n$ .

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

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

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

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

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

${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}$

${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}$${2n \choose 2}_{q}={\frac {(1-q^{2n})(1-q^{2n-1})}{(1-q)(1-q^{2})}}=(1+q^{2}+q^{4}+...+q^{2n-2})(1+q+q^{2}+...+q^{2n-2})$${2n+1 \choose 2}_{q}={\frac {(1-q^{2n+1})(1-q^{2n})}{(1-q)(1-q^{2})}}=(1+q+q^{2}+...+q^{2n})(1+q^{2}+...+q^{2n-2})$

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

• 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 :

${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 ${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 :

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

et

${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 $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 :

$n=0$									1
$n=1$								1		1
$n=2$							1		1+q		1
$n=3$						1		1+q+q2		1+q+q2		1
$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 : ${\binom {n-2}{2}}_{q}$ et ${\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 ${\binom {n}{k}}_{q}$.

Définitions combinatoires

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

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

Pour obtenir de ce modèle le coefficient binomial de Gauss ${\tbinom {n}{k}}_{q}$, il suffit de compter chaque mot avec un facteur $q^{i}$, où $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 $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 $q$ :

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

Chemin correspondant au mot 011100010010 ; ici, n = 12, k = 7, et le nombre d'inversions, aire sous le chemin, vaut i = 22.

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

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

On démontre ceci à partir de la relation $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 $k$ et de largeur $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 $B(n,m,i)$ le nombre de façons de lancer $i$ boules dans $n$ urnes indiscernables pouvant contenir $m$ boules au plus, $i\leqslant nm$.

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

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

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

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

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

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

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

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

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

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

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

On en déduit, pour $|q|<1$, le développement du produit infini  : $\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 $q=1/2$, $x=1$, on obtient $\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"  :

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

dont on déduit :

$\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 $|x|<1$ et $|q|<1$ (deuxième identité d'Euler).

Par exemple, pour $q=x=1/2$, on obtient ${\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 :

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

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

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

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

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