Конспект

Сочетания с повторениями и бином Ньютона

Ключевые тезисы

• Количество сочетаний с повторениями можно свести к количеству обычных сочетаний без повторений.
• Доказательство строится на установлении взаимно однозначного соответствия между объектами (идея «бараны и камни»).
• Бином Ньютона раскрывает связь между степенями двучлена и биномиальными коэффициентами (числами сочетаний).
• Комбинаторные тождества позволяют упрощать сложные выражения и лучше понимать свойства чисел сочетаний.

Теорема о сочетаниях с повторениями

Сочетание с повторениями — это выбор k объектов из n типов, где объекты одного типа неразличимы и могут выбираться многократно.

Формула:
Количество сочетаний с повторениями из n по k равно обычному числу сочетаний без повторений:
C̄(n, k) = C(n + k - 1, k)

Доказательство через взаимно однозначное соответствие

Идея доказательства аналогична древнему способу учёта баранов с помощью камней: каждому барану (сочетанию с повторениями) сопоставляется уникальный камень (последовательность нулей и единиц).

Процедура построения «паспорта» (последовательности):

1. Упорядочиваем n типов объектов (например, буквы алфавита).
2. Для каждого типа объекта a_i рисуем столько единиц (1), сколько раз он встречается в сочетании.
3. После каждой группы единиц (кроме последней) ставим разделитель — ноль (0).

Пример для n=33, k=4, сочетание {а, а, б, ж}:

• Буква а встречается 2 раза → рисуем 11. Ставим разделитель 0.
• Буква б встречается 1 раз → рисуем 1. Ставим разделитель 0.
• Буквы в-е не встречаются → рисуем только разделители 0.
• Буква ж встречается 1 раз → рисуем 1. Для последней буквы алфавита разделитель не ставится.

Итоговая последовательность (паспорт): 11 0 1 0 0 0 0 0 1 ... (всего 4 единицы и 32 нуля).

Обратное восстановление:
Имея последовательность из n + k - 1 символов (где k единиц и n-1 нулей), можно однозначно восстановить исходное сочетание, интерпретируя единицы как вхождения объекта, а нули как переход к следующему типу.

Итог доказательства:
Установлено взаимно однозначное соответствие между:

1. Всеми k-сочетаниями с повторениями из n объектов.
2. Всевозможными последовательностями длины n + k - 1, содержащими ровно k единиц.

Количество таких последовательностей — это число способов выбрать k позиций для единиц из n + k - 1 доступных позиций, то есть C(n + k - 1, k).

Бином Ньютона

Теорема:
(x + y)^n = Σ_{k=0}^{n} C(n, k) * x^k * y^(n-k)

Доказательство (комбинаторное):
(x + y)^n — это произведение n одинаковых скобок (x + y). При раскрытии скобок нужно из каждой выбрать либо x, либо y.

• Если мы выбираем x ровно из k скобок (а из оставшихся n-k скобок выбираем y), то получится слагаемое x^k * y^(n-k).
• Число способов выбрать, из каких именно k скобок мы возьмём x, равно C(n, k).
  Суммируя такие слагаемые для всех возможных k от 0 до n, получаем формулу бинома.

Биномиальные коэффициенты — это числа C(n, k), являющиеся коэффициентами в разложении бинома.

Комбинаторные тождества

1. Симметрия
C(n, k) = C(n, n - k)

Доказательство (комбинаторное):
Каждому k-сочетанию можно взаимно однозначно сопоставить его дополнение до полного множества из n объектов, которое является (n-k)-сочетанием.

2. Рекуррентное соотношение (Треугольник Паскаля)
C(n, k) = C(n-1, k-1) + C(n-1, k)

Доказательство (комбинаторное):
Все k-сочетания из n объектов можно разбить на два непересекающихся класса:

1. Содержащие фиксированный объект a₁: Остаётся выбрать k-1 объектов из оставшихся n-1. Число способов: C(n-1, k-1).
2. Не содержащие объект a₁: Нужно выбрать все k объектов из оставшихся n-1. Число способов: C(n-1, k).

Это соотношение лежит в основе построения треугольника Паскаля, где каждое число равно сумме двух вышестоящих.

3. Сумма биномиальных коэффициентов в строке
C(n, 0) + C(n, 1) + ... + C(n, n) = 2^n

Доказательство (комбинаторное):
Рассмотрим все последовательности длины n из нулей и единиц.

1. Общее число таких последовательностей: 2^n (по правилу умножения).
2. С другой стороны, число последовательностей, содержащих ровно k единиц, равно C(n, k).
   Суммируя количество последовательностей для всех возможных k (от 0 до n), мы получаем общее число всех последовательностей.

Доказательство (через бином Ньютона):
Подставим в формулу бинома x = 1, y = 1:
(1 + 1)^n = 2^n = Σ_{k=0}^{n} C(n, k) * 1^k * 1^(n-k) = Σ_{k=0}^{n} C(n, k).

Выводы

• Комбинаторные доказательства, основанные на установлении взаимно однозначных соответствий («бараны и камни»), часто мощнее и изящнее алгебраических выкладок.
• Числа сочетаний (C(n, k)) являются центральными объектами в комбинаторике и тесно связаны с биномом Ньютона.
• Тождества для чисел сочетаний (симметрия, рекуррентная формула, сумма строки) позволяют эффективно с ними работать и глубже понимать их природу.