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

Теорема 12.5. (Бином Ньютона). Для натурального n справедлива формула

¨ Перемножим последовательно (a + b) n раз. Тогда получим сумму 2 ⁿ слагаемых вида d ₁ d ₂… d_n, где d_i (i = 1, 2,…, n) равно либо a, либо b. Разобьем все слагаемые на (n + 1) группу B ₀, B ₁,…, B_n, отнеся к B_k все те произведения, в которых b встречается множителем k раз, а a встречается (n – k) раз. Число произведений в B_k равно, очевидно, (таким числом способов среди n множителей d ₁ d ₂… d_n можно выбрать k множителей, которые будут равны b), а каждое слагаемое из равно . Поэтому ¨

Числа называются биномиальными коэффициентами.

Поставим такой вопрос: сколькими способами можно разложить множество B, состоящее из n элементов, на сумму m подмножеств

B = A ₁È A ₂ È…È A_m

так, чтобы | A ₁ | = r ₁, | A ₂ | = r ₂,..., | A_m | = r_m, где r ₁, r ₂,…, r_m – заданные числа, r_i ³ 0 и r ₁+ r ₂+…+ r_m = n. При этом множества A ₁, A ₂,…, A_m, не должны иметь общих элементов. Все описанные выше разбиения множества B на m подмножеств A ₁, A ₂,…, A_m можно получить так: возьмем произвольное r ₁-элементное подмножество A ₁ множества B (это можно сделать способами); среди n – r ₁ оставшихся элементов возьмем r ₂-элементное подмножество A ₂ (это можно сделать способами) и т.д. Тогда общее число способов выбора множеств A ₁, A ₂,…, A_m равно

Итак, мы доказали следующую теорему.

Теорема 12.6. Пусть r₁, r₂,…, r_m – целые неотрицательные числа и r₁+r₂+…+r_m = n. Число способов, которыми можно представить множество B из n элементов в виде суммы m множеств A₁, A₂,…, A_m, число элементов в которых соответственно есть r₁, r₂,…, r_m, равно

Числа называются полиномиальными коэффициентами.

Пример. Число различных перестановок, которые можно составить из n элементов, среди, которых имеется r ₁ элементов первого типа, r ₂ элементов второго типа,..., r_m элементов m -го типа, равно . Так, из букв слова «топот» можно составить 30 всевозможных различных
5-буквенных слов (в том числе и бессмысленных).

Обобщение биномиальной формулы дает следующая теорема.

Теорема 12.7. (Полиномиальная теорема)

¨ Перемножим последовательно (a ₁+ a ₂+…+ a_k) n раз. Тогда получим kⁿ слагаемых вида d ₁ d ₂… d_n, где каждый множитель d_i равен или a ₁, или a ₂,..., или a_k. Обозначим через B (r,…, r_k) совокупность всех тех слагаемых, где a ₁ встречается множителем r ₁ раз, a ₂ – r ₂ раз,..., a_k – r_k раз. Согласно теореме 12.6, число таких слагаемых равно . Отсюда сразу следует утверждение теоремы. ¨

Пример. Какой коэффициент стоит при x ² y ³ z ⁸ в разложении (x + y + z)¹³? Для применения полиномиальной теоремы положим r_x = 2, r_y = 3, и r_z = 8. Тогда искомый коэффициент равен

Дата добавления: 2015-07-08