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-й степени

Логарифмы

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

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

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

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

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

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

Производная

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

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

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

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

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

Окружность

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

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

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

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

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

 

Группа Математика для школы|math4school.ru ВКонтакте

Давно собирался и вот, наконец! Примерно так выглядит история нашей группы ВКонтакте. Сомнения в необходимости её существования отброшены, и первые материалы сообщества уже выложены.

Нам 4 года!

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

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

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

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

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

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