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

Cвое название биномиальные коэффициенты получили от соответствующей им производящей функции, являющейся степенью бинома:

(1.1)

Для доказательства справедливости написанного соотношения (1.1) достаточно заметить, что коэффициент при x^k равен числу способов, которыми из mсомножителей (1+x) ... (1+x)можно выбрать k сомножителей.

Отметим некоторые важнейшие соотношения для биномиальных коэффициентов (чисел сочетаний).

1.

(1.2)

Это важнейшее соотношение - прямое следствие того факта, что каждому k-элементному подмножеству Y X однозначно соответствует (n-k) - элементное подмножество X\Y множества X.

2.

(1.3)

Зафиксируем некоторый элемент x из n- элементного множества X. Множество T всех k - элементных подмножеств множества X распадается на два непересекающихся класса:

,

класс T₁ подмножеств, которые не содержат элемент x, и класс T₂подмножеств, которые его содержат. Мощность первого класса составляет , а второго , то есть столько, сколько имеется (k-1) - элементных подмножеств множества X\{x}. ð

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

3. Полагая в (1.1) x=1 получим

Эта формула следует и из того, что сумма слева есть число всех подмножеств n-элементного множества.

4.

(1.4)

Дифференцируя (1.1) и полагая x=1, получаем соотношение (1.4) .

5.

(1.5)

Равенство легко следует из следующего равенства для производящих функций:

(1+x)^m+n =(1+x)^m (1+x)ⁿ .

Полагая в (1.5) m = k = n, получим

.

Отметим, что задача прямого доказательства последнего равенства без использования производящей функции достаточно трудна.

6. Полагая в (1.1) x = –1, получаем

.

Отсюда следует, что

,

где через обозначена целая часть числа m/2. ð

Исчисление конечных разностей

Приведем пример использования биномиальных коэффициентов в вычислительной математике.

Пусть дана функция j, определенная на множестве действительных (возможно целых) чисел и принимающая действительные значения. Определим новую функцию Dj(x), называемую первой разностью j, формулой

.

Оператор D называется разностным оператором первого порядка; кратко и очень упрощенно можно определить исчисление конечных разностей как исследование оператора D . Можно применить оператор D k раз и получить k-ый разностный оператор

.

Число D^kj(x) называется k-ой разностью j в точке x (D^kj(0) называется k-ой разностью j в 0).

Определим другой оператор E, называемый оператором сдвига, формулой

.

Таким образом, D=E - I, где I означает единичный оператор:

.

Тогда первая разность функции может быть записана в виде:

.

Разности более высоких порядков определяются рекуррентным соотношением

Откуда получаем выражение для n -ой разности:

В частности,

, (1.6)

что дает явную формулу для k-ой разности в терминах значений j(0), j(1), ... , j(k). Нетрудно обратить формулу (1.6) и выразить j(n) через Dⁱ j(0). Именно,

. (1.7)

Напишем теперь в строку значения

... j(-2) j(-1) j(0) j(1) j(2) j(3)...

Если внизу написать между каждой парой последовательных членов j(i), j(i +1) их разность j(i +1) - j(i) = Dj(i), то получим последовательность

...Dj(-2) Dj(-1) Dj(0) Dj(1) Dj(2) ... .

Повторение этой процедуры приводит к таблице разностей функции j, k-ая строка которой состоит из значений D^kj(n). Диагональ, начинающаяся в j(0) и идущая направо вниз, состоит из разностей D^kj(0) в 0. Например, пусть j(n) = n⁴ . Таблица разностей (начинающаяся с j(0) ) выглядит так:

Из формулы (1.7) следует, что

(1.8)

В этом случае, так как n⁴-многочлен четвертой степени и при фиксированном k есть многочлен степени k, написанное выше разложение обрывается после члена , то есть D^k0⁴ = 0, если k > 4 (или, более общим образом, D^k n⁴ = 0, если k > 4).

Предыдущее рассуждение, конечно, не относится лишь к функции n⁴ . Подобные рассуждения приводят к следующим результатам.

1. Функция j - полином степени, не превосходящей d, тогда и только тогда. когда D^d+1j(n) =0 (или D^dj(n) - постоянная).

2. Если многочлен j(n) степени, не превосходящей d, разложен в ряд по базису , 0 £ k £ d, то коэффициенты разложения есть D^kj(0), то есть

. ð

Еще одна связь комбинаторных объектов с исчислением конечных разностей дается формулой (1.15).

Разложения

Существует тесная связь между подмножествами множеств и разложениями целого числа.

Определение. Разложение n есть представление числа n в виде упорядоченной суммы положительных целых. Например, существует восемь разложений числа 4, а именно:

1+1+1+1 3+1

2+1+1 1+3

1+2+1 2+2

1+1+2 4

Если разложение s содержит в точности k слагаемых, то говорят, что s имеет k частей и называется k -разложением. Если a₁+ a₂+...+ a_k - k -разложение s числа n, определим (k -1) - элементное подмножество q(s) (или (k -1)- подмножество ) множества {1, 2, ..., n-1} формулой

q(s) ={a₁, a₁+a₂, ... , a₁ + a₂+ ... + a_k-1} .

Эта формула устанавливает взаимно однозначное соответствие (биекцию) между всеми k-разложениями и (k -1)- подмножествами q(s) множества {1, 2, ..., n-1}. Следовательно, существует k -разложений n и 2^{n - 1} разложений n. Разложение часто схематично представляют, рисуя в строку n точек и k - 1 разделяющую вертикальную черту. Точки разделяются по k линейно упорядоченным “отделениям”, числа точек в отделениях дают k -разложение числа n . Например, последовательность

· ½ · ·½ ·½·½· · ·½· ·

соответствуют разложению 1+2+1+1+3+2 .

Другая проблема, тесно связанная с разложениями, есть задача подсчета числа N(n, k) решений уравнения

x₁ + x₂+... +x_k = n

в неотрицательных целых числах. Решение такого уравнения называется слабым разложением n на k частей, или слабым k- разложением числа n. (Решение в положительных целых числах есть просто k-разложение n.) Если мы положим y₁ = x₁+1, y₂= x₂+1, ... , y_k=x_k+1, то получим, что N(n, k) есть количество решений в положительных числах уравнения

y₁ + y₂+... +y_k = n +k ,

то есть число k-разложений числа n+k .

Таким образом, .

Подобным же приемом (найти его предоставляется читателю) доказывается, что число решений неравенства x₁ + x₂+... +x_k £ n в неотрицательных целых числах есть .

k - подмножество T n - множества S иногда называют k - сочетанием из S без повторений. Так возникает задача подсчета числа k - сочетаний из S с повторениями; то есть мы выбираем k элементов из множества S, не взирая на их порядок и допуская повторяющиеся элементы. Обозначим число таких способов . Например, . Если S = {1,2,3}, то подходящие сочетания есть 11, 22, 33, 12, 13, и 23. Эквивалентное, но более точное определение и исследование сочетаний с повторениями может быть проведено, если ввести понятие мультимножества. На интуитивном уровне мультимножество есть множество с повторяющимися элементами, например {1, 1, 2, 5, 5}. Более точно, конечное мультимножество M на множестве S есть функция n: S®À(À - множество натуральных чисел), такая, что ; n(x) рассматривается как число повторений элемента x. Целое число называют мощностью или числом элементов M и обозначают êM ê. Если S = {x₁ , x₂ ,
... , x_n}, и n(x_i) = a_i, то мы пишем . Множество всех k - мультимножеств на S обозначается символом .

Если S = {y₁ , ... , y_n} и мы положим x_i= n(y_i), то увидим, что есть число решений в неотрицательных целых числах уравнения x₁ + x₂ + ... + x_n= k . Это число, как мы видели, есть

. (1.9)

Прямое комбинаторное доказательство утверждения (1.9) таково. Пусть

{a₁, a₂, ... , a_k}, 1 £ a₁< a₂ < ... < a_k £ n + k - 1,

есть k -подмножество множества [ n + k - 1]= {1, 2, ... , n+k - 1}. Положим b_i = a_i - i + 1. Тогда {b₁ , b₂ , ... , b_n} - k -мультимножество на множестве [n].

Обратно, если дано k - мультимножество 1 £ b₁ £ b₂£ b_k£ n на [n], то определив a_i формулой a_i = b_i + i - 1, видим, что {a₁ , a₂ , ..., a_k } есть k -подмножество множества [n + k - 1] . Следовательно, мы определили взаимно однозначное соответствие между и , что и требовалось доказать.

Поучителен подход к мультимножествам с точки зрения производящих функций. Cовершенно аналогично проведенному исследованию подмножеств множества S = {x₁ , x₂ , ... , x_n } имеем

Положим x_i = x. Тогда

.

Но

,

так что

.

Появление элегантной формулы

не случайно. Это простейший пример комбинаторной теории взаимности.

Не нашли, что искали? Воспользуйтесь поиском по сайту: