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

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

{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+q²		1+q+q²		1
$n=4$	1		1+q+q²+q³		1+q+2q²+q³+q⁴		1+q+q²+q³		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}$ [3].

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[4]:

{\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" [4] .

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" [4] :

\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

|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[1] :

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

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

\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)[1] :

\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

Références

(la) C. F. Gauss, Opera, Vol. 2, Summatio quarumdam serierum singularium, 1808 (lire en ligne), p. 7–12, paragraphes 5 à 9
(en) George Pólya et Gábor Szegő, Problems and Theorems in Analysis, vol. I, Springer, 1997 (1^re éd. 1972) (lire en ligne), p. 11 à 13
(en) M. Sved, « ,Gaussians and binomials », Ars Combinatoria, 17A,‎ 1984, p. 325-351. (lire en ligne)
(en) Victor Kac et Pokman Cheung, Quantum Calculus, Springer, 2002 (lire en ligne), chapitre 5, th. 7.6, th. 6.1

(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).

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.