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

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

Нотација

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

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

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

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

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

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

Стирлингови бројеви прве врсте

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

Инверзни однос

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

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

и

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

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

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

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

$s^{-1}=S$

где су елементи $S$

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

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

Симетричне формуле

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

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

и

$\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.
• 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.