MATH4YOU.ru
On-line учебник: теория и решение задач

Комбинаторика и бином Ньютона

Правило произведения.

Пусть элемент $ x_1$ строки $ (x_1, x_2, ..., x_k)$ можно выбрать $ n_1$ способами; после каждого выбора $ x_1$ элемент $ x_2$ можно выбрать $ n_2$ способами; после выборов $ x_1$ и $ x_2$ элемент $ x_3$ можно выбрать $ n_3$ способами и т.д.; после выборов $ x_1, x_2, ..., x_{k-1}$ элемент $ x_k$ можно выбрать $ n_k$ способами.

Тогда строку $ (x_1, x_2, ..., x_k)$ можно образовать $ n_1 \cdot n_2 \cdot ... \cdot n_k$ способами.

Пример 1.

Сколькими способами можно выбрать четырехзначное число, все цифры которого различны?

Решение.

Каждому четырехзначному числу можно поставить во взаимно однозначное соответствие строку $ (x_1, x_2, x_3, x_4)$ , где $ x_1, x_2, x_3, x_4$ – соответственно 1, 2, 3 и 4-я цифры.

Элемент $ x_1$ этой строки можно выбрать 9 способами (любую из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9);

элемент $ x_2$ можно выбрать также 9 способами (теперь можно использовать и цифру 0, но первую выбранную цифру повторить нельзя);

элемент $ x_3$ можно выбрать 8 способами (уже выбранные первые две цифры повторить нельзя);

наконец, элемент $ x_4$ можно выбрать 7 способами.

Согласно правилу произведения искомое число способов выбора четырехзначного числа с различными цифрами равно: $ 9 \cdot 9 \cdot 8 \cdot 7 = 4536.$

Размещения с повторениями.

Пусть Х – множество, состоящее из n элементов (n-членное множество).

Тогда любая строка длиной k, составленная из элементов множества X, называется размещением с повторениями из n элементов по k.

Число всех размещений с повторениями из n элементов по k равно $ n^k.$

Пример 2.

Сколькими способами можно выбрать четырехзначное число, в десятичной записи которого нет нуля?

Решение.

Четырехзначные числа указанного вида можно рассматривать как строки длиной 4, составленные из элементов множества X = {1, 2, 3, 4, 5, 6, 7, 8, 9}, т.е. как размещения с повторениями из 9 элементов по 4.

Следовательно, искомое число способов равно: $ 9^4 = 6561.$

Размещения без повторений. Перестановки.

Пусть Х - n-членное множество. Тогда любая строка длиной k, составленная из различных элементов множества Х, называется размещением без повторений из n элементов по k. Число всех таких размещений обозначается $ A^k_n$ и равно:

$\displaystyle A^k_n=n(n-1)(n-2)\hdots(n-k+1)=\dfrac{n!}{(n-k)!}.
$

В случае, когда k = n, размещения без повторений называются перестановками из n элементов. Число всех перестановок из n элементов обозначается $ P_n$ и равно:

$\displaystyle P_n = = n!.
$

Пример 3.

10 спортсменов разыгрывают одну золотую, одну серебряную и одну бронзовую медали. Сколькими способами эти медали могут быть распределены между спортсменами?

Решение.

Предположим, что спортсмены пронумерованы числами от 1 до 10 и $ x_1, x_2, x_3$ – номера спортсменов, получивших золотую, серебряную и бронзовую медали.

Каждому такому распределению медалей соответствует строка $ (x_1,x_2,x_3 )$ , состоящая из различных чисел (номеров спортсменов).

Обратно каждой строке $ (x_1,x_2,x_3 )$ соответствует способ распределения медалей.

Следовательно, число способов распределения медалей равно числу размещений без повторений из 10 элементов по 3, т.е.

$\displaystyle A^3_{10}=10\cdot 9\cdot 8=720.
$

Сочетания и бином Ньютона.

Всякое k-членное подмножество n-членного множества называется сочетанием из n элементов по k.

Число различных сочетаний из n элементов по k обозначается $ C_n^k$ .

Справедлива формула

$\displaystyle C_n^k=\dfrac{n!}{k!(n-k)!}.
$

. Числа $ C_n^0,C_n^1,...,C_n^n$ являются коэффициентами в разложении бинома Ньютона:

$\displaystyle (a + b)^n = C_n^0 a^0 b^n + C_n^1 a b^{n-1} + ... + C_n^n a^n b^0.
$

Пример 4.

Сколькими способами из 10 спортсменов можно отобрать команду из 6 человек?

Решение.

Очевидно, команда из 6 человек является 6-членным подмножеством 10-членного множества, т.е. сочетанием из 10 элементов по 6. Следовательно, искомое число способов равно $ C_{10}^6=210.$

Размещения данного состава. Полиномиальная формула.

Размещением данного состава $ (k_1, k_2,..., k_m)$ из элементов m-членного множества $ X = \{x_1, x_2,..., x_m\}$ называется всякая строка длинной $ k_1 + k_2 + ... + k_m = n,$ составленная из элементов множества Х, так, что элемент $ х_1$ повторяется $ k_1$ раз, элемент $ x_2 - k_2$ раз и т.д., элемент $ x_m - k_m$ раз.

Например, если $ X= \{x_1, x_2 ,x_3\},$ то $ (x_1, x_2 , x_2, х_1, х_1)$ есть размещение состава (3,2,0). Количество различных размещений заданного состава $ (k_1, k_2,..., k_m)$ обозначается $ A(k_1, k_2,..., k_m)$ и равно:

$\displaystyle A(k_1, k_2,..., k_m)=\dfrac{(k_1+k_2+...+k_m)!}{k_1!k_2!...k_m!}.
$

Следующая формула, обобщающая формулу бинома Ньютона, называется полиномиальной:

$\displaystyle (a_1+a_2+...+a_m)^n=\sum\dfrac{n!}{k_1!k_2!...k_m!}a_1^{k_1}a_2^{k_2}...a_m^{k_m},
$

где суммирование проводится по всевозможным наборам целых неотрицательных чисел $ k_1, k_2,..., k_m$ , для которых $ k_1 + k_2 + ... + k_m = n$ .

Пример 5.

Сколькими способами можно поставить на книжной полке 3 экземпляра учебника по алгебре, 2 экземпляра учебника по геометрии и один экземпляр учебника по математическому анализу?

Решение.

Очевидно, всякой расстановке указанных учебников взаимно однозначно соответствует строка длиной 3 + 2 + 1 = 6 состава (3, 2,1). Следовательно, искомое число способов равно числу размещений состава (3, 2, 1) .т.е.

$\displaystyle A(3,2,1)=\dfrac{(3+2+1)!}{3!2!1!}=60.
$

Пример 6.

Вычислите $ (1 + х + х^2)^3.$

Решение.

По полиномиальной формуле имеем:

$\displaystyle (1+x+x^2)^3=\sum\dfrac{3!}{k_1!k_2!k_3!}1^{k_1}x^{k_2}(x^2)^{k_m},
$

где суммирование производится по всем наборам неотрицательных целых чисел $ k_1, k_2, k_3$ , для которых $ k_1 + k_2 + k_3 = 3.$

Выпишем все такие наборы: (0,0,3), (0,3,0), (3,0,0), (0,1,2), (1,2,0), (2,0,1), (1,0,2), (0,2,1), (2,1,0), (1,1,1). Теперь находим:

$\displaystyle (1+x+x^2)^3=\sum\dfrac{3!}{k_1!k_2!k_3!}1^{k_1}x^{k_2}(x^2)^{k_m}=
$

$\displaystyle =
\dfrac{3!}{0!0!3!}1^{0}x^{0}(x^2)^{3}+
\dfrac{3!}{0!3!0!}1^{0}x^{3}(x^2)^{0}+
\dfrac{3!}{3!0!0!}1^{3}x^{0}(x^2)^{0}+
$

$\displaystyle +
\dfrac{3!}{0!1!2!}1^{0}x^{1}(x^2)^{2}+
\dfrac{3!}{1!2!0!}1^{1...
...dfrac{3!}{2!0!1!}1^{2}x^{0}(x^2)^{1}+
\dfrac{3!}{1!0!2!}1^{1}x^{0}(x^2)^{2}+
$

$\displaystyle +
\dfrac{3!}{0!2!1!}1^{0}x^{2}(x^2)^{1}+
\dfrac{3!}{2!1!0!}1^{2}x^{1}(x^2)^{0}+
\dfrac{3!}{1!1!1!}1^{1}x^{1}(x^2)^{1}=
$

$\displaystyle =
x^6+3x^5+6x^4+zx^3+6x^2+3x+1.
$