Какво трябва да знаем?

Числа на Стирлинг - урок или лекция

Станчо Павлов

Дълго се заблуждавах,
че животът ми е безсмислен.
Докато не научих,
че като дишам - храня растенията.
Ще ги храня и после!
Виц от вестниците

Възходяща и низходяща n-степен на z

Тези n-ти степени се дефинират така:
Низходяща n-та степен на z:
zn = z(z-1)(z-2)...(z-n+1)

Това определение, разбира се, има връзка с комбинаториката:
Броят на инективните изображения от множество, състоящо се от k елемента в множество от n елемента е равен на низходящата k-та степен на n ( nk ).
nk е броят на редиците от k различни елементи на множество, съдържащо n елемента.
Дефинира се и възходяща, n-та степен на z:
zn = z(z+1)(z+2)...(z+n-1)
( Поради невъзможност да изобразя горна черта над символа, съм използвал този междинен вариант.)
Възходящата n-та степен също има връзка с комбинаториката:
Определение
Нека K е множество от k предмета, които трябва да се подредеят в n рафта, като някои от тях може да са празни.
Броят на начините, по които може да стане това са zn.

Числа на Стирлинг от първи род

Коефициентите на полинома, изразяващ низходящата n-та степен на z се наричат числа на Стирлинг от първи род и се означават с Означения на числата на Стирлинг оп първи род -- StNumbIKind1         s(n, k) е коефициентът пред k-тата степен на z.     Абсолютните им стойности се наричат беззнакови числа на Стирлинг от първи род. Попълнете таблица, съдържаща възходящите и низходящи n-степени на z за стойности на n от 0 до 5. ?
Предложете схема, подобна на схемата Схема за получаване на числата от триъгълника на Паскал – Pascal1 при триъгълника на Паскал за получаване на новия ред от предходния за числата на Стирлинг от първи род. ?
Алгоритъм за получаване на числата на Стирлинг от първи род --AlgStIKind1
Числата на Стирлинг от първи род, получени по предложената схема
Корените на полинома zn са целите числа от 0 до n-1.
От формулите на Виет следва, че (-1)ks(n, n-k) е равно на сумата от произведенията на числата от k елементните под-множества на множеството {0, 1, 2, ... n-1}.

Връзка между числата на Стирлинг от първи род и комбинаториката

Всяка пермутация може да се представи като произведение от цикли. При това представяне ще отчитаме и циклите, съдържащи само един елемен, който разбира се, е неподвижен за пермутацията. Например за пермутацията
Пермутация от седми ред--Permut1
това представяне е π = (1, 4)(2)(3, 7, 5)(6) и то се състои от 4 цикъла.
Теорема: Броят на пермутациите от n-ти ред, които се представят с k на брой цикъла равен на беззнаковото число на Стирлинг от първи род |s(n, n-k)|.
Доказателство: ?

Връзка между числата на Стирлинг от първи род и производните

Разглеждаме сложната функция F(x) = f(t), където t = lnx . Производна на логаритмична функция --Der1
Диференцираме F спрямо x. n-тата производна на f спрямо t означаваме с f(n)(t). Използвайки правилата за диференциране на сложна функция получаваме:
Производните на f(lnx)--Der2
Изобщо, в сила е общата формула:
Производните на f(lnx)--Der3
Ето формулата, свързваща производните F(k)(x) с числата на Стирлинг от първи род:
Производните на f(lnx) и числата на Стирлинг от първи род --Der4

Числа на Стирлинг от втори род


Числата на Стирлинг от първи род са коефициентите на полинома, получен при разкриване на скобите на низходящата n-та степен на z.
Или с други думи, това са коефициентите на представянето на zn като линейна комбинация от zi i=0…∞.
Обратно - Коефициентите на представянето на n-тата степен на z като линейна комбинация от низходящите степени на z се наричат числа на Стирлинг от втори род.       Те се означават с Означения на числата на Стирлинг от втори род --StNumbIIKind1
Нека е даден полином от степен n на променливата x, който ще означим с Q0.
Поставяме си важния въпрос ( Защото за Нас, учениците, всичко е важно! ) - Как да представим Q0 във вида
Q0 = A0 + A1x1 + A2x2 +...+ Anxn       ?
Как да намерим неизвестните коефициенти Ai ? Да предположим, че n=4, надявайки се, от този частен случай да получим идея за общия. Представяме Q0 във вида:
Полином ---Pol111.
От това представяне следва, че A0 е остатъкът при делението на Q0 на x.
Нека частното е Q1 .
Ако разделим Q1 с частно и остатък на x-1 ще получим A1 като остатък.
Нека частното от това деление е Q2 .
Вече е ясно!
Продължавайки по същия начин ще намерим последователно коефициентите Ai.
Удобно е резултатите от последователните изчисления да се разполагат във вид, подобен на този при схемата на Хорнер:
Алгоритъм за получаване на числата на Стирлинг от втори род --AlgStIIKind1
Ще използваме описаната схема за получаване на числата на Стирлинг от втори род s(5, k). ?
Предложете схема, подобна на схемата Схема за получаване на числата от триъгълника на Паскал – Pascal1 при триъгълника на Паскал, за получаване на новия ред от предходния за числата на Стирлинг от втори род. ?

Връзка между числата на Стирлинг от втори род и комбинаториката


Нека е дадена множеството N, съдържащо n на брой елемента.
С P(n, k) означаваме броят на разделянето на N на k на брой непразни подмножества, които ще означаваме с pi .
Разделяне на множество на k подмножества --SetPart1
Разделяне на множеството N на k на брой, непресичащи се помежду си, непразни подмножества.
Разделяне на множество на k подмножества --SetPart2

Ще докажем, че     Формула за разделяне на множество на k подмножества --PartFormula1.         Доказателство: ?

Връзка между числата на Стирлинг от втори род и производните


Разглеждаме сложната функция F(x)=f(t), където t=ex . t'=ex=t.
Диференцираме F спрямо x.
n-тата производна на f спрямо t означаваме с f(n)(t).
Използвайки правилата за диференциране на сложна функция получаваме:
Производните на f(exp(x))--Der1_1

Изобщо, в сила е общата формула:
Производните на f(exp(x))--Der1_2 ,
която е аналогична на рекурентната зависимост за числата на Стирлинг от втори род.
Ето формулата, свързваща производните с числата на Стирлинг от втори род:
Производните на f(exp(x)) и числата на Стирлинг от втори род --Der1_3

Какво ще научим?