Secvență de tip binomial

În matematică , o secvență polinomială , adică o secvență de polinoame indicate prin {0, 1, 2, 3, ...} în care indicele fiecărui polinom coincide cu gradul său, se numește o secvență polinomială de tip binomial sau mai mult în secvență scurtă, binomială , dacă satisface succesiunea identităților

p_{n}(x+y)=\sum _{k=0}^{n}{n \choose k}\,p_{k}(x)\,p_{n-k}(y).

{\ displaystyle p_ {n} (x + y) = \ sum _ {k = 0} ^ {n} {n \ alege k} \, p_ {k} (x) \, p_ {nk} (y). }

{\ displaystyle p_ {n} (x + y) = \ sum _ {k = 0} ^ {n} {n \ alege k} \, p_ {k} (x) \, p_ {nk} (y). }

Există multe astfel de secvențe și se arată că ansamblul lor formează un grup Lie pentru operația de compoziție umbrală pe care o vom vedea mai târziu. Fiecare secvență binomială este o secvență Sheffer , dar majoritatea secvențelor Sheffer nu sunt de tip binomial.

Exemple

Ca o consecință a definiției, teorema binomului poate fi afirmată spunând că secvența polinomială { x ⁿ : n = 0, 1, 2, ...} este de tip binomial.

Secvența factorialelor descrescătoare este definită de

(x)_{n}:=x(x-1)(x-2)\cdot \cdots \cdot (x-n+1)~;

{\ displaystyle (x) _ {n}: = x (x-1) (x-2) \ cdot \ cdots \ cdot (x-n + 1) ~;}

{\ displaystyle (x) _ {n}: = x (x-1) (x-2) \ cdot \ cdots \ cdot (x-n + 1) ~;}

produsul se înțelege a fi egal cu 1 în cazul n = 0, deoarece în acest caz este un produs gol . Această secvență polinomială este de tip binomial.

La fel și factorialele în creștere

x^{(n)}:=x(x+1)(x+2)\cdot \cdots \cdot (x+n-1)

{\ displaystyle x ^ {(n)}: = x (x + 1) (x + 2) \ cdot \ cdots \ cdot (x + n-1)}

{\ displaystyle x ^ {(n)}: = x (x + 1) (x + 2) \ cdot \ cdots \ cdot (x + n-1)}

constituie o secvență polinomială de tip binomial.

Polinoamele lui Abel

p_{n}(x):=x(x-an)^{n-1}

{\ displaystyle p_ {n} (x): = x (x-an) ^ {n-1}}

{\ displaystyle p_ {n} (x): = x (x-an) ^ {n-1}}

constituie o secvență polinomială de tip binomial.

Polinoamele Touchard

p_{n}(x):=\sum _{k=1}^{n}S(n,k)x^{k}

{\ displaystyle p_ {n} (x): = \ sum _ {k = 1} ^ {n} S (n, k) x ^ {k}}

{\ displaystyle p_ {n} (x): = \ sum _ {k = 1} ^ {n} S (n, k) x ^ {k}}

unde S ( n , k ) este numărul de partiții ale setului de n elemente din k subseturi disjuncte ne-goale, constituie o secvență polinomială de tip binomial. Eric Temple Bell numește aceste funcții „exponențiale polinomiale” și acest termen apare și uneori în literatură. Coeficienții S ( n , k ) sunt „ numerele Stirling de ordinul doi”. Această secvență are o conexiune curioasă cu distribuția Poisson : dacă X este o variabilă aleatorie cu o distribuție Poisson cu valoarea așteptată λ atunci E ( X ⁿ ) = p _n (λ). În special, când λ = 1, vedem că al n - lea moment al distribuției Poisson cu valoarea așteptată 1 este numărul de partiții ale unui set de n elemente, numit al n - lea număr Bell . Acest fapt despre cel de - al nouălea moment al acelei distribuții Poisson este „ formula Dobinski ”.

O caracterizare simplă

Se poate arăta că o secvență polinomială { p _n (x): n = 0, 1, 2, ...} este de tip binomial dacă și numai dacă transformarea liniară a spațiului polinoamelor în x care este definită de

p_{n}(x)\mapsto np_{n-1}(x)

{\ displaystyle p_ {n} (x) \ mapsto np_ {n-1} (x)}

{\ displaystyle p_ {n} (x) \ mapsto np_ {n-1} (x)}

este shift-echivariant și p ₀ ( x ) = 1 pentru toate x și p _n (0) = 0 pentru n > 0. (A spune că acest operator este shift-echivariant înseamnă a spune că secvența polinomială este o secvență Sheffer ; setul de secvențe binomiale este inclus în mod corespunzător în setul de secvențe Sheffer.)

Operatori Delta

Transformarea liniară de mai sus este în mod clar un operator delta , adică o transformare liniară shift-echivariantă pe spațiul polinoamelor din x care reduce gradele polinoamelor cu 1. Cel mai evident exemplu de operatori delta sunt operatorii de diferență și diferențiere. Se poate arăta că orice operator delta poate fi scris ca o serie de putere a formularului

Q=\sum _{n=1}^{\infty }c_{n}D^{n}

{\ displaystyle Q = \ sum _ {n = 1} ^ {\ infty} c_ {n} D ^ {n}}

{\ displaystyle Q = \ sum _ {n = 1} ^ {\ infty} c_ {n} D ^ {n}}

unde D este diferențierea (rețineți că limita inferioară a sumei este 1). Fiecare operator delta Q are o secvență unică de „polinoame de bază”, adică o secvență polinomială care satisface cerințele

$p_{0}(x)=1~,$ ${\ displaystyle p_ {0} (x) = 1 ~,}$ ${\ displaystyle p_ {0} (x) = 1 ~,}$
$p_{n}(0)=0\quad {\rm {per\ }}n\geq 1~,$ ${\ displaystyle p_ {n} (0) = 0 \ quad {\ rm {pentru \}} n \ geq 1 ~,}$ ${\ displaystyle p_ {n} (0) = 0 \ quad {\ rm {pentru \}} n \ geq 1 ~,}$
$Qp_{n}(x)=np_{n-1}(x)~.$ ${\ displaystyle Qp_ {n} (x) = np_ {n-1} (x) ~.}$ ${\ displaystyle Qp_ {n} (x) = np_ {n-1} (x) ~.}$

S-a demonstrat în 1973 de Rota , Kahaner și Odlyzko că o secvență polinomială este de tip binomial dacă și numai dacă este secvența polinoamelor de bază pentru un operator delta. Prin urmare, prima formulă a paragrafului actual oferă o rețetă pentru generarea tuturor secvențelor polinomiale de tip binomial pe care le doriți: alegeți doar c _n .

Compoziția umbrală a secvențelor polinomiale

Setul tuturor secvențelor polinomiale de tip binomial constituie un grup pentru operația numită „compoziție umbrală” a secvențelor polinomiale pe care le definim acum. Să presupunem că { p _n (x): n = 0, 1, 2, 3, ...} și { q _n (x): n = 0, 1, 2, 3, ...} sunt secvențe polinomiale și acea

p_{n}(x)=\sum _{k=0}^{n}a_{n,k}\,x^{k}~.

{\ displaystyle p_ {n} (x) = \ sum _ {k = 0} ^ {n} a_ {n, k} \, x ^ {k} ~.}

{\ displaystyle p_ {n} (x) = \ sum _ {k = 0} ^ {n} a_ {n, k} \, x ^ {k} ~.}

Prin compoziția umbrală $p\circ q$ ${\ displaystyle p \ circ q}$ ${\ displaystyle p \ circ q}$ definim secvența polinomială al cărei al n-lea termen este

(p_{n}\circ q)(x)=\sum _{k=0}^{n}a_{n,k}\,q_{k}(x)~.

{\ displaystyle (p_ {n} \ circ q) (x) = \ sum _ {k = 0} ^ {n} a_ {n, k} \, q_ {k} (x) ~.}

{\ displaystyle (p_ {n} \ circ q) (x) = \ sum _ {k = 0} ^ {n} a_ {n, k} \, q_ {k} (x) ~.}

Cu operatorul delta definit de o secvență de puteri în D ca mai sus, bijecția naturală dintre operatorii delta și secvențele polinomiale de tip binomial, definite mai sus, este un izomorfism de grup, în care operația de grup între seria de puteri este (poate surprinzător) compoziția formală a seriilor formale de putere.

Caracterizare prin intermediul funcțiilor generatoare

Secvențele polinomiale de tip binomial sunt tocmai acelea ale căror funcții generatoare sunt formale (nu neapărat convergente) serii de forme ale formei

\sum _{n=0}^{\infty }{p_{n}(x) \over n!}t^{n}=e^{xf(t)}

{\ displaystyle \ sum _ {n = 0} ^ {\ infty} {p_ {n} (x) \ over n!} t ^ {n} = e ^ {xf (t)}}

{\ displaystyle \ sum _ {n = 0} ^ {\ infty} {p_ {n} (x) \ over n!} t ^ {n} = e ^ {xf (t)}}

unde f ( t ) este o serie formală de puteri al căror termen constant este zero și al cărui termen de gradul I este diferit de zero. Acest lucru poate fi demonstrat folosind versiunea Power Series a formulei lui Faà di Bruno, adică

f(t)=\sum _{n=1}^{\infty }{p_{n}'(0) \over n!}t^{n}.

{\ displaystyle f (t) = \ sum _ {n = 1} ^ {\ infty} {p_ {n} '(0) \ over n!} t ^ {n}.}

{\ displaystyle f (t) = \ sum _ {n = 1} ^ {\ infty} {p_ {n} '(0) \ over n!} t ^ {n}.}

Operatorul delta al seriei este f ⁻¹ ( D ) și deci

f^{-1}(D)p_{n}(x)\,=\,np_{n-1}(x).

{\ displaystyle f ^ {- 1} (D) p_ {n} (x) \, = \, np_ {n-1} (x).}

{\ displaystyle f ^ {- 1} (D) p_ {n} (x) \, = \, np_ {n-1} (x).}

Cumulanți și momente

secvența κ _n a coeficienților termenilor de gradul întâi într-o secvență polinomială de tip binomial poate fi numită secvența cumulanților secvenței polinomiale. Prin urmare, se poate spune că fiecare secvență polinomială de tip binomial este în întregime determinată de cumulanții săi, în armonie cu ceea ce este prezentat în articolul intitulat cumulant . În acest fel avem

p_{n}'(0)=\kappa _{n}=

{\ displaystyle p_ {n} '(0) = \ kappa _ {n} =}

{\ displaystyle p_ {n} '(0) = \ kappa _ {n} =}

n a cumulativ

Și

p_{n}(1)=\mu _{n}'=

{\ displaystyle p_ {n} (1) = \ mu _ {n} '=}

{\ displaystyle p_ {n} (1) = \ mu _ {n} '=}

a n- o oară.

Acestea sunt numite în mod convenabil „cumulanți formali” și „ momente formale”, pentru a le distinge de cumulanți și momente ale unei distribuții de probabilitate .

Este

f(t):=\sum _{n=1}^{\infty }{\frac {\kappa _{n}}{n!}}t^{n}

{\ displaystyle f (t): = \ sum _ {n = 1} ^ {\ infty} {\ frac {\ kappa _ {n}} {n!}} t ^ {n}}

{\ displaystyle f (t): = \ sum _ {n = 1} ^ {\ infty} {\ frac {\ kappa _ {n}} {n!}} t ^ {n}}

funcția generatoare a cumulanților (formalități). Atunci

f^{-1}(D)

{\ displaystyle f ^ {- 1} (D)}

{\ displaystyle f ^ {- 1} (D)}

este operatorul delta asociat cu secvența polinomială, adică avem

f^{-1}(D)p_{n}(x)\,=\,np_{n-1}(x).

{\ displaystyle f ^ {- 1} (D) p_ {n} (x) \, = \, np_ {n-1} (x).}

{\ displaystyle f ^ {- 1} (D) p_ {n} (x) \, = \, np_ {n-1} (x).}

Aplicații

Conceptul unei secvențe polinomiale binomiale are aplicații în combinatorică , probabilitate , statistici și o varietate de alte domenii.

Bibliografie

( RO ) Gian-Carlo Rota , Andrew Odlyzko și David Kahaner, operator de calcul finit. Journal of Mathematical Analysis and its Applications , 1973. vol. 42, nr. 3, iunie 1973. Retipărit în cartea cu același titlu publicată de Academic Press, New York, (1975). Lucrare în care au apărut rezultatele de bază dintre cele prezentate în acest articol.

( EN ) Ronald Mullin și Gian-Carlo Rota, Despre fundamentele teoriei combinatorii III: Teoria enumerării binomiale , New York , Academic Press , 1970, ISBN 978-01-23-26850-1 . cuprins în „Teoria graficului și aplicațiile sale” de Bernard Harris. După cum sugerează titlul însuși, acest text se referă în mod explicit la aplicații la enumerarea combinatorie .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

V · D · M Combinatorial
Orientare generală	Combinatorică · Istoria combinatoriei · Matematică discretă · Secțiunea 05-XX din MSC
Noțiuni introductive	Permutații · Dispoziții · Combinații · Coeficienți binomiali · Partiții de numere întregi · Partiții de mulțimi finite - Identități și bijecții combinatorii
Configurări	Pătrat latin · pătrate magice · Desene Block · geometrii finite · Matroids - mozaicare · Polimini
Teoria graficelor	Copaci · Mers pe grafice ( eulerian , hamiltonian ) · Conexiune în grafice - grafice plane · Vopsirea graficelor și teorema celor patru culori ) · hipergrafe · Grafice și grupuri · digraf · Graficul fluxului de numerar · Plimbări aleatorii pe grafice · omomorfismul graficelor · Algoritmi pe grafice
Combinatorie algebrică	Tabelul lui Young · funcții simetrice - serie de puteri formale · Funcții de generare · Polinoame ortogonale · Părți ale unui grup de structuri combinatorii - Aspecte algebră comutativă combinatorie
Alte domenii	Calculul umbrelor ( secvențe polinomiale de tip binomial · secvențe Sheffer ) - Combinatorial extremal