Изменения

'''Числа Стирлинга первого рода''' (англ. ''Stirling numbers of the first kind'') — количество [[Комбинаторные объекты|перестановок]] порядка <texdpi="130">n</tex> с <texdpi="130">k</tex> [[Действие перестановки на набор из элементов, представление в виде циклов|циклами]](или число способов посадить <tex>n</tex> человек с номерами на майках за <tex>k</tex> одинаковых круглых столов, чтобы за каждым столом кто-то сидел). Числа Стирлинга 1-го I рода обозначаются как <texdpi="130">s(n,k)</tex> или <texdpi="170">\left[{n\atop k}\right]</tex>. Числа Стирлинга используются в задачах(например, олимпиадных), где одной из подзадач является нахождение количества перестановок порядка <tex>n</tex> с <tex>k</tex> циклами.

<texdpi="130">s(4,2)=11</tex>

Существует <tex> 11 </tex> разбиений перестановки из четырех элементов на два цикла:

<texdpi="130">(1)(2; 4; 3) \qquad (1)(2; 3; 4)</tex> <br\><tex>(2)(1; 4; 3) \qquad (2)(1; 3; 4)</tex> <br\><tex>(3)(1; 4; 2) \qquad (3)(1; 2; 4)</tex> <br\><tex>(4)(1; 3; 2) \qquad (4)(1; 2; 3)</tex> <br\><tex>(1; 2)(3; 4)</tex> <br\><tex>(1; 4)(2; 3)</tex> <br\><tex>(1; 3)(2; 4)</tex> <br\>

Заметим, что перестановки <texdpi="130">(1)(2; 3; 4)</tex> и <tex>(1)(2; 4; 3)</tex> считаются различными, так как подмножество <tex>\qquad (2; 3; 4)</tex> невозможно получить ни из подмножества <tex>(1)</tex>, ни из подмножества <tex>(2; 3; 4; 3)</tex> с помощью циклического сдвига элементов.

==Соотношения==Равносильное определение получается, если числа Стирлинга задать как коэффициенты в разложении: <texdpi="130">(x3)(1; 4; 2)^{n} = \sum_{k=0}^n sqquad (3)(n,k1; 2; 4) x^k,</tex>

Следовательно, числа Стирлинга 1-го рода позволяют перейти от базиса <texdpi="130">(x4)^{(1},; 3; 2) \qquad (x4)^{2},(x)^{3} \cdots</tex> к базису <tex>1,x,x^; 2 \cdots; 3)</tex>

Здесь <texdpi="130">(x1; 2)(3; 4)^{n}</tex> обозначим как возрастающие факториальные степени:

:<texdpi="130">(x)^{n}=x(x+1; 4)(x+2; 3)\cdots(x+n-1).</tex>

Для ясности рассмотрим пример, при котором <texdpi="130">n=(1; 3)(2; 4)</tex>::Заметим, что разбиения <texdpi="130">(x)^{3}=x(x+1)(x+2; 3; 4)=1 \cdot x^3 + 3 \cdot x^2 + 2 \cdot x</tex>, здесь коэффициенты при и <texdpi="130">x^k</tex> — это <tex>s(1)(2; 4; 3,k)</tex>считаются различными, то есть::так как цикл <texdpi="130">s(2; 3,3; 4)=1</tex> :невозможно получить ни из подмножества <texdpi="130">s(3,21)=3</tex> :, ни из подмножества <texdpi="130">s(2; 4; 3,1)=2</tex> с помощью циклического сдвига элементов.

Числа Стирлинга первого рода задаются рекуррентным соотношением::<tex> s(0, 0) = 1 </tex>,:<tex> s(n, 0) = 0 </tex>, для <tex>n > 0</tex>,:<tex> s(0, k) = 0 </tex>, для <tex>k > 0</tex>. Выведем рекуррентную формулу для вычисления чисел Стирлинга первого рода. Каждое представление <texdpi="130">n</tex> элементов в виде <texdpi="130">k</tex> циклов либо помещает последний элемент(<texdpi="130">n-</tex>ый) в отдельный цикл <texdpi="130">s(n-1, k-1)</tex> способами, либо вставляет этот элемент в одно из <texdpi="130">s(n-1, k)</tex> циклических представлений первых <texdpi="130">(n-1)</tex> элементов. В последнем случае существует <texdpi="130">(n-1)</tex> различных способов подобной вставки. Например, при вставке элемента <tex>4</tex> в цикл <tex>[(1;2;3])</tex> можно получить только <tex> 3 </tex> разных цикла: <texdpi="130">[(1;2;3;4]), [(1;2;4;3]), [(1;4;2;3])</tex>. Таким образом, рекуррентность имеет вид::<p><texdpi="130">s(n, k) =\left \{\begin{array}{ll} s(0, 0) = 1, \\s(n, 0) = 0, & n > 0 \\s(0, k) = 0, & k >0 \\s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k), & n,k > 0 \end{array} \right.</tex></p>

Рассмотрим <texdpi="130">s(n+1,k)</tex>:

:<texdpi="130">(x)^{n+1}=x(x+1)(x+2)\cdotsdots (x+n-1)(x+n) = n(x)^{n}+x(x)^{n}</tex>

Заметим, что коэффициенты <texdpi="130">(x)^{n+1}</tex> — это <texdpi="130">s(n+1,k)</tex>

Аналогично можно сказать, что коэффициенты <texdpi="130">n(x)^{n}</tex> — это <texdpi="130">ns(n,k)</tex>

А коэффициенты <texdpi="130">x(x)^{n}</tex> — это <texdpi="130">s(n,k-1)</tex>, так как степени при <texdpi="130">x</tex> увеличатся на <tex> 1</tex>, а коэффициенты при этом не изменятся.

Так как левая и правая части равенства равны как полиномы, то равны и коэффициенты перед <texdpi="130">x^k</tex>, следовательно справедливо равенство::<texdpi="130">s(n+1,k)=ns(n,k)+s(n,k-1)</tex> или <texdpi="130">s(n,k)=(n-1)s(n-1,k)+ s(n-1,k-1)</tex>

==Числа Стирлинга для малых N и K= Таблица значений ===Ниже представлены некоторые Найдём числовые значения чисел Стирлинга<tex>s(n, которые легко подсчитать, используя рекуррентные соотношенияk)</tex> для малых <tex>n</tex> и <tex>k</tex>.

{|borderclass="1wikitable"

!width="20"| n\k!width="40"| 0!width="40"| 1!width="40"| 2!width="40"| 3!width="40"| 4!width="40"| 5!width="40"| 6!width="40"| 7!width="40"| 8!width="40"| 9

| ! 0

| ! 1

| ! 2

| ! 3

| ! 4

| ! 5

| ! 6

| ! 7

| ! 8

| ! 9

==ТождестваПрименение== Равносильное определение получается, включающие если числа Стирлинга первого задать как коэффициенты в разложении: <tex dpi="130">(x)^{n} = \sum\limits_{k=1}^n s(n,k) x^k,</tex> Следовательно, числа Стирлинга I родапозволяют перейти от базиса <tex dpi="130">(x)^{1},(x)^{2},(x)^{3} \dots </tex> к базису <tex dpi="130">1,x,x^2 \dots </tex> (одно из основных применений) Здесь <tex dpi="130">(x)^{n}</tex> обозначим как возрастающие факториальные степени или символ Похгаммера<ref> [http://ru.wikipedia.org/wiki/Символ_Похгаммера Википедия {{---}} Символ Похгаммера]</ref>:

Как уже упоминалось ранее:<tex dpi="130">(x)^{n}=x(x+1)(x+2) \dots (x+n-1).</tex> Для ясности рассмотрим пример, при котором <tex>n=3</tex>::<tex dpi="130">(x)^{3}=x(x+1)(x+2)=1 \cdot x^3 + 3 \cdot x^2 + 2 \cdot x</tex>, здесь коэффициенты при <tex dpi="130">x^k</tex> — это <tex dpi="130">s(3,k)</tex>, то есть::<tex dpi="130">s(3,3)=1</tex> :<tex dpi="130">s(3,2)=3</tex> :<tex dpi="130">s(3,1)=2</tex> {{Теорема|statement=Числа Стирлинга I рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней <tex dpi="130"> \forall n \in \mathbb{N} : \quad (x)^{n} = \sum\limits_{k=1}^n s(n,k) x^k</tex>.|proof=Индукция по <tex>n</tex>: '''База''': Для <tex>n = 1</tex>, <tex> (x)^{1} = x^{1} </tex> {{---}} очевидно. '''Переход''': Учитывая, что <tex> (x)^{n} = (x)^{n-1} \cdot (x+n-1) </tex> имеем: <tex> (x)^{n} = (x)^{n-1} \cdot (x+n-1) = x \cdot (x)^{n-1} + (n-1) \cdot (x)^{n-1} = </tex> <tex> \sum\limits_{k=1}^{n-1} s(n-1,k) x^{k+1} + \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) </tex>, Введём <tex> t = k + 1 </tex> для первой суммы <tex>\sum\limits_{t=2}^{n} s(n-1,t-1) x^{t} + \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) </tex> При <tex> t = 1 , \quad \sum\limits_{t=2}^{n} s(n-1,t-1) x^{t} = 0 </tex>, При <tex> k = n , \quad \sum\limits_{k=1}^{n-1} s(n-1,k) x^k \cdot (n-1) = 0 </tex>. Следовательно, мы можем представить выражение в виде одной суммы:

:<tex>\sum\limits_{k=1}^{n} (s(0n-1,0k-1)+(n-1)s(n-1,k)) \cdot x^{k} = \sum\limits_{k=1}^n s(n,k) x^k</tex>

Как уже упоминалось ранее:<tex>s(n,1)=(n-1)!</tex>

:#<tex dpi = "160">\left[{0\atop 0}\right]=1</tex>s(#<tex dpi = "160">\left[{n\atop 0}\right]=\left[{0\atop k}\right]=0</tex>,в общем случае <tex dpi = "160">\left[{n)\atop k}\right]=10</tex>, если <tex>k > n</tex>

Также:<tex>s(n,n-1)={n \choose 2}</tex>

#<tex dpi="160">\left[{n\atop 1}\right]=(n-1)!</tex>#:Зафиксируем один элемент, и переставим оставшиеся всеми возможными способами. Повторений не будет, так как чтобы зафиксированный элемент совпал, нужно сдвинуть всю перестановку на <tex dpi = "160">n</tex>s(, но тогда мы получим исходную перестановку.#<tex dpi="160">\left[{n\atop n}\right]=1</tex>,очевидно#<tex dpi="160">\left[{n\atop n-1}\right]={n \choose 2}</tex>#:Разбить <tex dpi = "160">n</tex> элементов на <tex dpi = "160">n-1</tex> множество можно только одним образом, а именно на множества состоящие из одного элемента и одно множество состоящее из двух. Так как нас интересуют только циклы, получаем выборку двух элементов из всех элементов(множество состоящее из двух элементов всегда является циклом).#<tex dpi="160">\left[{n\atop n-2}\right]=\frac{1}{4} (3n-1) {n \choose 3}</tex>#:По аналогии с предыдущим тождеством получаем, что нас интересуют виды конкатенации множеств <tex dpi = "160">((n-4)*1+2+2), ((n-3)*1+3)</tex>. Тогда искомая формула получается упрощением выражения <tex dpi = "160">2! \times {n \choose 3} + \frac{{n \choose 2} \times {n-2 \choose 2}}{2!}</tex>, которая учитывает фиксацию элемента в трехэлементном множестве и повторения двухэлементных.#<tex dpi="160">\left[{n\atop n-3}\right]={n \choose 2}{n \choose 4}</tex>#:Аналогично, учитываем только интересующие нас множества и получаем формулу <tex dpi = "160">2! \times {n \choose 2}{n-2 \choose 3} + \frac{{n \choose 2} \times {n-2 \choose 2} \times {n-4 \choose 2}}{3!} + 3! \times {n \choose 4}={n \choose 2}{n \choose 4}</tex>.

Для целых, положительных <tex>l,m,n:</tex>#<tex dpi="160">\left[{n+1\atop m+1}\right]=\sum\limits_{k=1}^n \left[{n\atop k}\right] {k \choose m}=n! \sum\limits_{k=0}^n \frac{\left[{k\atop m}\right]}{k!} </tex>#:Второе равенство доказывается путем постепенного спуска вниз: #:<texdpi="160">s\left[{n+1\atop m+1}\right]=\left[{n\atop m}\right] + n \cdot \left[{n\atop m+1}\right]=\left[{n\atop m}\right] + n \cdot \left(\left[{n-1\atop m}\right] + (n-1) \cdot \left[{n-1\atop m+1}\right]\right)=...=\sum\limits_{k=0}^n \left[{k\atop m}\right]\frac{n!}{k!}=n! \sum\limits_{k=0}^n \frac{\left[{k\atop m}\right]}{k!}</tex>#:Чтобы доказать первое,будем использовать биекцию(из прошлого раздела) в факториальные степени, а также формулу <tex dpi="160">(x)_{n+1} = x \cdot (x-31)_n \;</tex>.#:Разложим наше искомое выражение, используя формулу для факториальных степеней, и применив бином Ньютона для второго множителя. Тогда: <tex dpi="160">(x)_{n+1}=\sum_{i=0}^{n}\sum_{k=0}^{i} \left[{n\atop i}\right]\binom{i}{k} x^{k+1}</tex>. Немного преобразовав, получим: <tex dpi="160">(x)_{n+1}=\sum_{k=0}^{n}\sum_{i=k}^{n} \left[{n\atop i}\right]\binom{i}{k} x^{k+1} \;</tex>#:C другой стороны: <tex dpi="160">(x)_{n+1}=\sum_{k=0}^{n+1} \left[{n+1\atop k}\right] x^k =\sum_{k=0}^{n} \left[{n +1\atop k+1}\right] x^{k+1}</tex>#:Приравниваем эти два выражения и получаем искомую формулу.#<tex dpi="160">\left[{n\atop m}\right]=\sum\limits_{k=1}^n \left[{n+1\atop k+1}\right] {k \choose m} (-1)^{m-k} </tex>#:Доказательство аналогично предыдущему с учетом знакочередования в убывающих факториальных степенях.#<tex dpi="160">\left[{m+n+1\atop m}\right]=\sum\limits_{k=0}^m (n+k) \left[{n+k\atop k}\right]</tex>#:Постепенно раскладываем и получаем искомую формулу:#:<tex dpi="160">\left[{m+n+1\atop m}\right]=\left[{m+n\atop m-1}\right]+\left[{m+n\atop m}\right]\cdot(m+n)=\left[{m+n-1\atop m-2}\right]+\left[{m+n\atop m}\right]\cdot(m+n)+\left[{m+n-1\atop m-1}\right]\cdot(m+n-1)=...=\sum\limits_{k=0}^m (n +k) \left[{n+k\choose 4atop k}\right]</tex>

Если числа Стирлинга 1-го I рода позволяют перейти от базиса <texdpi="130">(x)^{1},(x)^{2},(x)^{3} \cdotsdots </tex> к базису <texdpi="130">1,x,x^2 \cdotsdots </tex>,

то [[Числа Стирлинга второго рода|числа Стирлинга 2-го II рода ]] играют обратную роль и позволяют перейти от базиса <texdpi="130">1,x,x^2 \cdotsdots </tex> к базису <texdpi="130">(x)^{1},(x)^{2},(x)^{3} \cdotsdots </tex>.

:<p>  <texdpi="130">\sum_sum\limits_{k=1}^n S(n,k) s(k,m) (-1)^{k-m} = \left \{\begin{array}{ll} 1</tex>, если <tex>& n=m \\0, & \text{otherwise} \end{array} \right.</tex>, иначе <tex>0</texp> 

==Ссылки==* [http://ruen.wikipedia.org/wiki/Числа_Стирлинга_первого_рода Числа Стирлинга первого родаStirling_numbers_of_the_first_kind Wikipedia {{---}} Stirling numbers of the first kind]

* [httpGraham, Knuth, and Patashnik://enConcrete Mathematics Second Edition 1994, ISBN 0-201-55802-5 {{---}} 257-267 с.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind Stirling numbers of the first kind]

== Литература ==* Graham, KnuthВ. Липский: Комбинаторика для программистов 1988, and Patashnik: Concrete Mathematics Second Edition 1994 ISBN 05-20103-55802000979-5{{---}} 49-50 с.