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

Из Википедије, слободне енциклопедије

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

(са малим словом s) означавају број пермутација n елемената са k дисјунктних циклуса.

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

(x)_{(n)} = \sum_{k=1}^n s(n,k) x^k.

где је (x)_{(n)} доњи факторијел

(x)_{(n)}=x(x-1)(x-2)\cdots(x-n+1).
Види главни чланак Стирлингови бројеви прве врсте за више информација.

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

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

B_n=\sum_{k=1}^n S(n,k)

је n-ти Белов број. Ако је

(x)_n=x(x-1)(x-2)\cdots(x-n+1)

(специјални случај, (x)0 = 1 јер се ради о празном производу) доњи факторијел, можемо да карактеризујемо Стирлингове бројеве друге врсте са

\sum_{k=0}^n S(n,k)(x)_k=x^n.

(Може да буде збуњујуће то што нотација коју комбинаторичари користе за доњи факторијел одговара нотацији која се користи у специјалним функцијама за горњи факторијел; види Почхамеров симбол.)

Види главни чланак Стирлингови бројеви друге врсте за више информација.

Инверзни однос[уреди]

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

\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].

Литература[уреди]