Math    schooL

 

 

Элементы комбинаторики


Что такое комбинаторика

Правила сложения и умножения

Перестановки

Перестановки с повторениями

Размещения

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

Сочетания

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

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

Треугольник Паскаля


Что такое комбинаторика

Комбинаторика — раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.

Комбинаторика возникла в XVI веке. Первые комбинаторные задачи касались азартных игр. Сегодня комбинаторные методы используются для решения транспортных задач, составления планов производства и реализации продукции. Установлены связи между комбинаторикой и задачами линейного программирования, статистики. Комбинаторика используется для составления и декодирования шифров, для решения других проблем теории информации.

Значительную роль комбинаторные методы играют и в  чисто математических вопросах — теории групп и их представлений, изучении основ геометрии,  неассоциативных алгебр и др.

Пример комбинаторной задачи. Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

I способ. Постараемся выписать все такие числа. На первом месте может стоять любая цифра кроме 0. Например, 2. На втором месте любая цифра из 0, 4, 6 и 8. Пусть 0. Тогда в качестве третьей цифры можно выбрать любую из 4, 6, 8. Получаем три числа

204, 206, 208.

Вместо 0 на второе место можно было поставить 4, тогда третье цифрой можно записать или 0, или 6, или 8:

240, 246, 248.

Рассуждая аналогично, получаем ещё две тройки трёхзначных чисел с цифрой 2 на первом месте:

260, 264, 268;

280, 284, 286.

Других, кроме выписанных 12-ти, трёхзначных чисел с цифрой 2 на первом месте, и удовлетворяющих условию,  нет.

Если на первом месте записать цифру 4, а остальные выбирать из цифр 0, 2, 6, 8,  то получим ещё 12 чисел:

402, 406, 408;

420, 426, 428;

460, 462, 468;

480, 482, 486.

По столько же трёхзначных чисел можно составить с цифрой 6 на первом месте и цифрой 8 на первом месте. Значит, искомое количество:

4 · 12 = 48.

Вот эти числа:

204, 206, 208, 240, 246, 248, 260, 264, 268, 280, 284, 286;

402, 406, 408, 420, 426, 428, 460, 462, 468, 480, 482, 486;

602, 604, 608, 620, 624, 628, 640, 642, 648, 680, 682, 684;

802, 804, 806, 820, 824, 826, 840, 842, 846, 860, 862, 864.

Ответ: 48.  

Метод рассуждения, которым мы воспользовались при решении предыдущей задачи, называется перебором возможных вариантов.


Правила сложения и умножения

Комбинаторное правило сложения (правило "или") — одно из основных правил комбинаторики, утверждающее, что, если имеется n элементов и элемент A1 можно выбрать m1 способами, элемент A2 можно выбрать m2 способами и так далее, элемент An можно выбрать mn способами, то выбрать или A1, или A2, или, и так далее, An можно 

m1 + m2 + ... + mn 

способами.

Например, выбрать подарок ребёнку из 9 машинок, 7 плюшевых медведей и 3 железных дорог можно

9 + 7 + 3 = 19

способами. 

Ответ: 19.

Правило умножения (правило "и") — ещё одно из важных правил комбинаторики. Согласно ему, если элемент A1 можно выбрать m1 способами, элемент A2 можно выбрать m2 способами и так далее, элемент An можно выбрать mn способами, то набор элементов (A1, A2, ... , An) можно выбрать

m· m2 · ... · mn 

способами. 

Например.

1) Выбрать ребёнку в подарок машинку, плюшевого медведя и железную дорогу, выбирая из 9 машинок, 7 плюшевых медведей и 3 железных дорог, можно

9 · 7 · 3 = 189

способами.

Ответ: 189. 


2) Воспользуемся правилом умножения для решения задачи, уже рассмотренной выше: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

II способ. 

0 не может стоять первым, значит первую цифру нужно выбрать из 2, 4, 6, 8 — 4 способа;

второй цифрой может быть любая из четырёх оставшихся — 4 способа;

третью цифру можно выбрать среди трёх оставшихся — 3 способа.

Итак, искомое количество трёхзначных чисел:

4 · 4 · 3 = 48. 

Ответ: 48.


Перестановки

Множество из n элементов называется упорядоченным, если каждому его элементу поставлено в соответствие натуральное число от 1 до n.

Перестановкой из n элементов называется любое упорядоченное множество из n элементов.

Например, из 4 элементов  ♦  ♥  ♣  ♠  можно составить следующие 24 перестановки:


♦  ♥  ♣  ♠
    ♣  ♠
      ♠
     
♦  ♥  ♠  
    ♠  
    ♠  
     
♦    ♥  ♠
      ♠
      ♠
      
  ♣  ♠  ♥
  ♣  ♠  
    ♠  
      
  ♠  ♥  ♣
  ♠    ♣
  ♠    
      
  ♠   ♣  ♥
  ♠   
  ♠    
      

 ◄ 

                       

Количество перестановок из n элементов принято обозначать Pn. С помощью перебора возможных вариантов легко убедиться, в том что

P1 = 1;  P2 = 2;  P3 = 6;  P4 = 24.

Вообще, число всевозможных перестановок из n элементов равно произведению всех натуральных чисел от 1 до n, то есть n! (читается "эн факториал"):

Pn = 1 · 2 · 3 · ... · (n –1) · n = n!.

Для  Pn  справедлива рекуррентная формула:

Pn = · Pn – 1 .

Значение факториала определено не только для натуральных чисел, но и для 0:

0! = 1.


Таблица факториалов целых чисел от 0 до 10
n
0
1
2
3
4
5
6
7
8
9
10
n!
1
1
2
6
24
120
720
5 040
40 320
362 880
3 628 800


► Например, сколькими способами 5 мальчиков и 5 девочек могут занять в театре места в одном ряду с 1-го по 10-е место, если никакие два мальчика и никакие две девочки не сидят рядом?

Возможны два случая с одинаковым количеством способов: 1) мальчики — на нечётных местах, девочки на чётных и 2) наоборот.

Рассмотрим первый случай. Мальчики по нечётным местам могут сесть

 P5 = 120

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

120 · 120 = 14 400

способами. Значит, всего способов

14 400 + 14 400 = 28 800.

Ответ: 28 800.  


Перестановки с повторениями

Перестановкой с повторениями из n элементов, среди которых k разных, при этом насчитывается n1 неразличимых элементов первого типа, n2 неразличимых элементов второго типа и так далее, nk неразличимых элементов k-го типа  (где n+ n+ … + nk = n), называется любое расположение этих элементов по n различным местам.  

Число перестановок с повторениями длины n из k разных элементов, взятых соответственно по n1, n2, …, nk раз каждый обозначается и вычисляется следующим образом:$$P_{n_1,n_2, ... , n_k}=\frac{n!}{n_1!n_2! ... n_k!}~.$$

► Например, сколько различных десятизначных чисел можно составить из цифр: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4?

В данном случае: n = 10,  n1 = 1,  n2, n= 3, n= 4,$$P_{1, 2, 3, 4}=\frac{10!}{1!2! 3! 4!}=\frac{10!}{1!2! 3! 4!}=12~600.$$

Ответ: 12 600.   


Размещения

Размещением из n элементов по m (m ≤ n) называется любое множество, состоящее из m элементов, взятых в определённом порядке из данных n элементов.

Два размещения из элементов по m считаются различными, если они различаются самими элементами или порядком их расположения.

► Например, составим все размещения из четырёх элементов  A, B, C, D  по два элемента:

A B;       A C;       A D;

B A;       B C;       B D;

C A;       C В;       C D;

D A;       D В;       D C.

 ◄                   

Число всех размещений из элементов по m обозначают \(A_n^m\) (читается: "А из n по m") и вычисляется по любой из формул:$$A_n^m=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot (n-m+1)\\A_n^m=\frac{n!}{(n-m)!}$$

► Примеры задач.

1) Воспользуемся понятием размещений из n элементов по m для решения задачи, уже дважды рассмотренной ранее: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

III способ.

Первую цифру можно выбрать четырьмя способами из набора 2, 4, 6, 8. В каждом из этих случаев количество пар второй и третей цифры равно числу размещений из 4 оставшихся цифр по 2. Значит искомое количество трёхзначных чисел равно:$$4\cdot A_4^2=4\cdot \frac{4!}{(4-2)!}=4\cdot \frac{4!}{2!}=4\cdot (3\cdot 4)=48.$$Ответ: 48. 


2) Для полёта в космос необходимо укомплектовать экипаж из шести человек. В него должны входить: командир корабля, первый и второй его помощники, два бортинженера, один из которых старший, и один врач. Командный состав выбирается из 20 лётчиков, бортинженеры — из 15 специалистов, а врач — из 5 медиков. Сколькими способами можно укомплектовать экипаж?

Поскольку в выборе командного состава важен порядок, то командира и двух его помощников можно выбрать \(A_{20}^3\) способами. Порядок бортинженеров тоже важен, значит, для их выбора существует \(A_{15}^2\) способов. Врач всего один, для его выбора существует 5 способов. Воспользуемся комбинаторным правилом умножения и найдём количество возможных экипажей корабля:$$A_{20}^3\cdot A_{15}^2\cdot 5=\frac{20!}{17!}\cdot \frac{15!}{13!}\cdot 5=(18\cdot 19\cdot 20)\cdot (14\cdot 15)\cdot 5=7~182~000.$$Ответ: 7 182 000.  


Понятно, что, если m = n, то$$A_n^m=A_n^n=P_n=n!.$$

Справедливо также, что, если m = n – 1, то$$A_n^{n-1}=A_n^n=P_n=n!.$$


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

Помимо обычных размещений бывают и размещения с повторениями или выборки с возвращением

Пусть имеется n различных объектов. Выберем из них m штук, действуя по следующему принципу. Возьмём любой, но не будем его устанавливать в какой-то ряд, а просто запишем под номером 1 его название, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был только что взят), запишем его название, пометив номером 2, и снова вернём объект обратно. И так далее, пока не получим m названий. 

Размещения с повторениями обозначаются \(\overline{A}_n^m\) и, согласно правилу умножения, вычисляются по формуле$$\overline{A}_n^m=n^m.$$Заметим, что здесь допустим случай, когда m > n, то есть выбранных объектов больше, чем их всего имеется. Это неудивительно: каждый объект после "использования" возвращается обратно и может быть использован повторно.

► Например, количество вариантов шестизначного пароля, в котором каждый знак является цифрой от 0 до 9 или буквой латинского алфавита (одна и та же строчная и прописная буква — один символ) и может повторяться, равно:$$\overline{A}_{10+26}^6=\overline{A}_{36}^6=36^6=2~176~782~336.$$Если же строчные и прописные буквы считаются различными символами (как это обычно и бывает), то количество возможных паролей становится ещё более колоссальным:$$\overline{A}_{10+26+26}^6=\overline{A}_{62}^6=62^6=56~800~235~584.$$

◄                

Сочетания

Сочетанием из n элементов по m (m ≤ n) называется любое множество, состоящее из m элементов, выбранных из данных n элементов.

В отличии от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания из элементов по m считаются различными, если они различаются хотя бы одним элементом.

► Например, составим все сочетания из четырёх элементов  A, B, C, D  по два элемента:

A B;       A C;       A D;

B C;       B D;

C D.

 ◄  

Число всех сочетаний из элементов по m обозначают \(C_n^m\) (читается: "C из n по m") и вычисляется по любой из формул:$$C_n^m=\frac{A_n^m}{P_m}$$$$C_n^m=\frac{n\cdot (n-1)\cdot (n-2)~\cdot~ ...~\cdot~ (n-m+1)}{1\cdot2\cdot3~\cdot~...~\cdot ~m}$$$$C_n^m=\frac{n!}{m!\cdot (n-m)!}.$$

Примеры задач. 

1) Бригада, занимающаяся ремонтом школы, состоит из 12 маляров и 5 плотников. Из них для ремонта физкультурного зала надо выделить 4 маляров и 2 плотников. Сколькими способами можно это сделать?

Так как порядок маляров в каждой выбранной четвёрке и порядок плотников в каждой выбранной паре не имеет значения, то, согласно комбинаторному правилу умножения, искомое количество способов равно:$$C_{12}^4 \cdot C_5^2 =\frac{12!}{4!\cdot 8!}\cdot \frac{5!}{2!\cdot 3!}=\frac{9\cdot10\cdot11\cdot12}{1\cdot2\cdot3\cdot4}\cdot \frac{4\cdot5}{1\cdot 2}=4~950.$$Ответ: 4 950.


2) В классе обучаются 30 учащихся, среди которых 13 мальчиков и 17 девочек. Сколькими способами можно сформировать команду из 7 учащихся этого класса, если в неё должна входить хотя бы одна девочка?

Количество всех возможных команд по 7 человек из класса равно \(C_{30}^7\). Количество команд в которых только мальчики — \(C_{13}^7\). Значит, количество команд, в которых есть хотя бы одна девочка, равно:$$C_{30}^7 - C_{13}^7 =\frac{30!}{7!\cdot 23!} - \frac{13!}{7!\cdot 6!}=2~035~800-1~716=2~034~084.$$Ответ: 2 034 084.


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

Помимо обычных сочетаний рассматривают сочетания с повторениями

Пусть в множестве имеется n объектов. Выберем из них m штук, действуя по следующему принципу. Возьмём любой, но не будем его устанавливать в какой-то ряд, а просто запишем, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был взят и записан ранее), запишем его название и снова вернём объект обратно. И так далее, пока не получим m названий.

Принципиальное отличие от размещений с повторениями заключается в том, что в данном случае элементы списка не нумеруются. Например, список "A, С, A, В" и список "А, А, В, С" считаются одинаковыми. 

Сочетания с повторениями обозначаются \(\overline{C}_n^m\) и вычисляются по формуле$$\overline{C}_n^m=P_{m,~n-1}=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$И ещё один способ записи той же формулы:$$\overline{C}_n^m=C_{m+n-1}^m=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$Заметим, что подобно размещениям с повторениями, допустим случай, когда m > n, то есть выбранных объектов больше, чем их всего имеется. Действительно, каждый объект после "использования" возвращается обратно и может быть использован снова и снова.

Например, выясним сколькими способами можно купить 7 пирожных в кондитерском отделе, если в продаже 4 их сорта?

Естественно полагать, что количество пирожных каждого вида не меньше 7, и при желании можно купить только пирожные одного из них. Так как порядок в котором кладут купленные пирожные в коробку не важен, то имеем дело с сочетаниями с повторениями. Так как нужно выбрать 7 пирожных из 4 его видов, то искомое количество способов равно:$$\overline{C}_4^7=\frac{(7+4-1)!}{7!\cdot (4-1)!}=\frac{10!}{7!\cdot 3!}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=120.$$

Ответ: 120.  


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

Равенство$$(x+a)^n=C_n^0x^na^0+C_n^1x^{n-1}a^1+...+C_n^mx^{n-m}a^m+...+C_n^nx^0a^n$$называют биномом Ньютона или формулой Ньютона. Правая часть равенства называется биномиальным разложением в сумму, а коэффициенты \(C_n^0,~C_n^1,~...~,~C_n^n\) — биномиальными коэффициентами


Свойства биномиальных коэффициентов:

\(~~~~~~~~1.~~C_n^0=C_n^n=1\\ ~~~~~~~~2.~~C_n^m=C_n^{n-m}\\ ~~~~~~~~3.~~C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\\ ~~~~~~~~4.~~C_n^0+C_n^1+C_n^2+~...~+C_n^n=2^n\\ ~~~~~~~~5.~~C_n^0+C_n^2+C_n^4+~... =C_n^1+C_n^3+C_n^5+~...=2^{n-1}\\ ~~~~~~~~6.~~C_n^n+C_{n+1}^n+C_{n+2}^n+~...~+C_{n+m-1}^n=C_{n+m}^{n+1}\\ \)


Свойства биномиального разложения:

1.  Число всех членов разложения на единицу больше показателя степени бинома, 

 то есть равно  n + 1.

2.  Сумма показателей степеней x и a каждого члена разложения равна показателю степени бинома,

 то есть  (n – m) + m = n.  

3.  Общий член разложения (обозначается Tn+1) имеет вид$$T_{n+1}=C_n^m x^{n-m}a^m,~~~~m=0,~1,~2,~...~,~n.$$


Треугольник Паскаля

Все возможные значения биномиальных коэффициентов (числа сочетаний) для каждого показателя степени бинома n можно записать в виде бесконечной треугольной таблицы. Такая таблица называется треугольником Паскаля:







\(C_0^0\)









\(C_1^0\)

\(C_1^1\)







\(C_2^0\)

\(C_2^1\)

\(C_2^2\)





\(C_3^0\)

\(C_3^1\)

\(C_3^2\)

\(C_3^3\)



\(C_4^0\)

\(C_4^1\)

\(C_4^2\)

\(C_4^3\)

\(C_4^4\)

\(C_5^0\)

\(C_5^1\)

\(C_5^2\)

\(C_5^3\)

\(C_5^4\)

\(C_5^5\)

. . .



. . .



. . .


В этом треугольнике крайние числа в каждой строке равны 1. Действительно, \(C_n^0=C_n^n=1\). А каждое не крайнее число равно сумме двух чисел предыдущей строки, стоящих над ним: \(C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\). 

Таким образом, этот треугольник предлагает ещё один (рекуррентный) способ вычисления чисел  \(C_n^m\):


n = 0








1








= 1







1

1







n = 2






1

2

1






= 3





1

3

3

1





n = 4




1

4

6

4

1




n = 5



1

5

10

10

5

1



n = 6


1

6

15

20

15

6

1


n = 7

1

7

21

35

35

21

7

1

n = 8
1

8

28

56

70

56

28

8

1
...



...



...

...



...




В k-й строке таблицы Паскаля записан набор коэффициентов, соответствующий биному с показателем степени n = k – 1.

Например, в шестой строке записаны коэффициенты для разложения в сумму (x + a)5. С учётом свойств биномиального разложения и набора биномиальных коэффициентов из треугольника Паскаля запишем:$$(x+a)^5=x^5+5x^4a+10x^3a^2+10x^2a^3+5xa^4+a^5.$$

◄                  

      Смотрите так же:

Обозначения и сокращения

Таблицы чисел

Алгебраические тождества

Степени

Арифметический корень n-й степени

Логарифмы

Графики элементарных функций

Построение графиков функций геометрическими методами

Тригонометрия

Арифметическая и геометрическая прогрессии

Таблицы значений тригонометрических функций

Предел и непрерывность функции

Производная

Первообразная и интегралы

Теория вероятностей

Треугольники

Четырёхугольники

Многоугольники

Окружность

Площади геометрических фигур

Прямые и плоскости

Многогранники

Тела вращения

Декартова система координат

 

Нам 4 года!

14 марта 2016 года сайту Математика для школы|math4school.ru исполнилось 4 года. Поскольку число 4 для нашего сайта не чужое, мы решили подвести некоторые итоги.

Новый формат главного меню

Расширены функциональные возможности главного меню.

Галерея на сайте math4school.ru
Приглашаю посетить Галерею, – новый раздел на сайте.

444 года со дня рождения Иоганна Кеплера

27 декабря 2015 года исполнилось 444 года со дня рождения Иоганна Кеплера.

Новый раздел на сайте math4school.ru

Закончена работа над новым разделом сайта Работа над ошибками.

Союз образовательных сайтов