П.1. Комбинаторные функции

Определение. Символ Кронекера определяется равенствами:

Определение. Число n! (читается " n -факториал"), определяется равенствами:

Определение. Многочлен x - убывающий факториал из х по n, определяется равенствами:

Определение. Многочлен - возрастающий факториал из x по n, определяется равенствами:

x ⁽⁰⁾ = 1.

Легко проверить, что многочлены x и имеют степень n и связаны равенством

, n Î N .

Биномиальные коэффициенты.

Определение. Для " n, k Î N , k £ n, биномиальный коэффициент (читается биномиальный коэффициент из n по k) определяется равенством

Для всех других значений n, k мы полагаем .

Основные свойства биномиальных коэффициентов.

1. Для " n, k Î N , k £ n,

.

Доказательство. Имеем . n

2. , " n Î N ,

, " n Î N.

, " n, k Î N , k £ n.

Доказательство. Имеем

, ,

, .

. n

3. , .

Доказательство. Имеем

. n

4. , .

Доказательство. Имеем

. n

5. Если n - чётное, то

.

Если n - нечётное, то

. n

Свойство 3 даёт удобный рекуррентный способ вычисления биномиальных коэффициентов, который осуществляется с помощью треугольника Паскаля. В n - ой строке треугольника Паскаля расположены биномиальные коэффициенты

.

Треугольник Паскаля.

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1