# 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 (n/k)$_q${\textstyle {\binom {n}{k}}_{q}} donne le coefficient binomial ordinaire (n/k).{\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 (n/k)$_q$=(n/n−k)$_q${\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+\cdots +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}+\cdots +q^{2n-2})(1+q+q^{2}+\cdots +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}+\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 :
    ${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 | 1 | | | | |
| $n=1$ | | | | 1 | 1 | 1 | 1 | | | |
| $n=2$ | | | 1 | 1 | 1+q | 1+q | 1 | 1 | | |
| $n=3$ | | 1 | 1 | 1+q+q$^2$ | 1+q+q$^2$ | 1+q+q$^2$ | 1+q+q$^2$ | 1 | 1 | |
| $n=4$ | 1 | 1 | 1+q+q$^2$+q$^3$ | 1+q+q$^2$+q$^3$ | 1+q+2q$^2$+q$^3$+q$^4$ | 1+q+2q$^2$+q$^3$+q$^4$ | 1+q+q$^2$+q$^3$ | 1+q+q$^2$+q$^3$ | 1 | 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}.$
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})\cdots (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é.