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

У математици, Стирлингови бројеви се јављају у многим проблемима у области комбинаторике. Добили су име по Џејмсу Стирлингу, који их је увео у 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].}$

Литература

• Стирлингови бројеви прве врсте, на сајту .
• Стирлингови бројеви друге врсте, на сајту .
• „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(Reviews and Descriptions of Tables and Books, 7[I]).}-
• 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., .}-