Numere stirling

În matematică , numerele Stirling sunt cantități care se întâlnesc în diferite domenii ale combinatoriei . Ele poartă numele matematicianului James Stirling .

Prima specie

Numerele Stirling de primul fel $s(n,k)$ ${\ displaystyle s (n, k)}$ $s (n, k)$ (minuscule) sunt definite ca fiind coeficienții dezvoltării polinomiale a factorului descrescător al lui x cu n factori:

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

{\ displaystyle (x) _ {n} = x (x-1) (x-2) \ cdots (x-n + 1) = \ sum _ {k = 1} ^ {n} s (n, k) x ^ {k}}

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

Numerele Stirling de prima natură nesemnate sunt definite de

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

{\ displaystyle \ left | s (n, k) \ right | = (- 1) ^ {nk} s (n, k)}

{\ displaystyle \ left | s (n, k) \ right | = (- 1) ^ {n-k} s (n, k)}

și reprezintă numărul de permutări posibile de n elemente în k cicluri disjuncte.

Uneori sunt scrise cu notația alternativă $\left[{\begin{matrix}n\\k\end{matrix}}\right]$ ${\ displaystyle \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right]}$ ${\ displaystyle \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right]}$ .

Tabelul valorilor

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 explicită

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

{\ displaystyle s (n, k) = [(- 1) ^ {nk}] \ times \ left [{\ frac {n!} {(k-1)! \ times 2 ^ {nk}}} \ right ] \ ori}

{\ displaystyle s (n, k) = [(- 1) ^ {nk}] \ times \ left [{\ frac {n!} {(k-1)! \ times 2 ^ {nk}}} \ right ] \ ori}

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

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

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

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

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

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

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

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

{\ displaystyle + {(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}

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

{\ displaystyle - {(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}

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

{\ displaystyle + {(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}

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

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

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

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

{\ displaystyle + {(1/1175731200) \ times (35 / (nk-12)! - 5040 / (nk-10)! + 87264 / (nk-8)!)} \ times n ^ {nk-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}

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

{\ displaystyle - {(1/7054387200) \ times (5 / (nk-14)! - 1260 / (nk-12)! + 52704 / (nk-10)! - 186624 / (nk-8)!)} \ times n ^ {nk-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}

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

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

-...]

{\ displaystyle -...]}

{\ displaystyle -...]}

Sursa: André F. Labossière, 27-03-2006, A008275 (OEIS - Enciclopedia on-line a secvențelor întregi)

A doua specie

Numerele Stirling de al doilea fel $S(n,k)$ ${\ displaystyle S (n, k)}$ $S (n, k)$ (Capital S) sunt definite ca numărul de posibile k - partiții (adică partiții făcute din k seturi) ale unui set de cardinalitate n. Relațiile sunt valabile:

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

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

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

Și

Imaginea prezintă un exemplu de funcție surjectivă între două seturi: primul de cardinalitate n = 8 și al doilea de cardinalitate k = 3. Funcția a fost construită prin partiționarea setului de 8 în 3 blocuri și asocierea fiecărui bloc cu unul dintre cele 3 elemente ale celui de-al doilea set.

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

{\ displaystyle B_ {n} = \ sum _ {k = 1} ^ {n} S (n, k)}

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

unde B _n este nth numărul Bell .

Mai mult, este posibil să se obțină o formulă explicită pentru calcularea numerelor Stirling din a doua specie. De fapt, se poate observa că numărul funcțiilor surjective de la un set de cardinalitate n la una de cardinalitate k poate fi identificat prin partiționarea domeniului (de cardinalitate n) în blocuri k și asocierea la fiecare dintre aceste blocuri a unuia dintre k elemente din interval (și acest lucru se poate face în k! moduri). Astfel obținem formula:

S(n,k)={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{k \choose j}j^{n}

{\ displaystyle S (n, k) = {\ frac {1} {k!}} \ sum _ {j = 0} ^ {k} (- 1) ^ {kj} {k \ alege j} j ^ { n}}

{\ displaystyle S (n, k) = {\ frac {1} {k!}} \ sum _ {j = 0} ^ {k} (- 1) ^ {kj} {k \ alege j} j ^ { n}}

Ele sunt uneori scrise în notație alternativă, cum ar fi $S_{n}^{(k)}$ ${\ displaystyle S_ {n} ^ {(k)}}$ ${\ displaystyle S_ {n} ^ {(k)}}$ sau $\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$ ${\ displaystyle \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \}}$ $\ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \}$ . Ca și în cazul primei specii, ideea utilizării parantezelor, în analogie cu coeficientul binomial , a venit pentru prima dată la Jovan Karamata în 1935 și a fost ulterior susținută de Donald Knuth ; este, prin urmare, cunoscut sub numele de „notație Karamata”.

Tabelul valorilor

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

Relaţii

Numerele de primul și al doilea fel sunt legate de relații

\sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]\left\{{\begin{matrix}k\\m\end{matrix}}\right\}(-1)^{k}=(-1)^{n}\delta _{mn}

{\ displaystyle \ sum _ {k = 0} ^ {n} \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right] \ left \ {{\ begin {matrix} k \\ m \ end {matrix}} \ right \} (- 1) ^ {k} = (- 1) ^ {n} \ delta _ {mn}}

{\ displaystyle \ sum _ {k = 0} ^ {n} \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right] \ left \ {{\ begin {matrix} k \\ m \ end {matrix}} \ right \} (- 1) ^ {k} = (- 1) ^ {n} \ delta _ {mn}}

Și

\sum _{k=0}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}\left[{\begin{matrix}k\\m\end{matrix}}\right](-1)^{k}=(-1)^{n}\delta _{mn}

{\ displaystyle \ sum _ {k = 0} ^ {n} \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \} \ left [{\ begin {matrix} k \ \ m \ end {matrix}} \ right] (- 1) ^ {k} = (- 1) ^ {n} \ delta _ {mn}}

{\ displaystyle \ sum _ {k = 0} ^ {n} \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \} \ left [{\ begin {matrix} k \ \ m \ end {matrix}} \ right] (- 1) ^ {k} = (- 1) ^ {n} \ delta _ {mn}}

unde este $\delta _{jk}$ ${\ displaystyle \ delta _ {jk}}$ $\ delta _ {{jk}}$ este delta Kronecker . Aceste relații pot fi interpretate astfel: matricea $(-1)^{n-k}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$ ${\ displaystyle (-1) ^ {nk} \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \}}$ ${\ displaystyle (-1) ^ {n-k} \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \}}$ este inversul matricei $\left[{\begin{matrix}n\\k\end{matrix}}\right]$ ${\ displaystyle \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right]}$ ${\ displaystyle \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right]}$ , și în mod similar matricea $(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]$ ${\ displaystyle (-1) ^ {nk} \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right]}$ ${\ displaystyle (-1) ^ {n-k} \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right]}$ este inversul matricei $\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$ ${\ displaystyle \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \}}$ $\ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \}$ .