КОМБИНАТО́РНЫЕ ЧИ́СЛА И МНОГОЧЛЕ́НЫ

КОМБИНАТО́РНЫЕ ЧИ́СЛА И МНОГО­ЧЛЕ́­НЫ, об­щее наз­ва­ние спе­ци­аль­ных чи­сел и мно­го­чле­нов, ко­то­рые иг­ра­ют важ­ную роль в ре­ше­нии ком­би­на­тор­ных за­дач. Как пра­ви­ло, ком­би­на­тор­ные чис­ла име­ют на­гляд­ную ком­би­на­тор­ную ин­тер­пре­та­цию (за­час­тую не един­ст­вен­ную), вы­ра­жае­мую в тер­ми­нах чис­ла спо­со­бов вы­бо­ра и рас­по­ло­же­ния эле­мен­тов не­ко­то­ро­го, обыч­но ко­неч­но­го, мно­же­ст­ва, при­во­дя­щих к кон­фи­гу­ра­ци­ям дан­но­го клас­са или чис­ла объ­ек­тов из не­ко­то­ро­го мно­же­ст­ва объ­ек­тов, об­ла­даю­щих тем или иным вы­де­лен­ным свой­ст­вом.

Про­стей­ши­ми при­ме­ра­ми ком­би­на­тор­ных чи­сел яв­ля­ют­ся чис­ла со­че­та­ний, раз­ме­ще­ний и пе­ре­ста­но­вок. Ес­ли име­ет­ся мно­же­ст­во из $N$ разл. эле­мен­тов, то его под­мно­же­ст­ва на­зы­ва­ют­ся со­че­та­ния­ми, чис­ло разл. со­че­та­ний раз­ме­ра $k$ рав­но $$C_N^k=\big(\frac{N}{k}\big)=\frac{N(N-1) \ldots(N-k+1)}{k!}=\frac{N!}{k!(N-k)!}.$$

Чис­ла $\big(\frac{N}{k}\big)$, $k=0,1,...,N$, на­зы­ва­ют бино­ми­аль­ны­ми ко­эф­фи­ци­ен­та­ми, по­сколь­ку они вхо­дят в фор­му­лу Нью­то­на би­но­ма

. Упо­ря­до­чен­ные на­бо­ры из разл. эле­мен­тов мно­же­ст­ва $N$ на­зы­ва­ют­ся раз­ме­ще­ния­ми, чис­ло разл. раз­ме­ще­ний раз­ме­ра $k$ рав­но $$A_N^k=k!C_N^k=N(N-1)\ldots(N-k+1).$$

В слу­чае $N=k$ раз­ме­ще­ния на­зы­ва­ют­ся пе­ре­ста­нов­ка­ми, чис­ло всех пе­ре­ста­но­вок из $N$ эле­мен­тов рав­но $PN=N!,$ где $N!=N(N-1)...2·1$. Со­че­та­ния, раз­ме­ще­ния и пе­ре­ста­нов­ки ис­поль­зу­ют­ся в разл. раз­де­лах ма­те­ма­ти­ки.

Ес­ли до­пус­ка­ют­ся по­вто­ре­ния эле­мен­тов, то чис­ло всех со­че­та­ний раз­ме­ра $k$ из $N$ разл. эле­мен­тов рав­но $C_{N-k+1}^k$, а чис­ло всех упо­ря­до­чен­ных на­бо­ров раз­ме­ра $k$ рав­но $N^k$. Эти чис­ла ис­поль­зу­ют при на­хо­ж­де­нии ве­ро­ят­но­стей разл. со­бы­тий при клас­сич. оп­ре­де­ле­нии ве­ро­ят­но­сти (см. Ве­ро­ят­но­стей тео­рия

). Напр., ес­ли име­ет­ся ур­на с $N$ ша­ра­ми, за­ну­ме­ро­ван­ны­ми чис­ла­ми $1,2,...,N$, при­чём ша­ры с но­ме­ра­ми $1,2,...,M$ бе­ло­го цве­та, а ос­таль­ные – чёр­но­го, то ве­ро­ят­ность по­лу­чить ров­но $m$ бе­лых ша­ров при слу­чай­ном вы­бо­ре из ур­ны $n$ ша­ров рав­на
  $$\frac{C_n^mA_M^mA_{N-M}^{n-m}}{A_N^n}=\frac{C_n^mC_{N-M}^{n-m}}{C_N^n},$$ ес­ли вы­бор про­из­во­дит­ся без воз­вра­ще­ния ша­ров, и рав­на $$\frac{C_n^mM^m(N-M)^{n-m}}{N^n}=C_n^m\bigg(\frac{M}{N}\bigg)^m\bigg(1-\frac{M}{N}\bigg)^{n-m}$$ при вы­бо­ре с воз­вра­ще­ни­ем.

Из чис­ла бо­лее спе­ци­аль­ных ком­би­на­тор­ных чи­сел наи­бо­лее час­то ис­поль­зу­ют­ся т. н. чис­ла Ка­та­ла­на $$C_n=\frac{1}{n+1}C_{2n}^n;$$ чис­ла Мор­га­на $$\Delta_k^n=\Delta^nx^k\big|_{x=0}=\sum_{j=0}^n(-1)^jC_k^j(k-j)^n,$$ где $Δ$ – опе­ра­тор раз­но­сти $Δf(x)=f(x+1)-f(x)$; чис­ла Стир­лин­га $S(n,k)$ и $σ(n,k)$ со­от­вет­ст­вен­но 1-го и 2-го ро­да; чис­ла Бел­ла $$B_n=\sum_{k=0}^nS(n,k).$$

Все эти чис­ла, как пра­ви­ло, име­ют на­гляд­ные ком­би­на­тор­ные ин­тер­пре­та­ции. Так, напр., чис­ло Ка­та­ла­на $C_n$ рав­но чис­лу век­то­ров $(\varepsilon_1,...,\varepsilon_{2n}), \varepsilon_i=±1, i=1,...,2_n$, та­ких, что $\sum_{i=1}^k \varepsilon_i\geq0,$ $k=1,...,$ $2n-1$, $\sum_{i=1}^{2n}\varepsilon_i=0$; чис­ло Морга­на $\Delta_k^n$ рав­но чис­лу ото­бра­же­ний $f$ мно­жест­ва $A$ из $k$ эле­мен­тов на мно­жест­во $B$ из $n$ эле­мен­тов, т. е. та­ких ото­бра­же­ний, что $f(A)=f(B);$ чис­ло Бел­ла $B_n$ есть чис­ло разл. раз­бие­ний мно­же­ст­ва из $n$ эле­мен­тов на не­пе­ре­се­каю­щие­ся под­мно­же­ст­ва.

При ис­сле­до­ва­нии свойств ком­би­на­тор­ных чи­сел ши­ро­ко ис­поль­зу­ют про­из­во­дя­щие функ­ции

, ре­кур­рент­ные со­от­но­ше­ния

 >>

и ко­неч­но-раз­но­ст­ные урав­не­ния. Во мно­гих слу­ча­ях на рас­смат­ри­вае­мом мно­же­ст­ве объ­ек­тов уда­ёт­ся по­стро­ить под­хо­дя­щую ве­ро­ят­но­ст­ную мо­дель и тем са­мым ком­би­на­тор­ную за­да­чу пе­ре­чис­ли­тель­но­го ха­рак­те­ра сфор­му­ли­ро­вать как за­да­чу изу­че­ния рас­пре­де­ле­ния ве­ро­ят­но­стей со­от­вет­ст­вую­щей слу­чай­ной ве­ли­чи­ны. Та­кая ин­тер­пре­та­ция да­ёт воз­мож­ность при­ме­нять при изу­че­нии ком­би­на­тор­ных чи­сел разл. ме­то­ды тео­рии ве­ро­ят­но­стей.

Под ком­би­на­тор­ны­ми мно­го­чле­на­ми по­ни­ма­ют про­из­во­дя­щие функ­ции ком­би­на­тор­ных чи­сел или про­из­во­дя­щие функ­ции этих чи­сел с не­ко­то­ры­ми ве­са­ми. Напр., про­из­во­дя­щей функ­ци­ей чи­сел со­че­та­ний $C_N^k$, $k=0,1,...,N,$ яв­ля­ет­ся би­ном Нью­то­на $$\sum_{k=0}^NC_N^kx^k=(1+x)^N;$$ для чи­сел Стир­лин­га $$\sum_{k=0}^nS(n,k)x^k=x(x-1)\ldots(x-n+1),\\ \sum_{k=0}^n \sigma(n,k)x_k=x^n,$$ где $(x)_k=x(x-1)\ldots(x-k+1), k=0,1, \ldots, n.$