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{matrix} n \\ k \end{matrix}]}_{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] :

{(\binom{n}{k})}_{q} = {\begin{matrix} \frac{(1 - q^{n}) (1 - q^{n - 1}) \dots (1 - q^{n - k + 1})}{(1 - q) (1 - q^{2}) \dots (1 - q^{k})} = \frac{(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})} & si k ⩽ n \\ 0 & si k > n \end{matrix}

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 $ℤ [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} + \dots + q^{k - 1} = {\begin{matrix} \frac{1 - q^{k}}{1 - q} & pour & q \neq 1 \\ k & pour & q = 1 \end{matrix}

.

La division de ces facteurs donne la formule équivalente :

{(\binom{n}{k})}_{q} = \frac{[n]_{q} [n - 1]_{q} \dots [n - k + 1]_{q}}{[1]_{q} [2]_{q} \dots [k]_{q}} (k ⩽ n)

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

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

{(\binom{n}{k})}_{q} = \frac{n!_{q}}{k!_{q} (n - k)!_{q}} (k ⩽ 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 ${(\binom{n}{k})}_{q} = {(\binom{n}{n - k})}_{q}$ pour $k ⩽ n$ .

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

{(\binom{\infty}{k})}_{q} = \lim_{n \to \infty} {(\binom{n}{k})}_{q} = \frac{1}{k!_{q} (1 - q)^{k}} = \frac{1}{(1 - q) (1 - q^{2}) \dots (1 - q^{k})}

.

Exemples

{(\binom{0}{0})}_{q} = {(\binom{1}{0})}_{q} = {(\binom{1}{1})}_{q} = {(\binom{n}{n})}_{q} = 1;

{(\binom{n}{1})}_{q} = \frac{1 - q^{n}}{1 - q} = 1 + q + \dots + q^{n - 1};

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

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

{(\binom{6}{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 + 2 q^{2} + 2 q^{3} + 3 q^{4} + 2 q^{5} + 2 q^{6} + q^{7} + q^{8};

{(\binom{2 n}{2})}_{q} = \frac{(1 - q^{2 n}) (1 - q^{2 n - 1})}{(1 - q) (1 - q^{2})} = (1 + q^{2} + q^{4} + \dots + q^{2 n - 2}) (1 + q + q^{2} + \dots + q^{2 n - 2});

{(\binom{2 n + 1}{2})}_{q} = \frac{(1 - q^{2 n + 1}) (1 - q^{2 n})}{(1 - q) (1 - q^{2})} = (1 + q + q^{2} + \dots + q^{2 n}) (1 + q^{2} + \dots + q^{2 n - 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 :

{(\binom{n}{k})}_{q} = \frac{1 - q^{n}}{1 - q^{k}} {(\binom{n - 1}{k - 1})}_{q} = \frac{[n]_{q}}{[k]_{q}} {(\binom{n - 1}{k - 1})}_{q}

,

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

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

{(\binom{n}{k})}_{q} = q^{k} {(\binom{n - 1}{k})}_{q} + {(\binom{n - 1}{k - 1})}_{q}

et

{(\binom{n}{k})}_{q} = {(\binom{n - 1}{k})}_{q} + q^{n - k} {(\binom{n - 1}{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+qModèle:2		1+q+qModèle:2		1
$n = 4$	1		1+q+qModèle:2+q³		1+q+2qModèle:2+q³+q⁴		1+q+qModèle:2+q³		1

Pour q =2, il forme la Modèle: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 : Modèle:OEIS et suivantes jusqu'à q=-24.

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

Modèle:OEIS et Modèle: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}$ .
Modèle:OEIS donnant les coefficients de la somme de chaque ligne.
Modèle: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 $(\binom{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 Modèle:Formule 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 ${(\binom{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$ :

{(\binom{4}{2})}_{q} = 1 + q + 2 q^{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 :

{(\binom{n}{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 ⩽ n m$ .

Pour $i ⩾ 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}] {(\binom{n + m}{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

Modèle:Article détaillé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 ${(\binom{n}{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 ${(\binom{n + 1}{k + 1})}_{q}$ .

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

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

{(\binom{n}{k})}_{q} = \sum_{\begin{matrix} X \subset E_{n} \\ | X | = k \end{matrix}} q^{Σ (X) - Σ (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} {(\binom{n}{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}) \dots (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 + \frac{1}{2^{n}}) = 1 + \sum_{n = 1}^{\infty} \frac{2^{n}}{(2 - 1) (2^{2} - 1) \dots (2^{n} - 1)}$ , voir Modèle: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} {(\binom{n + k - 1}{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}) \dots (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 - \frac{1}{2^{n + 1}}} = 1 + \sum_{n = 1}^{\infty} \frac{2^{n (n - 1) / 2}}{(2 - 1) (2^{2} - 1) \dots (2^{n} - 1)}$ , voir Modèle: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

Modèle:Article détaillé Modèle:Ancre 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}^{2 n} (- 1)^{k} {(\binom{2 n}{k})}_{q} = (1 - q) (1 - q^{3}) \dots (1 - q^{2 n - 1}) .

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

\sum_{k = 0}^{2 n + 1} (- 1)^{k} {(\binom{2 n + 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

Modèle:Traduction/Référence

Modèle:Portail

[:0-1] 1,0 ^1,1 ^1,2 et ^1,3 Modèle:Ouvrage

[2] Modèle:Ouvrage à 13

[3] Modèle:Article

[:1-4] 4,0 ^4,1 ^4,2 et ^4,3 Modèle:Ouvrage

[1]

[2]

[3]

[4]

Coefficient binomial de Gauss

Sommaire

Définition algébrique

Exemples

Relations de récurrence

q-analogue du triangle de Pascal

Définitions combinatoires

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

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

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

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

q-analogue de la formule du binôme

Autres relations entre coefficients q-binomiaux

q-analogue de la sommation en colonne

q-analogue de l'identité de Vandermonde

Sommation alternée d'une ligne

Étoile de David

Voir aussi

Références

Menu de navigation

Coefficient binomial de Gauss

Définition algébrique

Exemples

Relations de récurrence

q-analogue du triangle de Pascal

Définitions combinatoires

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

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

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

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

q-analogue de la formule du binôme

Autres relations entre coefficients q-binomiaux

q-analogue de la sommation en colonne

q-analogue de l'identité de Vandermonde

Sommation alternée d'une ligne

Étoile de David

Voir aussi

Références

Menu de navigation

Rechercher