Sequenza di tipo binomiale

In matematica, una sequenza polinomiale, cioè una successione di polinomi indiciati da { 0, 1, 2, 3, ... } dove l'indice di ogni polinomio coincide con il suo grado, si dice sequenza polinomiale di tipo binomiale, o più in breve sequenza di tipo binomiale, se soddisfa la successione di identità

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

Esistono molte sequenze siffatte e si dimostra che il loro insieme forma un gruppo di Lie per l'operazione di composizione umbrale che vedremo in seguito. Ogni sequenza di tipo binomiale è una sequenza di Sheffer, ma la maggior parte delle sequenze di Sheffer non sono di tipo binomiale.

Esempi

• In conseguenza della definizione, il teorema binomiale può essere enunciato dicendo che la sequenza polinomiale { xⁿ : n = 0, 1, 2, ... } è di tipo binomiale.

• La sequenza di fattoriali decrescenti è definita da

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

il prodotto è sottinteso che sia uguale a 1 nel caso n = 0, poiché in quel caso è un prodotto vuoto. Questa sequenza polinomiale è di tipo binomiale.

• Similmente anche i fattoriali crescenti

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

costituiscono una sequenza polinomiale di tipo binomiale.

• I polinomi di Abel

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

costituiscono una sequenza polinomiale di tipo binomiale.

• I polinomi di Touchard

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

dove S(n, k) è il numero di partizioni dell'insieme di n elementi in k sottoinsiemi disgiunti non vuoti, costituiscono una sequenza polinomiale di tipo binomiale. Eric Temple Bell chiama queste funzioni "esponenziali polinomiali" e questo termine ricorre a volte anche in letteratura. I coefficienti S(n, k ) sono i "numeri di Stirling del secondo ordine". Questa sequenza ha una curiosa connessione con la distribuzione di Poisson: se X è una variabile casuale con una distribuzione di Poisson con valore atteso λ allora E(Xⁿ) = p_n(λ). In particolare, quando λ = 1, vediamo che il momento n-esimo della distribuzione di Poisson con valore atteso 1 è il numero di partizioni di un insieme di n elementi, chiamato l'n-esimo numero di Bell. Questo fatto sull'n-esimo momento di quella particolare distribuzione di Poisson è la "formula di Dobinski".

Una semplice caratterizzazione

Si può dimostrare che una sequenza polinomiale { p_n(x) : n = 0, 1, 2, ... } è di tipo binomiale se e solo se la trasformazione lineare dello spazio di polinomi in x che è definita dalla

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

è shift-equivariante e p₀(x) = 1 per ogni x e p_n(0) = 0 per n > 0. (Dire che questo operatore è shift-equivariante equivale a dire che la sequenza polinomiale è una sequenza di Sheffer; l'insieme delle sequenze di tipo binomiale è propriamente incluso nell'insieme delle sequenze di Sheffer.)

Operatori delta

La precedente trasformazione lineare è chiaramente un operatore delta, cioè, una trasformazione lineare shift-equivariante sullo spazio dei polinomi in x che riduce i gradi dei polinomi di 1. Il più ovvio esempio di operatori delta sono gli operatori differenza e differenziazione. Si può dimostrare che ogni operatore delta può essere scritto come una serie di potenze della forma

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

dove D è la differenziazione (si noti che il limite inferiore della somma è 1). Ogni operatore delta Q possiede un'unica sequenza di "polinomi di base", cioè, una sequenza polinomiale che soddisfa le richieste

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

È stato dimostrato nel 1973 da Rota, Kahaner e Odlyzko, che una sequenza polinomiale è di tipo binomiale se e solo se è la sequenza dei polinomi di base per qualche operatore delta. Perciò la prima formula del corrente paragrafo fornisce una ricetta per generare tutte le sequenze polinomiali di tipo binomiale che si vogliono: basta scegliere i c_n.

Composizione umbrale di sequenza polinomiali

L'insieme di tutte le sequenze polinomiali di tipo binomiale costituisce un gruppo per l'operazione detta "composizione umbrale" di sequenze polinomiali che ora definiamo. Supponiamo che { p_n(x) : n = 0, 1, 2, 3, ... } e { q_n(x) : n = 0, 1, 2, 3, ... } siano sequenze polinomiali, e che

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

Per composizione umbrale ${\displaystyle p\circ q}$ si definisce la sequenza polinomiale il cui n-esimo termine è

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

Con l'operatore delta definito da una sequenza di potenze in D come sopra, la biiezione naturale fra gli operatori delta e sequenze polinomiali di tipo binomiale, definita sopra, è un isomorfismo di gruppo, nel quale l'operazione gruppale tra serie di potenze è (forse sorprendentemente) la composizione formale di serie formali di potenze.

Caratterizzazione mediante funzioni generatrici

Le sequenze polinomiali di tipo binomiale sono precisamente quelle le cui funzioni generatrici sono serie formali di potenze (non necessariamente convergenti) della forma

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

dove f(t) è una serie formale di potenze il cui termine costante è zero e il cui termine di primo grado è non nullo. Questo si può dimostrare usando la versione per le serie di potenze della formula di Faà di Bruno cioè la

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

L'operatore delta della serie è f⁻¹(D) e quindi

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

Cumulanti e momenti

la successione κ_n dei coefficienti di termini di primo grado in una sequenza polinomiale di tipo binomiale può essere chiamata successione dei cumulanti della sequenza polinomiale. Si può quindi dire che ogni sequenza polinomiale di tipo binomiale è interamente determinata dai suoi cumulanti , in sintonia di quanto presentato nell'articolo intitolato cumulante. In questo modo abbiamo

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

e

${\displaystyle p_{n}(1)=\mu _{n}'=}$ nesimo momento.

Questi conviene siano chiamati "cumulanti formali" e "momenti formali", per distinguerli dai cumulanti e dai momenti di una distribuzione di probabilità.

Sia

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

la funzione generatrice dei cumulanti (formalie). Allora

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

è l'operatore delta associato alla sequenza polinomiale, cioè, abbiamo

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

Applicazioni

Il concetto di sequenza polinomiale di tipo binomiale ha applicazioni in combinatorica, probabilità, statistica, e in una varietà di altri campi.

Bibliografia

• (EN) Gian-Carlo Rota, Andrew Odlyzko e David Kahaner, Finite operatore Calculus. Journal of Mathematical Analysis and its Applications, 1973. vol. 42, no. 3, June 1973. Ristampato nel libro dello stesso titolo edito da Academic Press, New York, (1975). Lavoro nel quale sono apparsi i risultati di base tra quelli enunciati in questo articolo.

• (EN) Ronald Mullin e Gian-Carlo Rota, On the Foundations of Combinatorial Theory III: Theory of Binomial Enumeration, New York, Academic Press, 1970, ISBN 978-01-23-26850-1. contenuto in "Graph Theory and Its Applications" di Bernard Harris. Come suggerisce lo stesso titolo, questo testo riguarda esplicitamente le applicazioni alla enumerazione combinatoria.

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