![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Термин «сочетание» в его современном значении начал первым употреблять Б. Паскаль. Обозначение C введено в 1880 году первоначально в виде
С
. Второе, принятое в настоящее время обозначение введено Л. Эйлером.
При составлении k – элементных подмножеств n –элементного множества нас не интересует порядок, в котором располагаются элементы.
Например, если имеется 10 сортов ткани и нужно выбрать 4 сорта, то порядок, в котором будут выбраны сорта, не имеет значения. В таких задачах речь идёт о подмножествах, не являющихся упорядоченными.
Определение. Всякое k- элементное подмножество n -элементного множества (k n) называют сочетанием без повторений из n элементов по k.
Число различных сочетаний из n элементов по k обозначают символом C .
Как следует из определения, 2 сочетания считают различными, если они отличаются друг от друга хотя бы одним элементом. Порядок следования элементов в сочетании значения не имеет.
Теорема 8. Число сочетаний и з n элементов по k элементов определяется по формуле:C =
.
ÿ Формула для числа сочетаний легко получается из формул для числа размещений и числа перестановок. Действительно, составив сначала все сочетания из n элементов по k, а затем, переставив всеми возможными способами элементы, входящие в каждое сочетание, получим все размещения из n –элементов по k–элементов. Но из каждого такого сочетания можно составить k! перестановок. То есть справедлива формула:
k! C =A
C
=
=
.
Теорема 8 доказана.
Задача. Из группы студентов, состоящей из 25 человек, надо составить команду из 4 человек для участия в беге на 1000 м. Сколькими способами можно это сделать?
Решение. Порядок следования элементов в данном соединении значения не имеет. Из 25 человек набрать команду из 4 человек можно:
С =
=12650 (способами).
Ответ: 12650 способов.
Вспомним теорему о том, что конечное множество, содержащее п элементов, имеет 2 п подмножеств, то есть если Ап={а1,а2,...,aп }, то п(Р(Ап))=2п.
Напомним также, что принято считать 0! равным 1.
При этом предположении формула С =
остаётся в силе и при k=n, и при k =0 и поэтому имеет равенство:
=2
.
Свойства чисел C
Следующие простые свойства чисел С легко выводятся из факториальной формулы C
=
:
а) ;
б) ;
в) ;
г) .
д) Правило симметрии.
Если 0 k
n, то верно равенство: C
=C
.
Известно, что C =
.
Найдём C =
=
=
.
Следовательно, C =C
.
Утверждение доказано.
е) Для k,n: 0
k
n, верно равенство:
(n + 1) C =(k + 1) C
.
(n + 1) C =
=
;
(k + 1) C =
=
=
= =
.
Следовательно, (n + 1) C =(k + 1) C
.
Утверждение доказано.
ж) Правило Паскаля.
k, n: 0
k
n верно равенство: C
=C
+ C
.
Найдем C :
C =
=
=
;
Найдем C : C
=
=
=
.
Найдём C + C
:
C + C
=
+
=
=
= =
= C
.
з) Для любого m верны равенства:
C + C
+ … + C
=2
;
C – C
+ C
– C
+…+ (– 1)
C
+ … + (–1)
C
=0;
C + C
+ C
+ …=C
+ C
+ C
+ …=2
.
Покажем, как данные свойства можно использовать при решении задач.
Задача 1. Некоторый комитет состоит из 12 человек. Минимальный кворум для принятия решения должен насчитывать 8 человек. а) Сколькими способами может быть достигнут минимальный кворум? б) Сколькими способами может быть достигнут какой-либо кворум?
Решение. а) Искомое число совпадает с С и равно:
С =С
=С
=
=495 (способа)
б) Какой-либо кворум достигается, если на заседании присутствует 8, 9, 10, 11 или 12 членов комитета. Согласно правилу суммы искомое число равно:
C + C
+ C
+ C
+ C
=C
+ C
+ C
+ C
+ C
=
=495 + +
+
+ 1=794 (способа)
(При вычислении мы учли, что 0!=1, и поэтому C =1).
Ответ: а) 495 способов; б) 794 способа.
Задача 2. У 6 взрослых и 11 детей обнаружены признаки инфекционного заболевания. Сколькими способами можно взять выборочный анализ, чтоб изучить течение болезни у 2 взрослых и 3 детей.
Решение. Из 6 взрослых выбрать двух можно:
C =
=15 (способами)
Из 11 детей выбрать трёх можно:
С =
=165 (способами)
Согласно правилу произведения имеется 15 ∙ 165=2 475 способов выбора двух взрослых и трёх детей.
Ответ: 2 475 способов.
Дата публикования: 2015-01-23; Прочитано: 1566 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!