Coefficiente binomiale gaussiano

In matematica, il coefficiente binomiale gaussiano (noto anche come coefficiente gaussiano o coefficiente ${\displaystyle q}$-binomiale) è un ${\displaystyle q}$-analogo del coefficiente binomiale. Viene denotato con ${\displaystyle {\binom {n}{k}}_{q}}$, oppure con ${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}_{q}}$, ed è un polinomio in ${\displaystyle q}$ a coefficienti interi il cui valore, quando ${\displaystyle q}$ è una potenza di un numero primo, corrisponde al numero di sottospazi di dimensione ${\displaystyle k}$ in uno spazio vettoriale di dimensione ${\displaystyle n}$ su ${\displaystyle \mathbb {F} _{q}}$, un campo finito con ${\displaystyle q}$ elementi; equivalentemente, è il numero di punti nella grassmanniana ${\displaystyle \mathrm {Gr} (k,\mathbb {F} _{q}^{n})}$.

Il coefficiente binomiale gaussiano è definito nel seguente modo:^[1]

${\displaystyle {m \choose r}_{q}={\frac {(1-q^{m})(1-q^{m-1})\cdots (1-q^{m-r+1})}{(1-q)(1-q^{2})\cdots (1-q^{r})}}}$,

dove ${\displaystyle m}$ e ${\displaystyle r}$ sono due interi non negativi; analogamente al coefficiente binomiale, se ${\displaystyle r>m}$ si ottiene 0, mentre se ${\displaystyle r=0}$ il valore è 1 in quanto sia il numeratore che il denominatore sono prodotti vuoti. Sebbene questa formula possa sembrare una funzione razionale, in realtà essa rappresenta un polinomio, poiché la divisione è esatta in ${\displaystyle \mathbb {Z} [q]}$.

Tutti i fattori del numeratore e del denominatore sono divisibili per ${\displaystyle 1-q}$: eseguendo queste divisioni si ottiene

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

Possiamo in tal modo ottenere la formula equivalente

${\displaystyle {m \choose r}_{q}={\frac {[m]_{q}[m-1]_{q}\cdots [m-r+1]_{q}}{[1]_{q}[2]_{q}\cdots [r]_{q}}}\quad (r\leq m).}$

Si può infine osservare che, sostituendo ${\displaystyle q}$=1 in ${\displaystyle {\tbinom {m}{r}}_{q}}$, si ottiene il coefficiente binomiale ordinario ${\displaystyle {\tbinom {m}{r}}}$.

Analogamente al coefficiente binomiale ordinario, il coefficiente binomiale gaussiano è invariante rispetto alla mappa ${\displaystyle r\rightarrow m-r}$:

${\displaystyle {m \choose r}_{q}={m \choose m-r}_{q}.}$

In particolare,

${\displaystyle {m \choose 0}_{q}={m \choose m}_{q}=1\,,}$

${\displaystyle {m \choose 1}_{q}={m \choose m-1}_{q}={\frac {1-q^{m}}{1-q}}=1+q+\cdots +q^{m-1}\quad m\geq 1\,.}$

Valutando il coefficiente binomiale gaussiano in q = 1 si ottiene

${\displaystyle \lim _{q\to 1}{\binom {m}{r}}_{q}={\binom {m}{r}}}$

cioè la somma dei coefficienti restituisce il corrispondente valore del coefficiente binomiale.

Il grado di ${\displaystyle {\binom {m}{r}}_{q}}$ è ${\displaystyle {\binom {m+1}{2}}-{\binom {r+1}{2}}-{\binom {(m-r)+1}{2}}=r(m-r)}$.

Per i coefficienti binomiali gaussiani valgono le seguenti identità

${\displaystyle {m \choose r}_{q}=q^{r}{m-1 \choose r}_{q}+{m-1 \choose r-1}_{q}}$

e

${\displaystyle {m \choose r}_{q}={m-1 \choose r}_{q}+q^{m-r}{m-1 \choose r-1}_{q}}$.

Entrambe possono essere ricondotte all'altrettanto nota identità relativa ai coefficienti binomiali

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

imponendo ${\displaystyle q=1}$.

Entrambe le identità possono essere dimostrate osservando che, dalla definizione di ${\displaystyle {\tbinom {m}{r}}_{q}}$, si ha:

1. ${\displaystyle {\binom {m}{r}}_{q}={\frac {1-q^{m}}{1-q^{m-r}}}{\binom {m-1}{r}}_{q}}$
2. ${\displaystyle {\binom {m}{r}}_{q}={\frac {1-q^{m}}{1-q^{r}}}{\binom {m-1}{r-1}}_{q}}$
3. ${\displaystyle {\frac {1-q^{r}}{1-q^{m-r}}}{\binom {m-1}{r}}_{q}={\binom {m-1}{r-1}}_{q}}$

Poiché

${\displaystyle {\frac {1-q^{m}}{1-q^{m-r}}}={\frac {1-q^{r}+q^{r}-q^{m}}{1-q^{m-r}}}=q^{r}+{\frac {1-q^{r}}{1-q^{m-r}}}}$,

l'equazione 1. diventa

${\displaystyle {\binom {m}{r}}_{q}=q^{r}{\binom {m-1}{r}}_{q}+{\frac {1-q^{r}}{1-q^{m-r}}}{\binom {m-1}{r}}_{q}}$

ed utilizzando l'equazione 3. si ottiene la prima delle due identità.

Un ragionamento simile, utilizzando l'uguaglianza

${\displaystyle {\frac {1-q^{m}}{1-q^{r}}}=q^{m-r}+{\frac {1-q^{m-r}}{1-q^{r}}}}$,

permette di giungere alla seconda identità.

Esiste anche un analogo del teorema binomiale per i coefficienti binomiali gaussiani, noto come teorema binomiale di Cauchy:

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

Allo stesso modo del teorema binomiale, questa formula ha numerose generalizzazioni ed estensioni: una di esse, ad esempio, corrisponde al teorema binomiale generalizzato di Newton per potenze negative

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

Con i coefficienti binomiali ordinari vale la seguente identità:

${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}}$.

L'analogo nel caso dei coefficienti binomiali gaussiani è:

${\displaystyle \sum _{k=0}^{n}q^{k^{2}}{\binom {n}{k}}_{q}^{2}={\binom {2n}{n}}_{q}}$.

Originariamente Gauss utilizzò questi coefficienti per determinare il segno della somma quadratica di Gauss.^[2]

La principale applicazione dei coefficienti binomiali gaussiani avviene nella teoria enumerativa degli spazi proiettivi definiti su un campo finito: per ogni campo finito ${\displaystyle \mathbb {F} _{q}}$ con ${\displaystyle q}$ elementi, il coefficiente binomiale gaussiano

${\displaystyle {n \choose k}_{q}}$

determina il numero di sottospazi vettoriali ${\displaystyle k}$-dimensionali all'interno di uno spazio vettoriale ${\displaystyle n}$-dimensionale su ${\displaystyle \mathbb {F} _{q}}$ (una grassmanniana). Quando viene espanso come polinomio in ${\displaystyle q}$, restituisce la decomposizione della grassmanniana in celle di Schubert.

Il numero di sottospazi affini ${\displaystyle k}$-dimensionali di ${\displaystyle \mathbb {F} _{q}^{n}}$ è invece uguale a

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

Se si denota con ${\displaystyle B(n,m,r)}$ il numero di possibili modi di lanciare ${\displaystyle r}$ palline indistinguibili in ${\displaystyle m}$ urne indistinguibili, ciascuna delle quali può contenere al massimo ${\displaystyle n}$ palline, il coefficiente binomiale gaussiano può essere utilizzato per caratterizzare questo valore: infatti,

${\displaystyle B(n,m,r)=[q^{r}]{n+m \choose m}_{q}}$,

dove ${\displaystyle [q^{r}]P}$ denota il coefficiente del termine ${\displaystyle q^{r}}$ nel polinomio ${\displaystyle P}$.

• Eugene Mukhin, Symmetric Polynomials and Partitions (PDF), su mathcircle.berkeley.edu (archiviato dall'url originale il 4 marzo 2016). (undated, 2004 or earlier).
• (EN) Eric W. Weisstein, Coefficiente binomiale gaussiano, in MathWorld, Wolfram Research.
• John Konvalina, Generalized binomial coefficients and the subset-subspace problem, in Adv. Appl. Math., vol. 21, n. 2, 1998, pp. 228–240, DOI:10.1006/aama.1998.0598, MR 1634713.
• John Konvalina, A unified interpretation of the Binomial Coefficients, the Stirling numbers, and the Gaussian coefficients, in Amer. Math. Monthly, vol. 107, n. 10, 2000, pp. 901–910, DOI:10.2307/2695583, JSTOR 2695583, MR 1806919.
• Boris A. Kupershmidt, q-Newton binomial: from Euler to Gauss, in J. Nonlinear Math. Phys., vol. 7, n. 2, 2000, pp. 244–262, Bibcode:2000JNMP....7..244K, DOI:10.2991/jnmp.2000.7.2.11, MR 1763640, arXiv:math/0004187.

• Coefficiente binomiale
• Teorema binomiale
• Calcolo combinatorio
• Spazio proiettivo

V · D · M Combinatoria
Orientamento generale	Combinatoria · Storia della combinatoria · Matematica discreta · Sezione 05-XX di MSC
Nozioni introduttive	Permutazioni · Disposizioni · Combinazioni · Coefficienti binomiali · Partizioni di interi · Partizioni di insiemi finiti - Identità combinatorie e biiezioni · Principio dei cassetti
Configurazioni	Quadrati latini · Quadrati magici · Disegni a blocchi · Geometrie finite · Matroidi - Tassellazioni · Polimini
Teoria dei grafi	Alberi · Cammini sui grafi (euleriani, hamiltoniani) · Connessione nei grafi - Grafi planari · Colorazione dei grafi e teorema dei quattro colori) · Ipergrafi · Grafi e gruppi · Digrafo · Flussi su grafi · Passeggiate aleatorie su grafi · Omomorfismo fra grafi · Algoritmi sui grafi
Combinatoria algebrica	Tavola di Young · Funzioni simmetriche - Serie formale di potenze · Funzioni generatrici · Polinomi ortogonali · Azioni di un gruppo su strutture combinatorie - Aspetti combinatorici dell'algebra commutativa
Altre aree	Calcolo umbrale (sequenze polinomiali di tipo binomiale · sequenze di Sheffer) - Combinatoria estremale

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica