Стирлингов број

У математици, Стирлингови бројеви се јављају у многим проблемима у области комбинаторике. Добили су име по Џејмсу Стирлингу, који их је увео у 18. веку. Два различита скупа бројева носе ово име: Стирлингови бројеви прве врсте и Стирлингови бројеви друге врсте.

Користи се неколико различитих ознака за Стирлингове бројеве. Стирлингови бројеви прве врсте се обично обележавају малим латиничним словом ${\displaystyle s}$, док се Стирлингови бројеви друге врсте обележавају великим латиничним словом ${\displaystyle S}$. Стирлингови бројеви друге врсте су увек ненегативни за разлику од Стирлингових бројева прве врсте, који могу бити и негативни. Стандардне ознаке су:

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

за (означене) Стирлингове бројеве прве врсте и

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

за Стирлингове бројеве друге врсте.

Нотацију са угластим и витичастим заградама, као аналогију са биномним коефицијентима, 1935. године увео је Јован Карамата, а касније ју је подржао Доналд Кнут; ово се назива Караматина нотација.

Неозначени Стирлингови бројеви прве врсте, ${\displaystyle |s(n,k)|\,}$, означавају број пермутација ${\displaystyle n}$ елемената са ${\displaystyle k}$ дисјунктних циклуса, при чему се фиксна тачка рачуна као циклус дужине један.

Стирлингови бројеви прве врсте су коефицијенти у развоју

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

где је ${\displaystyle (x)_{n}}$ опадајући факторијел, тј.

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

Дефинишемо ${\displaystyle (x)_{0}=1.}$

Неки примери Стирлингових бројева прве врсте дати су у доњој табели, која почиње од нулте врсте и нулте колоне.

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

За Стирлингове бројеве прве врсте важи следећа рекурентна веза:

${\displaystyle s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k).}$

Стирлингови бројеви друге врсте, ${\displaystyle S(n,k)}$, означавају број партиција скупа од ${\displaystyle n}$ елемената на ${\displaystyle k}$ непразних подскупова. Збир

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

се назива ${\displaystyle n}$-ти Белов број.

Стирлингове бројеве друге врсте можемо да представимо помоћу опадајућег факторијела на следећи начин:

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

Све двочлане партиције скупа ${\displaystyle \{a,b,c,d\}}$ од ${\displaystyle n=4}$ елемента су:

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

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

Према томе, ${\displaystyle S_{4,2}=7}$.

Стирлингови бројеви прве и друге врсте се могу сматрати узајамним инверзима:

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

и

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

где је ${\displaystyle \delta _{jk}}$ Кронекерова делта функција. Ова два односа се могу посматрати као инверзи матрица. То јест, нека је ${\displaystyle s}$ доња троугаона матрица Стирлингових бројева прве врсте, тако да има елементе

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

Тада је инверз ове матрице ${\displaystyle S}$, доња троугаона матрица Стирлингових бројева друге врсте. Симболички, записује се

${\displaystyle s^{-1}=S}$

где су елементи ${\displaystyle S}$

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

Иако су ${\displaystyle s}$ и ${\displaystyle S}$ бесконачни, ово ради за коначне матрице простим посматрањем само Стирлингових бројева до неког ${\displaystyle N}$.

Абрамовиц и Стегун дају следеће симетричне формуле које дају однос Стирлингових бројева прве и друге врсте.

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

и

${\displaystyle \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].}$

• 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.
• Стирлингови бројеви прве врсте, s(n,k) на сајту PlanetMath.
• Стирлингови бројеви друге врсте, S(n,k) на сајту PlanetMath.
• Neil J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, s(n,k): A008275 & A008276, S(n,k): A008277 & A008278.
• „Stirling numbers of the first kind”. 10 (53). 1956: 35. ISSN 0891-6837. , "27 leaves reproduced from typewritten manuscript on deposit in the UMT File", Mathematical Tables and Other Aids to Computation, 10  (53):  37-38 , January 1956(Reviews and Descriptions of Tables and Books, 7[I]).}-
• Victor Adamchik, "„On Stirling Numbers and Euler Sums” (PDF).  Архивирано на веб-сајту Wayback Machine (16. јун 2009)", Adamchik, Victor (1997). „On Stirling Numbers and Euler Sums”. Journal of Computational and Applied Mathematics. 79 (1997): 119—130. doi:10.1016/S0377-0427(96)00167-7. .
• Benjamin, Arthur T.; Preston, Gregory O.; Quinn, Jennifer J. (2002). „A Stirling Encounter with Harmonic Numbers” (PDF). Mathematics Magazine. 75 (2): 95—103. doi:10.1080/0025570X.2002.11953110. Архивирано из оригинала (PDF) 17. 06. 2009. г. Приступљено 05. 04. 2020. , .}-
• 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” (PDF).  Архивирано на веб-сајту Wayback Machine (17. јун 2009), 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.