Сетевая библиотекаСетевая библиотека

1

Дата публикации: 19.01.2016
Тип: Текстовые документы DOCX
Размер: 27 Кбайт
Идентификатор документа: -111831908_437213397
Файлы этого типа можно открыть с помощью программы:
Microsoft Word из пакета Microsoft Office
Для скачивания файла Вам необходимо подтвердить, что Вы не робот


Не то что нужно?


Вернуться к поиску


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

Слово combination происходит из латинского языка и означает соединение.

Эта часть математики возникла в XVI веке в связи с играми в карты и кости.

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

Основные правила комбинаторики

Правило сложения («или»)

Если m взаимно исключающих друг друга действий могут выполняться соответственно k1, k2, k3,…, km способами, то выполнить одно любое из этих действий можно k1+ k2+ k3+…+ km способами.

Пример 1. Ответы на один из вопросов теста подразделены на две подгруппы: в одной 6 возможных вариантов ответа, а в другой – 4 варианта. Сколькими способами можно ответить на данный вопрос?

k1=6, k2=4⇒k1+k2=6+4=10 способами можно ответить на данный вопрос.

Правило умножения («и»)

Если требуется выполнить одно за другим какие – то m действий, которые можно выполнить соответственно k1, k2, k3,…, km способами, то все m действий вместе могут быть выполнены k1∙ k2∙ k3∙…∙ km способами.

Пример 2. В мини тесте с заданными вариантами ответов задано всего 4 вопроса. На 1 – ый вопрос имеется 5 вариантов ответов, на 2 – ой – 4, на 3 – й – 6, на 4 – ый – 3. Сколько всего возможно различных вариантов ответов на данный тест?

k1=5, k2=4, k3=6, k4=3 k1∙ k2∙ k3∙ k4=5∙4∙6∙3=360 вариантов.

Основные виды соединений и расчет их количества

1. Размещения. Предположим, что имеется n – элементное множество. Из элементов этого множества составляются k – членные комбинации (соединения), k≤n, отличающиеся друг от друга как порядком следования элементов, так и составом элементов, причем каждый из n элементов может входить в соединение не более одного раза. Такой тип комбинации называется размещением. Число (количество) размещений из n элементов по k элементов определяется по формуле

Ank=n∙n-1…n-k+1=n!n-k! (1)Здесь использовано типовое обозначение стандартного произведения:

n!=n∙n-1∙n-2∙…∙3∙2∙1=1∙2∙3∙…n-2∙n-1∙nЭто произведение называется n – факториал (произведение чисел натурального ряда). По определению 0!=1Пример 1. В классе 25 учащихся. Нужно выбрать старосту, профорга и редактора газеты. Сколькими способами можно это сделать?

n=25, k=3⇒Ank=n!n-k!=25!25-3!=25!22!=22!∙23∙24∙2522!==23∙24∙25=13800 способами.

2. Размещения с повторениями. Предположим, что имеется n – элементное множество из элементов этого множества составляются k – членные соединения, допускающие повторение каждого элемента от 0 до k раз. Такие соединения называются размещения с повторениями. Число размещений с повторениями определяется по формуле: Ank=nk. (2)Пример 2. Сколько двухбуквенных серий для денежных знаков можно составить из 31 буквы русского алфавита (исключить й и ъ)?⇒n=31, k=2 A312=312=961 двухбуквенную серию для денежных знаков можно составить из 31 буквы русского алфавита.

3. Перестановки. Размещения из n элементов, отличающиеся друг от друга порядком следования элементов, называются перестановками из n элементов, число перестановок из n элементов определяется по формуле Pn=Ann=n! (3)

Пример 3. Сколькими способами 6 человек могут сесть на 6 стульев?

Число способов равно P6=6!=1∙2∙3∙4∙5∙6=7204. Перестановки с повторениями. В тех случаях, когда среди образующих перестановки элементов имеются одинаковые, получаются соединения, называемые перестановками с повторениями. Число перестановок с повторениями определяется по формуле

Pn=n1, n2, n3,…, nk=n!n1!n2!…nk! (4)Пример 4. Сколько различных перестановок букв можно сделать в слове «колокол»?

В слове «колокол», состоящего из 7 букв, буква к повторяется 2 раза, о – 3 раза, л – 2 раза. Следовательно, по формуле (4) при n=7, n1=2, n2=3, n3=2 получаем P7=2;3;2=72!3!2!=2105. Сочетания. Пусть имеется n – элементное множество, k – членные комбинации (k≤n), различающиеся только составом элементов, называются сочетаниями из n элементов по k элементов. Число сочетаний без повторений определяется по формуле

Cnk=n!k!n-k!=Cnn-k (5)Пример 5. Сколькими способами можно составить команду из 4 человек для соревнования по бегу, если имеется 7 бегунов?

n=7, k=4Число способов равно

C74=7!4!7-4!=7!4!3!=4!∙5∙6∙74!1∙2∙3=356. Сочетания с повторениями. Сочетания с повторениями из n элементов по k называются такие соединения, которые включают k из n различающихся между собой элементов при условии, что один и тот же элемент может включаться в комбинацию несколько раз. Число сочетаний с повторениями из n элементов по k определяется по формуле

Cnk=Cn+k-1k (6)Пример 6. Сколько наборов из 7 пирожных можно составить, если в продаже имеются 4 сорта пирожных?

Искомое число С47=С7+4-17=С107=10!7!10-7!=10!7!3!=120Чтобы выбрать формулу для решения задачи, т.е. ответить на поставленный вопрос, для примера разберем такие две задачи.

1. В классе 25 учащихся. Сколькими способами можно выбрать 4 – х человек для участия в соревновании по бегу на 100 метровке?

2. Сколькими способами можно выбрать 4 человек для участия в соревновании по эстафете 100+200+300+400 м, если в классе обучается 30 человек?

И в первой и во второй задаче выбираем из 25 и 30 по 4.

1 – выбрали, и как они будут распределяться, неизвестно.

2 – выбрали и каждому определили место в эстафете, т.е. разместили. Следовательно, применяем формулу размещения Ank=n!k! где n=30, а k=4.

Подставляем в формулу и получаем

A304=30!30-4!=30!26!=26!∙27∙28∙29∙3026!=27∙28∙29∙30=657720 способами.

А первую задачу по формуле сочетания, т.е. Cnk=n!k!n-k!, n=25, k=4 подставляем в формулу и считаем Cnk=n!k!n-k!C254=25!4!25-4!=25!4!21!Для вычисления нам надо сократить факториалы. Расписываем. В ряд 25! Входит 21!, а 4! Представляем как произведение, т.к. у нас больше нет в числителе факториалов, чтобы сократить. И получаем

C254=25!4!25-4!=21!∙22∙23∙24∙2521!∙1∙2∙3∙4=11∙23∙4∙25=25300способами.

И задачи, решаемые с применением формулы соединений – перестановки.

Вернемся к определению. Размещения из n элементов по n элементов называют перестановками без повторений из n элементов и обозначают Pn.Как получаем по формуле размещений формулу перестановок.

Pn=Ann=n!n-n!=n!0!=n!⇒т.к.0!=1 Pn=n!1. Сколько всего шестизначных четных чисел можно составить из цифр 1,3,4,5,7,9?

Решение. Цифрой единиц четного числа может только четная цифра, т.е. только цифра 4. Остальные пять цифр могут стоять на оставшихся пяти местах в любом порядке. Следовательно, поставленная задача сводится к нахождению числа перестановок из пяти элементов, т.е. n=5 и P5=1∙2∙3∙4∙5=120 указанных чисел.

Тест



п/п1

2

3

4

5

6

7

8

Вопросы

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

С75=Определение размещения

С94=Основные правила комбинаторики

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

Р7=Определить формулу перестановок

А193=Cnk=Cn+k-1kP102,4,5=Определение сочетания

А128=Что такое факториал?

7!

Ответы

a) складывает числа

в) раздел математики…

а)=2520

в)=21

а) n – элементное множество

в) комбинация

а)=126

в)=3024

а) деление и вычитание

в) сложение и умножение

а) =1

в)=160а) n размещают

в) соединения с повторениями элементов

а)=1340; в) 720

а)Pnв) Cn+kkа)=361; в) 5659

а) размещения

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

а)=1270; в) =495

а) k – членные комбинации без повторений

в) n комбинаций из множества

а)=11880; в) 495

а) k=±1, ±2,…в) k∈N произведение

а) =1540; в) 720

Ключ к ответам

№ задания

1

2

3 Правильный ответ

в, в

а, в

в, а № задания

4

5

6 Правильный ответ

в, а

а, в

в, в № задания

7

8 Правильный ответ

а, а

в, а