ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

КОМБИНАТОРИКА

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

В основе комбинаторики лежат два основных правила: правило суммы и правило произведения.

Правило суммы: если объект А можно выбрать m способами, а объект В – n способами, и при это ни один способ выбора объекта А не совпадает со способами выбора объекта В, то объект «А или В» может быть выбран (m + n) способами.

Правило произведения: если объект А можно выбрать m способами, и при каждом способе выбора объекта А, объект В может быть выбран n способами, то совместный выбор объектов А и В может быть осуществлён (mn) способами.

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

Комбинации	Без повторений	С повторениями
Сочетания (различаются только составом элементов)
Размещения (различаются либо составом элементов либо порядком их расположения)
Перестановки (различаются только порядком расположения элементов)	Рn = n!	k 1 – число повторений I элемента, k 2 – число повторений II элемента, ……………………………………., kn – число повторений n -го элемента, m = k 1 + k 2 + … + kn

где m – длина комбинации, n – количество элементов множества

Замечание! Для нахождения числа сочетаний можно использовать формулу:

Свойства сочетаний

1) , 5) ,

2) , 6) ,

3) , 7) ,

4) , 8) .

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

, или .

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

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

..

..

..

..

..

..

..

..

..

..

..

..

..

..

..

Основное свойство треугольника Паскаля:

Если строчки треугольника Паскаля и позиции в них нумеровать, начиная с нуля, то на k -м месте в n -й строке будет стоять значение .

Пример 1.

В кружке занимаются 2 девочки и 7 мальчиков. Сколько есть способов послать на конкурс команду из 4-х человек, если в ней обязательно должна быть хоть одна девочка?

Решение. В команду входит либо одна девочка, либо обе.

В первом случае эту девочку можно выбрать способами, а также способами выбрать в команду еще трех мальчиков. По правилу произведения в этом случае × способов выбора.

Во втором случае в команду надо выбрать еще 2-х мальчиков разными способами. Всего по правилу суммы получаем × + = 91 способов выбора.

Ответ: 91.

Пример 2.

Сколько способов разложить 7 белых и 2 черных шара по 9 различным ящикам?

Решение. .Составим несколько комбинаций разложения:

(б, б, ч, б, ч, б, б, б, б), (ч, ч, б, б, б, б, б, б, б), …

Это комбинации с повторениями, одинаковые по составу, различающиеся только порядком расположения элементов – это размещения с повторениями. Тогда их число находится по формуле:

Ответ: 36.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

1. В некотором государстве не найдется двух человек, у которых оказался бы одинаковый набор зубов: либо у них разное число зубов, либо зубы отсутствуют в разных местах. Какая может быть наибольшая численность населения государства, если полное число зубов у человека равно 32?

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

3. Сколькими способами можно переставлять буквы слова ЛОГАРИФМ так, чтобы второе, четвёртое и шестое места были заняты согласными буквами?

4. Из полного набора шахмат вынули 4 фигуры или пешки. Во скольких случаях среди них окажется не менее двух коней?

5. Сколькими способами можно переставить буквы слова ПЕРЕШЕЕК так, чтобы 4 буквы «Е» не стояли подряд?

6. Две команды играют в футбол до 10 голов (встреча прекращается, как только какая-то команда забьет 10 голов). В процессе игры заполняется протокол, в который вносится счет после каждого изменения счета (например, один из протоколов – 0:0, 0:1, 0:2, 1:2,..., 5:10). Сколько разных протоколов может получиться?

7. Из 80 школьников 40 играют в футбол, а 50 – в волейбол. Каким может быть число школьников, играющих в обе игры; играющих хотя бы в одну из этих игр?

8. В классе 40 человек. Из них 26 человек играют в баскетбол, 25 занимаются плаванием, 27 – ходят на лыжах, при этом одновременно плаванием и баскетболом занимаются 15 человек, баскетболом и лыжами – 16, плаванием и лыжами – 18. Один человек освобождён от физкультурных занятий. Сколько человек занимается всеми указанными видами спорта? Сколько человек занимается только одним видом спорта?

9. В игре «Кто хочет стать миллионером» ведущий, с целью проверить математическую грамотность участника задал ему следующий вопрос: какое число точек n нужно изобразить на плоскости так, чтобы число отрезков, соединяющих всевозможные пары различных точек, было равно 1 000 000? Участник ответил, что вопрос некорректен, т.е. такого n не существует. Как он мог это объяснить?

10. На плоскости проведено n прямых, и на каждой из них взято р точек так, что ни одна из них не является точкой пересечения прямых и никакие три не лежат на одной прямой, отличной от заданных. Найдите число треугольников с вершинами в этих точках.

11.На плоскости даны три точки А, В и С. Через точки А, В и С проведены пучки соответственно из m, n и р прямых, при этом никакие три прямые не из одного пучка не пересекаются в одной точке, и никакие две не параллельны. Найдите наибольшее возможное число треугольников, вершины которых являются точками пересечения этих прямых и не совпадают с заданными точками А, В и С.

12. Даны шесть цифр 0, 1, 2, 3, 4, 5. Найдите сумму всех четырёхзначных чётных чисел, которые можно написать этими цифрами (одна и та же цифра может повторяться).

13. Сколькими способами можно выбрать из натуральных чисел от 1 до 100 три натуральных числа так, чтобы их сумма была чётной?

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

15. Каждая сторона квадрата разбита на n частей. Сколько можно построить треугольников с вершинами в точках деления?

16. Надо отгадать, какие пять монет держит в руке партнёр. Выбор монет такой: 1, 2, 3, 5, 10, 15, 20, 50 копеек, 1 рубль. Сколько может быть дано неверных ответов? А если все монеты в руке различного достоинства?

17. Сколько существует четырёхзначных чисел, делящихся на 4, в десятичной записи которых нет цифр 4, 5, 6, 8?

Не нашли, что искали? Воспользуйтесь поиском: