Основы теории делимости. Основная теорема теории чисел. Алгоритм Евклида и цепные дроби. Разложение числа в цепную дробь, страница 9

{n}                                                 {n…}

Разбиение содержит только n       в комбинации с другими элементами элемент

Остается n-1, разбиваем на k-1     n выбран, n фиксировано, но k подмножеств.

S(n-1,k-1)      +  k S(n-1,k)

В каждом подмножестве S(n-1,k) можно добавить n и увеличим в k

Треугольник Стирлинга.

n\k	1	2	3	4	5	6
1	1	0	0	0	0	0
2	1	1	0	0	0	0
3	1	3	1	0	0	0
4	1	25	6	1	0	0
5	1	15	25	10	1	0
6	1	31	90	65	15	1

S(2,1) = S(1,0)+ 1 S(1,1)=1

S(n,1)=1

S(3,2)=S(2,1) + 2 S(2,2)

Числа Белла

S(n,k) – Это способы разбиения n элементного множества на k подмножеств

B_n – это число разбиений n элементного множества на все вариантные не пересекающиеся подмножества.

В_n=Sⁿ_k=0 S(n,k)

B₀=1

Теорема: 28

В_n+1=Sⁿ_k=0 C_kⁿB_k

Доказательство:

{1,2,….,n,n+1}   - множество, n+1 - фиксировано из 1..n будем выбирать по k элементов

k=0,1,…,n

Если k=0, все множество

K=n, то останется только n+1

Выбирая k остается n+1-i

Оставшееся рассмотрим как одно подмножество.

Всевозможных k разбиений B_k способами выбрать можно столько элементов – С_kⁿ отсюда В_n+1=Sⁿ_k=0 C_kⁿB_k

0  1

1  0

_   _    _   …   _

x₁  x₂   x₃        x_n

x_iÎX   Если x₁ÎX, то ставим 1

Если x₁ÏX, то ставим 0

Получается 2ⁿ комбинаций

_A2^A – множество всех подмножеств данного подмножества

i=0,1,2,…,2ⁿ-1

i=0 (0,0,…,0)        \

i=1 (0,0,…,1)        |  Все подмножества данного множества

…                          |        

i=2ⁿ-1(1,1,…,1)     /

(0,0,0,1,1,1)   Очень сильно отличаются друг от друга

(0,0,1,0,0,0)

Бинарный код Грея

Задача: Сделать расстояние между соседними элементами отличающееся на 1.

В_k=(0,0,…,0) – первый набор

i=0,1,2,…,2ⁿ-1

{

p=Q(i)   Q- функция которая вычисляет степень двойки

B[p]=1-b[p] (если бы 0, будет 1 и наоборот)

}

Q(i):

{

q=1

while (i-четное)

{i=i/2;

q=q+1

}

return Q: (возврат Q)

}

n=1 для n B₁ 1, B₂ 1, … ,B₂n  0

{0},{1} для n+1  B₁ 0, B₂ 0 … ,B₂n 1

Q(2^k+m)=Q(2^k-m)

Пример:

i	P	B	i	P	B
1	1	0000	8	4	1100
2	2	0001	9	1	1101
3	1	0011	10	2	1111
4	3	0110	11	1	1110
5	1	0111	12	3	1010
6	2	0101	13	1	1000
7	1	0100	14	2	1100

Числа Стирлинга

Определение: Факториальный многочлен

[x]_k=x(x-1)…(x-k+1)

Пример: [x]₁=x    [x]₂=x(x-1)

Теорема: 29 Биномиальная теорема Вандельмонда

[x+y]_n=Sⁿ_k=0 C_kⁿ[x]_k[y]_n-k

P(x)=Sⁿ_k=0 a_xX^k

S[n,k] – матрица перехода от обычного к ортогональному.

{1,x,x²…xⁿ} базис пространства

{1,[x]₁,[x]₂,…,[x]_n} – базис многочленов пространства многочленов

Числа Стирлинга второго рода xⁿ = Sⁿ_k=0 S[n,k][x]_k  

Числа Стирлинга первого рода [x]_n=Sⁿ_k=0 x^k s[n,k] – матрица перехода от ортогонального базиса к обычному базису.

Свойства чисел Стирлинга

1)  s(n,0)=0, n>0

2)  s(n,n)=1

3)  s(n,k)=s(n-1,k-1)-(n-1)×S(n-1,k)

Доказательство:

[x]_n=[x]_n-1(x-n+1)  по определению биномиального многочлена

[x]_n=Sⁿ_k=0 s(n,k)×x^k  =(по определению чисел Стирлинга 1 рода)

=(S^n-1_k=0 s(n-1,k)×x^k)×(x-n+1)= (S^n-1_k=0 s(n-1,k)×x^k+1)-(n-1)×(S^n-1_k=0 S(n-1,k)×x^k) =

=S(n-1,k-1)×x^k+(S^n-1_k=0 S(n-1,k-1)×x^k)-(n-1)×(S^n-1_k=0 S(n-1,k)×x^k) -(n-1)×(S(n-1,0)×x^k)=

xⁿ+(S^n-1_k=0 S(n-1,k-1)-(n-1)×(S^n-1_k=0 S(n-1,k))×x^k

xⁿ – уйдет вместе с ч_л если поменять до n-1 в начале