Краткие сведения из теории

Размещения. Имеется множество, состоящее из элементов произвольной природы. Из них образуется группа, содержащая k элементов. При этом две группы, составленные из одних и тех же элементов, считаются различными, если внутри группы разный порядок расположения элементов. Группы, которые отличаются друг от друга не только элементами, входящими в группу, но и порядком их расположения внутри группы, называются размещениями. Число размещений обозначается символом (читается: «число размещений из элементов по элементам»). Нижний индекс число всех элементов, из которых можно составлять группу. Верхний индекс число элементов, из которых составлена группа. Доказывается, что число размещений из элементов по элементам находится по формуле

(1)

Например, , и так далее…

Перестановки. Если размещение создается сразу из всех элементов, то такое размещение называется перестановкой. Число перестановок из элементов обозначается символом и находится по формуле

. (2)

Величина (читается: факториал) помимо комбинаторики используется во многих разделах математики. Полагают по определения, что . Затем, используя определение, находим: и так далее…

Сочетания. Группы, которые отличаются друг от друга только элементами, входящими в группу, но не порядком элементов внутри группы, называются сочетаниями. Число сочетаний из элементов по элементам обозначается символом и находится по любой из двух формул

, (3)

. (4)

Формулу (3) удобно использовать для небольших ; в остальных случаях лучше использовать формулу (4).

Сочетания обладают рядом свойств, которые используются для решения задач. Отметим некоторые из этих свойств:

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

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

Правило произведения. Если одну часть группы можно составить способами, а вторую - способами, то всю группу можно составить способами. Если комбинаторная группа разбивается на s частей, и эти части можно составить способами соответственно, то всю группу можно составить способами.

Бином Ньютона. Формула бинома Ньютона имеет вид

(5)

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

Используя формулу бинома Ньютона (5) при , получим известную формулу квадрата суммы двух слагаемых.

При формула (5) дает другую известную формулу

Рассмотрим еще один важный частный случай формулы (5) при . Имеем

После преобразования получим формулу

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

Имеется различных типов элементов (общее количество элементов нас сейчас не интересует). Из них составляются размещения, содержащие элементов, причем в размещениях могут встречаться элементы одного и того же типа. Такие размещения называются размещениями с повторениями. Их число обозначается символом и находится по формуле

. (6)

Перестановки с повторениями. Имеется различных типов элементов, причем элементов первого типа, элементов второго типа, . . ., элементов го типа (всего элементов). Перестановки, составленные из этих элементов, называются перестановками с повторениями. Их количество обозначается символом и находится по формуле

(7)

Сочетания с повторениями. Имеется различных типов элементов (общее количество элементов нас сейчас не интересует). Из них составляются сочетания, содержащие элементов, причем в сочетаниях могут встречаться элементы одного и того же типа. Такие сочетания называются сочетаниями с повторениями. Их число обозначается символом и находится по формуле

. (8)

2. Контрольные вопросы и упражнения

1. Из села в село можно попасть только через село . Из в ведут две дороги, а из в три дороги. Сколькими способами можно построить маршрут движения из в ?

2. Множество состоит из 10 элементов, множество из 15 элементов. Сколько элементов содержит множество ?

3. Какая комбинаторная группа называется размещением?

4. По какой формуле находится число размещений?

5. Какая комбинаторная группа называется перестановкой?

6. По какой формуле находится число перестановок?

7. Какая комбинаторная группа называется сочетанием?

8. По какой формуле находится число сочетаний?

9. Вычислить: а) ; б) ; в) .

10. Решите для натуральных уравнение

11. Решите для натуральных уравнение

12. Решите для натуральных уравнение

13. Докажите, что величина является полным квадратом.

14. Докажите тождество .

15. Школьное расписание понедельника содержит 5 уроков. Сколькими способами можно составить расписание на понедельник, если школьники изучают 10 дисциплин?

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

17. Тренер, руководящий командой из 12 спортсменов, должен подать заявку на участие в эстафете, состоящей из 5 этапов. Сколькими способами он может составить заявку, если: а) он должен указать фамилию спортсмена на каждом этапе; б) фамилии спортсменов на этапах он может не указывать.

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

19. На шахматную доску ставится две ладьи так, чтобы они не били друг друга. Укажите количество вариантов такой расстановки.

20. В вазе стоят 5 белых и 4 алых розы. Сколькими способами можно отобрать букет из 3 роз?

21. Шестеро юношей и шестеро девушек собрались играть в волейбол. Сколькими способами они могут разделиться на две команды, в которых юношей и девушек было бы поровну?

22. В библиотеке имеется 4 разных учебника по математике, 3 учебника по физике, 2 учебника по русскому языку. Сколькими способами можно сформировать комплект учебников?

23. В комнате общежития живут 3 студента; у них имеется 5 разных чайных чашек, 4 разных блюдца, 6 разных ложек. Сколькими способами они могут сервировать стол для чаепития?

24. Приведите формулу бинома Ньютона.

25. Используя формулу бинома Ньютона, докажите формулы сокращенного умножения для .

26. Какая комбинаторная группа называется размещением с повторениями?

27. По какой формуле находится число размещений с повторениями?

28. Какая комбинаторная группа называется перестановкой с повторениями?

29. По какой формуле находится число перестановок с повторениями?

30. Какая комбинаторная группа называется сочетанием с повторениями?

31. По какой формуле находится число сочетаний с повторениями?

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

33. Для организации фейерверка устроители праздника решили запустить последовательно одну за другой 4 красных, 3 зеленых, 2 синих ракеты. Сколькими способами можно организовать фейерверк из этих ракет?

34. В цветочном магазине продаются белые, желтые и алые розы. Сколькими способами можно составить букет из 5 роз?

Задание на работу

Задача 1. Сколько костей должна содержать игра в домино, если бы наибольшее число очков на кости было равно ?

Варианты

10.

11.

12.

13.

14.

15.

Задача 2. Найти натуральные корни уравнения.

Варианты

10.

11.

12.

13.

14.

15.

Задача 3. Окрашенный куб с ребром 10 см распиливается на кубики с ребром 1 см. Сколькими способами из этих кубиков можно взять кубиков, среди которых кубиков имеют 3 окрашенных грани, кубиков имеют 2 окрашенных грани кубиков имеют 1 окрашенную грань, кубиков не имеют ни одной окрашенной грани.

Варианты

10.

11.

12.

13.

14.

15.

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

Варианты

1. ШИРЛИЛИРЛИ

2. МУСИПУСИ

3. АВВАГАВВА

4. МУМБАЮМБА

5. АЛКАКАЛКА

6. ЕЛКИПАЛКИ

7. АБРАКАДАБРА

8. ТОРОТОРО

9. РОНГОРАНГА

10. КУКАРЕКУКУ

11. РОНГОРОНГО

12. КУРКАУРКА

13. ВИЛКАПИЛКА

14. ЧУЧАЧАЛЛА

15. КАРАКАЧЧА

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