Numeri di Stirling

In matematica, i numeri di Stirling sono delle quantità che si incontrano in vari campi della combinatoria. Prendono il loro nome dal matematico James Stirling.

Prima specie

I numeri di Stirling di prima specie $s (n, k)$ (s minuscola) sono definiti come i coefficienti dello sviluppo polinomiale del fattoriale decrescente di x con n fattori:

(x)_{n} = x (x - 1) (x - 2) \dots (x - n + 1) = \sum_{k = 1}^{n} s (n, k) x^{k}

I numeri di Stirling di prima specie senza segno sono definiti invece da

| s (n, k) | = (- 1)^{n - k} s (n, k)

e rappresentano il numero di possibili permutazioni di n elementi in k cicli disgiunti.

Sono talvolta scritti con la notazione alternativa $[\begin{matrix} n \\ k \end{matrix}]$ .

Tavola di valori

n \ k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	−1	1
3	0	2	−3	1
4	0	−6	11	−6	1
5	0	24	−50	35	−10	1
6	0	−120	274	−225	85	−15	1
7	0	720	−1764	1624	−735	175	−21	1
8	0	−5040	13068	−13132	6769	−1960	322	−28	1
9	0	40320	−109584	118124	−67284	22449	−4536	546	−36	1

Formula esplicita

s (n, k) = [(- 1)^{n - k}] \times [\frac{n!}{(k - 1)! \times 2^{n - k}}] \times

[(1 / (n - k)!) \times n^{n - k - 1}

- (1 / 6) \times (1 / (n - k - 2)!) \times n^{n - k - 2}

+ (1 / 72) \times (1 / (n - k - 4)!) \times n^{n - k - 3}

- (1 / 6480) \times (5 / (n - k - 6)! - 36 / (n - k - 4)!) \times n^{n - k - 4}

+ (1 / 155520) \times (5 / (n - k - 8)! - 144 / (n - k - 6)!) \times n^{n - k - 5}

- (1 / 6531840) \times (7 / (n - k - 10)! - 504 / (n - k - 8)! + 2304 / (n - k - 6)!) \times n^{n - k - 6}

+ (1 / 1175731200) \times (35 / (n - k - 12)! - 5040 / (n - k - 10)! + 87264 / (n - k - 8)!) \times n^{n - k - 7}

- (1 / 7054387200) \times (5 / (n - k - 14)! - 1260 / (n - k - 12)! + 52704 / (n - k - 10)! - 186624 / (n - k - 8)!) \times n^{n - k - 8}

+ (1 / 338610585600) \times (5 / (n - k - 16)! - 2016 / (n - k - 14)! + 164736 / (n - k - 12)! - 2156544 / (n - k - 10)!) \times n^{n - k - 9}

- ...]

Sorgente: André F. Labossière, 2006-03-27, A008275 ( OEIS - The On-Line Encyclopedia of Integer Sequences )

Seconda specie

I numeri di Stirling di seconda specie $S (n, k)$ (S maiuscola) sono definiti come il numero di possibili k-partizioni (cioè partizioni fatte da k insiemi) di un insieme di cardinalità n. Valgono le relazioni:

\sum_{k = 0}^{n} S (n, k) (x)_{k} = x^{n}

e

B_{n} = \sum_{k = 1}^{n} S (n, k)

dove B_n è l'n-esimo numero di Bell.

Inoltre, è possibile ricavare una formula esplicita per calcolare numeri di Stirling di seconda specie. Si può infatti osservare che il numero di funzioni suriettive da un insieme di cardinalità n ad uno di cardinalità k può essere individuato partizionando il dominio (di cardinalità n) in k blocchi e associando ad ognuno di questi blocchi uno dei k elementi del codominio (e ciò si può fare in k! modi). Così si ricava la formula:

S (n, k) = \frac{1}{k!} \sum_{j = 0}^{k} (- 1)^{k - j} (\binom{k}{j}) j^{n}

Sono talvolta scritti in notazione alternativa come $S_{n}^{(k)}$ o ${\begin{matrix} n \\ k \end{matrix}}$ . Come per la prima specie, l'idea di usare parentesi, in analogia con il coefficiente binomiale, è venuta per la prima volta a Jovan Karamata nel 1935 ed è stata supportata poi da Donald Knuth; è per questo nota come "notazione Karamata".

Tavola di valori

n \ k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1
7	0	1	63	301	350	140	21	1
8	0	1	127	966	1701	1050	266	28	1
9	0	1	255	3025	7770	6951	2646	462	36	1

Relazioni

I numeri di prima e seconda specie sono legati dalle relazioni

\sum_{k = 0}^{n} [\begin{matrix} n \\ k \end{matrix}] {\begin{matrix} k \\ m \end{matrix}} (- 1)^{k} = (- 1)^{n} δ_{m n}

e

\sum_{k = 0}^{n} {\begin{matrix} n \\ k \end{matrix}} [\begin{matrix} k \\ m \end{matrix}] (- 1)^{k} = (- 1)^{n} δ_{m n}

dove $δ_{j k}$ è il delta di Kronecker. Queste relazioni possono essere interpretate come segue: la matrice $(- 1)^{n - k} {\begin{matrix} n \\ k \end{matrix}}$ è l'inversa della matrice $[\begin{matrix} n \\ k \end{matrix}]$ , e analogamente la matrice $(- 1)^{n - k} [\begin{matrix} n \\ k \end{matrix}]$ è l'inversa della matrice ${\begin{matrix} n \\ k \end{matrix}}$ .

Abramowitz e Stegun inoltre hanno dato le seguenti formule che legano tra loro i due tipi di numeri:

[\begin{matrix} n \\ k \end{matrix}] = \sum_{j = 0}^{n - k} (- 1)^{j} (\binom{n - 1 + j}{n - k + j}) (\binom{2 n - k}{n - k - j}) {\begin{matrix} n - k + j \\ j \end{matrix}}

e

{\begin{matrix} n \\ k \end{matrix}} = \sum_{j = 0}^{n - k} (- 1)^{j} (\binom{n - 1 + j}{n - k + j}) (\binom{2 n - k}{n - k - j}) [\begin{matrix} n - k + j \\ j \end{matrix}]

.

Bibliografia

(EN) Rosen Kenneth H., Handbook of Discrete and Combinatorial Mathematics, Boca Raton, CRC Press, 2018, ISBN 978-1-5848-8780-5.
(EN) Mansour Toufik; Schork Mathias, Commutation Relations, Normal Ordering, and Stirling Numbers, Boca Raton, CRC Press, 2015, ISBN 978-1-4665-7989-7.

Voci correlate

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