Polinomi di Bell

Da Teknopedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

Nella matematica combinatoria, i polinomi di Bell, in onore del matematico scozzese Eric Temple Bell, sono una famiglia di polinomi utilizzati nello studio delle partizioni di un insieme. Sono connessi ai numeri di Stirling e di Bell, e compaiono in numerose applicazioni, come ad esempio nella formula di Faà di Bruno.

Polinomi di Bell esponenziali

[modifica | modifica wikitesto]

I polinomi esponenziali parziali o incompleti sono una famiglia di polinomi definiti da

dove la somma è su tutte le sequenze , , , , di interi non negativi tali che le seguenti due condizioni siano soddisfatte:

La somma al variare di dei polinomi incompleti

è chiamata l'n-esimo polinomio di Bell esponenziale completo.

Polinomi di Bell ordinari

[modifica | modifica wikitesto]

I polinomi di Bell ordinari sono invece definiti come

dove la somma è su tutte le sequenze , , , , di interi non negativi tali che

I polinomi di Bell ordinari si possono esprimere in funzione di quelli esponenziali come:

In generale, con il termine generico polinomi di Bell ci si riferisce alla versione esponenziale, a meno che non venga specificato esplicitamente.

Significato combinatorio

[modifica | modifica wikitesto]

I polinomi di Bell esponenziali sono collegati ai vari modi in cui un insieme può essere partizionato. Per esempio, se si considera un insieme , può essere diviso in due insiemi disgiunti e non vuoti, quest'ultimi chiamati anche blocchi, in tre diversi modi:

Questa informazione è codificata all'interno del seguente polinomio di Bell

Qui il pedice di indica che stiamo considerando le partizioni di 3 elementi in 2 blocchi, mentre il termine indica la presenza di blocchi composti da elementi all'interno di una partizione. Nel caso precedente, indica la presenza di un solo blocco con due elementi. In modo simile, mostra la presenza di un unico blocco con un singolo elemento. Il coefficiente del monomio mostra il numero di queste partizioni. Nell'esempio considerato esistono 3 partizioni di un insieme con tre elementi in due blocchi, dove in ogni partizione gli elementi sono divisi in due blocchi di grandezza 1 e 2.

Dato che un insieme può essere diviso in un unico blocco in un solo modo possibile, l'interpretazione precedente implica che . In modo simile, poiché esiste un unico modo in cui un insieme di n elementi può essere partizionato in n singoletti, allora .

Un caso più complicato è il seguente

Da questo polinomio si può inferire che se un insieme di 6 elementi viene diviso in 2 blocchi, allora si possono avere 6 partizioni con blocchi di dimensione 1 e 5, 15 partizioni con blocchi di 4 e 2 elementi, e 10 partizioni con due blocchi di grandezza 3.

La somma dei pedici in un monomio è uguale al numero totale di elementi dell'insieme. Perciò, il numero di monomi che appaiono nel polinomio di Bell parziale è uguale al numero di modi in cui un intero può essere espresso come somma di interi positivi, cioè la partizione dell'intero in parti. Negli esempi precedenti, il numero 3 può essere partizionato in due parti solo come 2+1, perciò è composto da un unico monomio. Al contrario, il numero 6 può essere scritto come 5+1, 4+2 e 3+3, quindi in i monomi sono 3. Il numero totale di monomi che appaiono in un polinomio di Bell completo è quindi uguale al numero totale di partizioni intere di .

Inoltre il grado di ogni monomio, che è la somma degli esponenti di ciascuna variabile nel monomio, è uguale al numero di blocchi in cui l'insieme è diviso. In altre parole, . Di conseguenza, dato un polinomio di Bell completo , si possono separare i vari polinomi parziali raggruppando tutti i monomi di grado .

Infine, la somma dei coefficienti del polinomio di Bell parziale darà il numero di partizioni di un insieme di elementi in blocchi, che è la definizione del numero di Stirling di seconda specie . Inoltre, la somma di tutti i coefficienti del corrispondente polinomio di Bell completo darà il numero totale di partizioni possibili dell'insieme di elementi, e quindi sarà il relativo numero di Bell.

Per esempio, si ha

perché i modi di partizionare un insieme di 6 elementi in 2 blocchi sono

6 modi con ,
15 modi con , e
10 modi con .

Similmente,

perché i modi di partizionare un insieme di 6 elementi in 3 blocchi sono

15 modi con ,
60 modi con , e
15 modi con .

Funzione generatrice

[modifica | modifica wikitesto]

I polinomi di Bell parziali possono essere definiti tramite l'espansione della funzione generatrice in una doppia serie:

In modo equivalente, è l'espansione in serie della k-esima potenza:

I polinomio di Bell completi sono definiti come , o in altre parole:

Perciò, l'n-esimo polinomio completo è dato da

Similmente, i polinomi di Bell ordinari corrispondono alla funzione generatrice

O, equivalentemente, dall'espansione in serie della k-esima potenza:

I polinomi di Bell sono fondamentali per calcolare potenze, logaritmi, esponenziali e composizioni di funzioni generatrici[1].

Relazioni di ricorrenza

[modifica | modifica wikitesto]

I polinomi di Bell completi si possono definire ricorsivamente come

con il valore iniziale .

I polinomi parziali invece si possono calcolare in modo efficiente dalla seguente relazione di ricorrenza:

where

I polinomi completi inoltre soddisfano la ricorrenza differenziale[2]:

Le derivate parziali dei polinomi di Bell completi sono date da[3]

In modo simile, le derivate parziali dei polinomi di Bell incompleti sono

Se gli argomenti dei polinomi di Bell sono funzioni unidimensionali, si può usare la regola della catena per ottenere

Si possono esprimere i polinomi di Bell completi come dei determinanti nei due seguenti modi:

e

Legame con i numeri di Stirling e di Bell

[modifica | modifica wikitesto]

Il valore del polinomio di Bell incompleto calcolato sulla sequenza dei fattoriali è uguale a un numero di Stirling di prima specie senza segno:

La somma di questi numeri da il valore del polinomio di Bell completo sulla sequenza dei fattoriali:

Il valore del polinomio calcolato su una sequenza di 1 è uguale a un numero di Stirling di seconda specie:

La somma di questi numeri da il valore del polinomio di Bell completo sulla n-upla di 1:

che è l'n-esimo numero di Bell.

Relazioni inverse

[modifica | modifica wikitesto]

Se si definisce

allora si ha la relazione inversa

Polinomi di Touchard

[modifica | modifica wikitesto]

Il polinomio di Touchard può essere espresso come un polinomio di Bell completo con tutte le variabili uguali a :

Identità di convoluzione

[modifica | modifica wikitesto]

Per le successioni e viene definita una convoluzione tramite:

Da notare che i limiti della sommatoria sono e .

Sia l'n-esimo termine della successione

Allora[4]

Per esempio, per quanto riguarda , si ha

e quindi,

Altre identità

[modifica | modifica wikitesto]
  • che è il numero di Lah.
  • , che è collegato al numero di funzioni idempotenti di un insieme di elementi.
  • and .
  • I polinomi di Bell completi soddisfano una relazione di tipo binomiale:
  • Quando ,
  • Casi particolari di polinomi di Bell parziali:

Polinomi completi di grado più basso

[modifica | modifica wikitesto]

I primi polinomi di Bell completi sono:

Formula di Faà di Bruno

[modifica | modifica wikitesto]
Lo stesso argomento in dettaglio: Formula di Faà di Bruno.

La formula di Faà di Bruno può essere espressa in termini dei polinomi di Bell nel modo seguente:

La versione con le serie di potenze afferma che se

allora

Un caso particolare è l'esponenziale di una serie formale di potenze:

che rappresenta anche la funzione generatrice esponenziale dei polinomi di Bell completi calcolata su una sequenza fissata di valori .

Reversione della serie

[modifica | modifica wikitesto]
Lo stesso argomento in dettaglio: Teorema di inversione di Lagrange.

Siano due funzioni e espresse in serie formali di potenze come

tale che è l'inversa di , definita da oppure . Se e , allora esiste una forma esplicita dei coefficienti dell'inversa in termini dei polinomi di Bell[5]:

con , il fattoriale crescente, e

Espansione asintotica degli integrali di Laplace

[modifica | modifica wikitesto]
Lo stesso argomento in dettaglio: Metodo di Laplace.

Si consideri l'integrale della forma

dove è un intervallo reale (anche infinito), è un parametro positivo sufficientemente grande, e le funzioni e sono continue. La funzione ha un solo minimo in che lo assume in . Si assuma che per ,

con , ; e che l'espansione di possa essere derivata termine a termine. Allora, il teorema di Laplace–Erdelyi afferma che l'espansione asintotica dell'integrale è data da

dove i coefficienti sono esprimibili in termini di e usando i polinomi di Bell ordinari grazie alla formula di Campbell–Froman–Walles–Wojdylo:

Polinomi simmetrici

[modifica | modifica wikitesto]
Lo stesso argomento in dettaglio: Identità di Newton.

Il polinomio simmetrico elementare e il polinomio simmetrico ottenuto con somma di potenze n-esime sono in relazione tra loro tramite i polinomi di Bell:

Questo formule permettono di esprimere i coefficienti dei polinomi monici in termine dei polinomi di Bell calcolati nei loro zeri. Un'applicazione delle proprietà è che, insieme al teorema di Hamilton-Cayley, si ottiene un'espressione del determinante di una matrice quadrata di dimensione in funzione delle tracce delle sue potenze:

Indice di ciclo dei gruppi simmetrici

[modifica | modifica wikitesto]

L'indice di ciclo del gruppo simmetrico è dato da:

Momenti e cumulanti

[modifica | modifica wikitesto]

La somma

è l'n-esimo momento semplice di una distribuzione di probabilità i cui primi n cumulanti sono . In altre parole, l'n-esimo momento è l'n-esimo polinomio di Bell completo valutato nei primi n cumulanti. Similmente, l'n-esimo cumulante si può esprimere in termini dei momenti come

Polinomi di Hermite

[modifica | modifica wikitesto]

I polinomi di Hermite probabilistici sono dati da

dove per ogni ; in questo modo si ha un'interpretazione combinatoria dei coefficienti dei polinomi di Hermite. Si può vedere meglio comparando la funzione generatrice dei polinomi di Hermite

con quella dei polinomi di Bell.

Rappresentazione delle successioni di polinomi di tipo binomiale

[modifica | modifica wikitesto]

Per ogni successione , , , di scalari, sia

Questa sequenza di polinomi è di tipo binomiale, cioè soddisfa l'identità binomiale

Per esempio con , i polinomi rappresentano i polinomi di Touchard.

Si ha il risultato generale che i polinomi rappresentano tutti i polinomi di tipo binomiale. Detto in altre parole, tutti polinomi di tipo binomiale si possono scrivere in questa forma, rappresentandone una relazione biunivoca.

Se si definisce una serie formale di potenze

allora per ogni ,

In altre parole, l'operatore di sinistra ha le proprietà di operatore delta per i polinomi .

Implementazioni

[modifica | modifica wikitesto]

I polinomi di Bell sono implementati in:

  1. ^ Comtet, L., Advanced Combinatorics: The Art of Finite and Infinite Expansions, Reidel Publishing Company, 1974 (archiviato dall'url originale il 1º giugno 2017).
  2. ^ Alexeev, N., Pologova, A. e Alekseyev, M. A., Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs, in Journal of Computational Biology, vol. 24, n. 2, 2017, DOI:10.1089/cmb.2016.0190, arXiv:1503.05285.
  3. ^ Bell, E. T., Exponential Polynomials, in Annals of Mathematics, vol. 35, n. 2, 1934, DOI:10.2307/1968431.
  4. ^ Cvijović, D., New identities for the partial Bell polynomials (PDF), in Applied Mathematics Letters, vol. 24, n. 9, 2011, DOI:10.1016/j.aml.2011.03.043 (archiviato dall'url originale il 9 marzo 2020).
  5. ^ Charalambides, C. A., Enumerative Combinatorics, Chapman & Hall / CRC, 2002, p. 632, ISBN 9781584882909.

Voci correlate

[modifica | modifica wikitesto]
  Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica