Stirlingov broj

U matematici, Stirlingovi brojevi se javljaju u mnogim problemima u oblasti kombinatorike. Dobili su ime po Džejmsu Stirlingu, koji ih je uveo u 18. veku. Dva različita skupa brojeva nose ovo ime: Stirlingovi brojevi prve vrste i Stirlingovi brojevi druge vrste.

Notacija

Koristi se nekoliko različitih oznaka za Stirlingove brojeve. Stirlingovi brojevi prve vrste se obično obeležavaju malim latiničnim slovom $s$, dok se Stirlingovi brojevi druge vrste obeležavaju velikim latiničnim slovom $S$. Stirlingovi brojevi druge vrste su uvek nenegativni za razliku od Stirlingovih brojeva prve vrste, koji mogu biti i negativni. Standardne oznake su:

$s(n,k)=\left[{\begin{matrix}n\\k\end{matrix}}\right].$

za (označene) Stirlingove brojeve prve vrste i

$S(n,k)=S_{n}^{(k)}=\left\{{\begin{matrix}n\\k\end{matrix}}\right\}.$

za Stirlingove brojeve druge vrste.

Notaciju sa uglastim i vitičastim zagradama, kao analogiju sa binomnim koeficijentima, 1935. godine uveo je Jovan Karamata, a kasnije ju je podržao Donald Knut; ovo se naziva Karamatina notacija.

Stirlingovi brojevi prve vrste

Neoznačeni Stirlingovi brojevi prve vrste, $|s(n,k)|\,$, označavaju broj permutacija $n$ elemenata sa $k$ disjunktnih ciklusa, pri čemu se fiksna tačka računa kao ciklus dužine jedan.

Stirlingovi brojevi prve vrste su koeficijenti u razvoju

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

gde je $(x)_{n}$ opadajući faktorijel, tj.

$(x)_{n}=x(x-1)(x-2)\cdots (x-n+1).$

Definišemo $(x)_{0}=1.$

Neki primeri Stirlingovih brojeva prve vrste dati su u donjoj tabeli, koja počinje od nulte vrste i nulte kolone.

${\begin{array}{rrrrrrr}1&&&&&&\\0&1&&&&&\\0&-1&1&&&&\\0&2&-3&1&&&\\0&-6&11&-6&1&&\\0&24&-50&35&-10&1&\\0&-120&274&-225&85&-15&1\\\end{array}}$

Za Stirlingove brojeve prve vrste važi sledeća rekurentna veza:

$s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k).$

Stirlingovi brojevi druge vrste

Stirlingovi brojevi druge vrste, $S(n,k)$, označavaju broj particija skupa od $n$ elemenata na $k$ nepraznih podskupova. Zbir

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

se naziva $n$-ti Belov broj.

Stirlingove brojeve druge vrste možemo da predstavimo pomoću opadajućeg faktorijela na sledeći način:

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

Primer

Sve dvočlane particije skupa $\{a,b,c,d\}$ od $n=4$ elementa su:

$\{\{a,b\},\{c,d\}\},\ \{\{a,c\},\{b,d\}\},\ \{\{a,d\},\{b,c\}\},$

$\{\{a,b,c\},\{d\}\},\ \{\{a,b,d\},\{c\}\},\ \{\{a,c,d\},\{b\}\},\ \{\{b,c,d\},\{a\}\}.$

Prema tome, $S_{4,2}=7$.

Inverzni odnos

Stirlingovi brojevi prve i druge vrste se mogu smatrati uzajamnim inverzima:

$\sum _{n=0}^{\max\{j,k\}}\left[{\begin{matrix}n\\j\end{matrix}}\right]\left\{{\begin{matrix}k\\n\end{matrix}}\right\}=\delta _{jk}$

i

$\sum _{n=0}^{\max\{j,k\}}\left\{{\begin{matrix}n\\j\end{matrix}}\right\}\left[{\begin{matrix}k\\n\end{matrix}}\right]=\delta _{jk}$

gde je $\delta _{jk}$ Kronekerova delta funkcija. Ova dva odnosa se mogu posmatrati kao inverzi matrica. To jest, neka je $s$ donja trougaona matrica Stirlingovih brojeva prve vrste, tako da ima elemente

$[s]_{nk}=s(n,k)=\left[{\begin{matrix}n\\k\end{matrix}}\right]$

Tada je inverz ove matrice $S$, donja trougaona matrica Stirlingovih brojeva druge vrste. Simbolički, zapisuje se

$s^{-1}=S$

gde su elementi $S$

$[S]_{nk}=S(n,k)=\left\{{\begin{matrix}n\\k\end{matrix}}\right\}.$

Iako su $s$ i $S$ beskonačni, ovo radi za konačne matrice prostim posmatranjem samo Stirlingovih brojeva do nekog $N$.

Simetrične formule

Abramovic i Stegun daju sledeće simetrične formule koje daju odnos Stirlingovih brojeva prve i druge vrste.

$\left[{\begin{matrix}n\\k\end{matrix}}\right]=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}\left\{{\begin{matrix}n-k+j\\j\end{matrix}}\right\}$

i

$\left\{{\begin{matrix}n\\k\end{matrix}}\right\}=\sum _{j=0}^{n-k}(-1)^{j}{n-1+j \choose n-k+j}{2n-k \choose n-k-j}\left[{\begin{matrix}n-k+j\\j\end{matrix}}\right].$

Literatura

• M. Abramowitz, I. Stegun (Eds.). Stirling Numbers of the First Kind., §24.1.3 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, pp. 824, 1972.
• D.E. Knuth, Two notes on notation Архивирано на сајту Wayback Machine (6. мај 2021) (TeX source).
• Louis Comtet, "Valeur de s(n, k)", Analyse combinatoire, Tome second (page 51), Presses universitaires de France, 1970.
• Louis Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Reidel Publishing Company, Dordrecht-Holland/Boston-U.S.A., 1974.
• Stirlingovi brojevi prve vrste, s(n,k) na sajtu PlanetMath.
• Stirlingovi brojevi druge vrste, S(n,k) na sajtu PlanetMath.
• Neil J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, s(n,k): A008275 & A008276, S(n,k): A008277 & A008278.
• Francis L. Miksa (1901-1975), Stirling numbers of the first kind, "27 leaves reproduced from typewritten manuscript on deposit in the UMT File", Mathematical Tables and Other Aids to Computation, vol. 10, no. 53, January 1956, pp. 37-38 (Reviews and Descriptions of Tables and Books, 7[I]).
• Victor Adamchik, "On Stirling Numbers and Euler Sums Архивирано на сајту Wayback Machine (16. јун 2009)", Journal of Computational and Applied Mathematics 79 (1997), pp. 119–130.
• Arthur T. Benjamin, Gregory O. Preston, Jennifer J. Quinn, A Stirling Encounter with Harmonic Numbers, (2002) Mathematics Magazine, 75 (2) pp 95-103.
• J. M. Sixdeniers, K. A. Penson, A. I. Solomon, Extended Bell and Stirling Numbers From Hypergeometric Exponentiation (2001), Journal of Integer Sequences, 4, Article 01.1.4.
• Hsien-Kuei Hwang, Asymptotic Expansions for the Stirling Numbers of the First Kind (1994).
• John J. O'Connor, Edmund F. Robertson, James Stirling (1692-1770), (September 1998).
• Dragoslav S. Mitrinović, Sur les nombres de Stirling de première espèce et les polynômes de Stirling, AMS 11B73_05A19, Publications de la Faculté d'Electrotechnique de l'Université de Belgrade, Série Mathématiques et Physique (ISSN 0522-8441), no. 23, 1959 (5.V.1959), pp. 1-20.