Gaussiska binomialkoefficienter

Gaussiska binomialkoefficienter (och även Gaussiska koefficienter , Gausspolynom eller q -binomialkoefficienter ) är q -analogerna av binomialkoefficienter . Den gaussiska binomialkoefficienten är ett polynom i q med heltalskoefficienter vars värde, givet q som en potens av ett primtal, räknar antalet delrum av dimensionen k i ett n -dimensionellt vektorrum över ett ändligt fält med q element. $\textstyle {\binom {n}{k}}_{q}$

Definition

Gaussiska binomialkoefficienter definieras enligt följande [1]

{m \choose r}_{q}={\begin{cases}{\frac {(1-q^{m})(1-q^{m-1})\cdots (1-q ^{m-r+1})}{(1-q)(1-q^{2})\cdots (1-q^{r})}}&r\leqslant m\\0&r>m\end{ fall}}

där m och r är icke-negativa heltal.

I Smirnovs artikel [2] och Vasilievs bok används fyrkantiga parenteser istället för runda parentes:

\left[{\begin{array}{c}m\\r\\\end{array}}\right]_{q}

För , värdet är 1 eftersom täljaren och nämnaren är de tomma produkterna av . Även om formeln i det första uttrycket är en rationell funktion definierar den faktiskt ett polynom. Observera att formeln kan tillämpas på , vilket ger 0 på grund av faktorn i täljaren enligt det andra uttrycket (för alla större r , är faktorn 0 närvarande i täljaren, men ytterligare faktorer kommer att ha negativa potenser av q , så det explicita andra uttrycket är att föredra). Alla faktorer i täljaren och nämnaren är delbara med 1 − q med en kvot i form av ett q -tal [3] : $r=0$ $r=m+1$ $1-q^{0}=0$

[k]_{q}={\frac {1-q^{k}}{1-q}}=\summa _{0\leqslant i<k}q^{i}=1+q +q^{2}+\cdots +q^{k-1};

Detta ger motsvarande formel

{m \choose r}_{q}={\frac {[m]_{q}[m-1]_{q}\cdots [m-r+1]_{q}}{[ 1]_{q}[2]_{q}\cdots [r]_{q}}}\quad (r\leqslant m),

vilket gör det uppenbart att substitution i ger den vanliga binomialkoefficienten . När det gäller q -faktorn kan formeln skrivas om som $q=1$ ${\tbinom {m}{r}}_{q}$ ${\tbinom {m}{r))$ ${\displaystyle [n]_{q}!=[1]_{q}[2]_{q}\cdots [n]_{q))$

{m \choose r}_{q}={\frac {[m]_{q}!}{[r]_{q}!\,[mr]_{q}!}}\quad (r\leqslant m)

Denna kompakta form (ofta given som definition) döljer dock förekomsten av många gemensamma faktorer i täljaren och nämnaren. Denna vy gör symmetri för . ${\tbinom {m}{r}}_{q}={\tbinom {m}{mr}}_{q}$ $r\leqslant m$

Till skillnad från den vanliga binomialkoefficienten har den Gaussiska binomialkoefficienten ändliga värden för (gränsen har en analytisk betydelse för ): $m\rightarrow \infty$ $|q|<1$

{\infty \choose r}_{q}=\lim _{m\rightarrow \infty }{m \choose r}_{q}={\frac {1}{[r]_{q} !\,(1-q)^{r}}}

Exempel

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

{1 \choose 1}_{q}={\frac {1-q}{1-q}}=1

{2 \choose 1}_{q}={\frac {1-q^{2}}{1-q}}=1+q

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

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

Kombinatorisk beskrivning

Istället för dessa algebraiska uttryck kan man också ge en kombinatorisk definition av gaussiska binomialkoefficienter. Den vanliga binomialkoefficienten räknar r - kombinationer valda från en mängd med m element. Om man fördelar de m elementen som distinkta tecken i ett ord med längden m , så motsvarar varje r -kombination ett ord med längden m , sammansatt av ett alfabet med två bokstäver, säg {0,1}, med r kopior av bokstav 1 (som indikerar att bokstaven är vald) och med m − r kopior av bokstaven 0 (för de återstående positionerna). ${\tbinom {m}{r))$

Ord som använder nollor och ettor är 0011, 0101, 0110, 1001, 1010, 1100. ${4 \choose 2}=6$

För att få en Gaussisk binomialkoefficient från denna modell räcker det att räkna varje ord med en faktor q d , där d är lika med antalet "inversioner" i ordet - antalet par av positioner för vilka den vänstra positionen av paret är 1 och den högra positionen innehåller 0 i ordet. Till exempel finns det ett ord med 0 inversioner, 0011. Det finns ett ord med en inversion, 0101. Det finns två ord med två inversioner, 0110 och 1001. Det finns ett ord med tre inversioner, 1010, och slutligen ett ord med fyra inversioner, 1100. Detta motsvarar koefficienterna i . ${\tbinom {m}{r}}_{q}$ ${\displaystyle {4 \choose 2}_{q}=1+q+2q^{2}+q^{3}+q^{4))$

Det kan visas att de sålunda definierade polynomen uppfyller Pascal-identiteterna nedan och därför sammanfaller med polynomen som definieras algebraiskt. Ett visuellt sätt att se denna definition är att tilldela varje ord en väg genom ett rektangulärt gitter med höjd r och bredd m − r från det nedre vänstra hörnet till det övre högra hörnet, med ett steg till höger för bokstaven 0 och ett steg upp för bokstaven 1. Sedan antalet inversioner i ordet lika med arean av delen av rektangeln under banan.

Egenskaper

Liksom vanliga binomialkoefficienter är Gaussiska binomialkoefficienter kontrasymmetriska, d.v.s. är oföränderliga under reflektion : $r\rightarrow mr$

{m \choose r}_{q}={m \choose mr}_{q}.

Särskilt,

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

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

Namnet på den Gaussiska binomialkoefficienten förklaras av det faktum att dess värde vid en punkt är lika med $q=1$

{\displaystyle \lim _{q\to 1}{m \choose r}_{q}={m \choose r))

För alla m och r .

Analoger av Pascals identiteter för Gaussiska binomialkoefficienter

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

och

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

Det finns analoger till binomialformler och generaliserade newtonska versioner av dem för negativa heltalspotenser, även om de Gaussiska binomialkoefficienterna i det första fallet inte visas som koefficienter [4] :

\prod _{k=0}^{n-1}(1+q^{k}t)=\summa _{k=0}^{n}q^{k(k-1)/ 2}{n \välj k}_{q}t^{k}

och

\prod _{k=0}^{n-1}{\frac {1}{(1-q^{k}t)))=\summa _{k=0}^{\infty } {n+k-1 \välj k}_{q}t^{k}.

och vid , identiteterna förvandlas till $n\högerpil\infty$

\prod _{k=0}^{\infty }(1+q^{k}t)=\summa _{k=0}^{\infty }{\frac {q^{k(k) -1)/2}t^{k}}{[k]_{q}!\,(1-q)^{k}}}

och

\prod _{k=0}^{\infty }{\frac {1}{(1-q^{k}t)))=\sum _{k=0}^{\infty }{ \frac {t^{k}}{[k]_{q}!\,(1-q)^{k}}}.

Pascals första identitet gör det möjligt att beräkna de Gaussiska binomialkoefficienterna rekursivt (med avseende på m ) med hjälp av initiala "gränsvärden"

{m \choose m}_{q}={m \choose 0}_{q}=1

Och visar förresten att de Gaussiska binomialkoefficienterna verkligen är polynom (i q ). Pascals andra identitet följer från den första genom substitution och invariansen av Gaussiska binomialkoefficienter med avseende på reflektion . Av Pascals identiteter följer $r\rightarrow mr$ $r\rightarrow mr$

{m \choose r}_{q}={{1-q^{m}} \över {1-q^{mr}}}{m-1 \choose r}_{q}

vilket leder (vid iterationer för m , m − 1, m − 2,....) till ett uttryck för de Gaussiska binomialkoefficienterna som i definitionen ovan.

Applikationer

Gaussiska binomialkoefficienter visas i räkningen av symmetriska polynom och i teorin om partitioner av tal . Koefficient q r in

{\displaystyle {n+m \choose m}_{q))

är antalet partitioner av numret r i m eller färre delar, som var och en inte är större än n . På motsvarande sätt är det också antalet partitioner av numret r i n eller färre delar, som var och en inte är större än m .

Gaussiska binomialkoefficienter spelar också en viktig roll i uppräkningen av projektiva utrymmen definierade över ett ändligt fält. Speciellt för varje ändligt fält F q med q element, den Gaussiska binomialkoefficienten

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

räknar antalet k -dimensionella vektordelrum i ett n -dimensionellt vektorrum över F q ( gräsmänniska ) . När det expanderas som ett polynom i q ger detta den välkända nedbrytningen av Grassmannian till Schubert-celler. Till exempel den Gaussiska binomialkoefficienten

{\displaystyle {n \choose 1}_{q}=1+q+q^{2}+\cdots +q^{n-1))

är antalet endimensionella delrum i ( F q ) n (motsvarande antalet punkter i det associerade projektiva utrymmet ). Dessutom, om q är lika med 1 (respektive −1), ger den gaussiska binomialkoefficienten Eulerkarakteristiken för motsvarande komplexa (respektive reella) Grassmannian.

Antalet k -dimensionella affina delrum F q n är

{\displaystyle q^{nk}{n \choose k}_{q))

Detta möjliggör en annan tolkning av identiteten

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

som ett antal ( r − 1)-dimensionella delrum av ett ( m − 1)-dimensionellt projektivt utrymme för ett fixerat hyperplan, i vilket fall man räknar antalet delrum som finns i detta fasta hyperplan. Dessa delrum är i bijektiv överensstämmelse med de ( r − 1)-dimensionella affina delrummen i rummet som erhålls genom att behandla detta fixerade hyperplan som ett hyperplan i oändligheten.

Inom kvantgruppsteorin finns det lite olika konventioner i definitionen. Kvantbinomialkoefficienterna är

q^{k^{2}-nk}{n \choose k}_{q^{2))

Denna version av kvantbinomialkoefficienten är symmetrisk med avseende på och . $q$ $q^{{-1}}$

Trianglar

Gaussiska binomialkoefficienter kan ordnas i en triangel för varje q och denna triangel för q =1 sammanfaller med Pascals triangel [2] .

Om vi placerar raderna av dessa trianglar på en linje får vi följande OEIS -sekvenser :

A022166 för q = 2
A022167 för q = 3
A022168 för q = 4
A022169 för q = 5
A022170 för q = 6
A022171 för q = 7
A022172 för q = 8
A022173 för q = 9
A022174 för q = 10

Anteckningar

↑ Kuzmin, 2000 , sid. 19.
↑ 1 2 Smirnov, 2015 , sid. åtta.
↑ Smirnov, 2015 , sid. 9.
↑ Smirnov, 2015 , sid. tio.

Litteratur

Smirnov E. Yu. Unga diagram och q-kombinatorik // Kvant. - 2015. - Nr 1 . - S. 7-12 . — ISSN 0130-2221 .
Kuzmin O.V. Generaliserade Pascal-pyramider och deras tillämpningar. - Novosibirsk: "Nauka" Siberian Publishing Company RAS, 2000. - ISBN 5-02-031578-8 .
Exton H. q-Hypergeometriska funktioner och tillämpningar. - New York: Halstead Press, 1983. - ISBN 0853124914 .
Eugene Mukhin. Symmetriska polynom och partitioner . Arkiverad från originalet den 10 december 2004.
Ratnadha Kolhatkar. Zeta-funktion av Grassmann-varianter . - 2004. - Januari.
Weisstein, Eric W. q-Binomial Coefficient (engelska) på Wolfram MathWorld -webbplatsen .
Henry Gould. Bracketfunktionen och Fontene-Ward generaliserade binomialkoefficienter med tillämpning på fibonomialkoefficienter // Fibonacci Quarterly . - 1969. - T. 7 . — S. 23–40 .
Alexanderson GL En Fibonacci-analog av Gaussiska binomialkoefficienter // Fibonacci Quarterly . - 1974. - T. 12 . — S. 129–132 .
George E. Andrews. Tillämpningar av grundläggande hypergeometriska funktioner // SIAM Rev .. - 1974. - V. 16 , nr. 4 . - doi : 10.1137/1016081 . — .
Peter B. Borwein. Padé approximationer för de q-elementära funktionerna // Construct. Ca.. - 1988. - V. 4 , nr. 1 . — S. 391–402 . - doi : 10.1007/BF02075469 .
John Konvalina. Generaliserade binomialkoefficienter och subset-subspace-problemet // Adv. Appl. Math.. - 1998. - T. 21 . — S. 228–240 . - doi : 10.1006/aama.1998.0598 .
Di Bucchianico A. Kombinatorik, datoralgebra och Wilcoxon-Mann-Whitney-testet // J. Stat. Plan. Inf.. - 1999. - T. 79 . — S. 349–364 . - doi : 10.1016/S0378-3758(98)00261-4 .
John Konvalina. En enhetlig tolkning av binomialkoefficienterna, stirlingtalen och gaussiska koefficienterna // Amer. Matematik. En gång i månaden. - 2000. - T. 107 , nr. 10 . — S. 901–910 . — .
Boris A. Kupershmidt. q-Newton binomial: från Euler till Gauss // J. Nonlin. Matematik. Phys.. - 2000. - Vol. 7 , nr. 2 . — S. 244–262 . - doi : 10.2991/jnmp.2000.7.2.11 . - . - arXiv : math/0004187 .
Henry Cohn. Projektiv geometri över F 1 och de Gaussiska binomialkoefficienterna // Amer. Matematik. En gång i månaden. - 2004. - T. 111 , nummer. 6 . — S. 487–495 . — .
Kim T. q-Utvidgning av Eulerformeln och trigonometriska funktioner // Russ. J Math. Phys.. - 2007. - Vol. 14 , nr. 3 . — S. 275–278 . - doi : 10.1134/S1061920807030041 . - .
Kim T. q-Bernoulli tal och polynom associerade med Gaussiska binomialkoefficienter // Russ. J Math. Phys.. - 2008. - Vol. 15 , nr. 1 . — S. 51–57 . - doi : 10.1134/S1061920808010068 . - .
Roberto B. Corcino. På p,q-binomialkoefficienter // Heltal. - 2008. - T. 8 . — S. #A29 .
Gevorg Hmayakyan. Rekursiv formel relaterad till Mobius-funktionen . — 2009.