Комбинаторные конфигурации в алгебре и анализе

Многие важные формулы алгебры и математического анализа (и других разделов математики) имеют наглядную комбинаторную интерпретацию или доказываются с использованием правил комбинаторики.

3.1. Бином Ньютона. – формула бинома Ньютона. В частности, (х + у)² = х² + 2ху + у²; (х + у)³ = х³ + 3х²у + 3ху² + у³ и т.д.

Доказательство. Раскроем скобки выражения (х + у) ⁿ = (x + y)(x + y)…(x + y). В результате получим сумму членов вида . Например (х + у) ³ = ххх + хху + хух + хуу + ухх + уху + уух + ууу. Приведем подобные члены, подсчитав число таких произведений при каждом k = 0,…, n. Каждое такое выражение – не что иное, как перестановка повторениями из 2-х элементов. Полагая n₁ = k, n₂ = n – k, получим, что число этих перестановок равно Р(k, n – k) = (см. пп. 2.3, 2.4), т.е. множитель при х^kу^{n – k} совпадает с , что и требовалось доказать.

С помощью формулы бинома легко получить новые свойства чисел сочетаний.

5. . Доказать легко с использованием бинома Ньютона на основе тождества (1 – 1)ⁿ = 0.

6. .

Доказательство. Имеем: n×2^n–1 = n×(1 + 1)^{n –1} = . В свою очередь при любом р выполняется равенство:

= = .

Следовательно, . Переобозначим индекс суммирования, положив p + 1 = k. Имеем:

,

что и требовалось доказать. В последнем равенстве формально введено равное нулю слагаемое при k = 0.

3.2. Полиномиальная формула. Формулу бинома можно обобщить на случай нескольких слагаемых: (х₁ + х₂ + … + х_k)ⁿ.

Запишем эту формулу в виде произведения одинаковых сомножителей и перемножим. Получим все возможные n-размещения с повторениями из объектов х₁, х₂ , … , х_k. Приведем подобные, сосчитав число повторений каждого слагаемого вида . Для этого надо определить число слагаемых, в которых символ х₁ повторяется n₁ раз, х₂ – n₂ раз, и т.д., х_k повторяется n_k раз. Каждое такое слагаемое – это перестановка с повторением n_j раз элемента х_j, j = 1,…k. Число таких перестановок равно Р(n₁, n₂ ,…, n_k), å n_j = n. Следовательно

(х₁ + х₂ + … + х_k)ⁿ = .

Выражение n₁ + … + n_k = n в значке суммы означает, что перебираются все (целые неотрицательные) значения n₁,…, n_k, удовлетворяющие данному условию.

Например: (x + y + z)⁴ = P(4, 0, 0)×x⁴ + P(0, 4, 0)×y⁴ + P(0, 0, 4)×z⁴ + P(3, 1, 0)×x³y + P(3, 0, 1)×x³z + P(2, 2, 0)×x² y² + P(2, 1, 1)×x² y z + P(2, 0, 2)×x² z² + P(1, 3, 0)×x y³ + P(1, 0, 3)×x z³ + P(1, 1, 2)×x y z² + P(1, 2, 1)×x y² z + P(0, 3, 1)×y³ z + P(0, 1, 3)×y z³ + P(0, 2, 2)×y² z².

Напоминаем, что здесь Р(a, b, c) = , например Р(2, 1, 1) = = 12.

3.3. Ряд Ньютона. Формулу бинома можно обобщить на случай нецелой степени, в результате получим выражение:

(у + х)ⁿ = уⁿ + n у^n–1х + + … + ++…

При целом значении n формула содержит конечное число слагаемых, т.к. для k > n коэффициенты при у^n–kх^k обращаются в ноль. При нецелом n получается бесконечный степенной ряд.