Сочетания без повторений

Решим задачу: сколькими способами из множества можно составить всевозможные подмножества по k элементов каждое?

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

.

Но нас не интересует порядок элементов, выбранный в вектор длины k, а интересует лишь состав. Тогда среди различных векторов k! штук имеют одинаковые компоненты и отличаются лишь их порядком. Таким образом, сочетаний будет в k! раз меньше, чем размещений

.

Число сочетаний без повторений обладает следующими свойствами:

; ;

; ;

.

Удобно, также помнить, что .

Пример. Из 1, 2, 3, 4 упорядоченных пар можно составить .

12 13 14 23 24 34

21 31 41 32 42 43

При таком расположении заметно, что эти пары можно составить, выбрав сначала в пару какие-то 2 элемента, а затем составить все возможные векторы, переставив данный состав 2! различными способами. Значит, если считать пары, отличающиеся только составом, то их будет в 2! раз меньше, чем .

Пример. Сколько существует различных способов заполнения карточек “Спортлото” 6 из 49? Нам надо выбрать неупорядоченные подмножества размерности k = 6 из множества Х, n= 49.

ЗАДАЧИ

1.Определить, обладает ли следующая группа событий свойствами группы случаев:

а) Испытание состоит в бросании 2х монет.

А - выпал хотя бы один герб;

А - выпала хотя бы одна решка.

б) Испытание состоит в 2х выстрелах по мишени.

А - ни одного попадания;

А - ровно одно попадание;

А - ровно два попадания.

в) Испытание состоит в бросании игральной кости.

А - выпало нечетное число очков;

А - выпало четное число очков.

2.Среди студентов, собравшихся на лекцию по ТВ, выбирают наудачу одного. Событие А = ²выбран юноша²; В = ²не курит²; С = ²живет в общежитии².

а) Описать событие .

б) При каком условии будет иметь место тождество АВС = А?

в) Когда будет справедливо соотношение ?

г) Может ли быть верным равенство , если все юноши курят?

3.Пусть А, В, С - три произвольных события. Записать выражения для событий, состоящих в том, что из событий А, В, С:

а) произошло только А;

б) произошло А и В, но С не произошло;

в) все три события произошли;

г) произошло, по крайней мере, одно из этих событий;

д) произошло, по крайней мере, два события;

е) произошло одно и только одно событие;

ж) произошло два и только два события;

з) ни одно событие не произошло;

и) произошло не более двух событий.

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

5.Староста одного класса дал следующие сведения об учащихся: ”В классе учатся 45 школьников, в том числе 25 мальчиков. 30 школьников учатся на хорошо и отлично, в том числе 16 мальчиков. Спортом занимаются 28 учеников, в том числе 18 мальчиков и 17 учеников, учащихся на хорошо и отлично. 15 мальчиков учатся на хорошо и отлично и занимаются спортом.”

Докажите, что в этих сведениях есть ошибка.

6.Сколько чисел среде первых 100 натуральных чисел не делятся ни на 2, ни на 3, ни на 5, ни на 7?

7.На железнодорожной станции имеется 10 путей. Сколькими способами можно расставить на них 3 состава?

8.Из 30 букв алфавита составлено слово длины 6. Сколькими способами это можно сделать? Сколькими способами это можно сделать так, чтобы:

а) в слове была ровно одна буква А;

б) в слове было ровно две буквы А;

в) в слове было ровно 5 букв А;

г) в слове была хотя бы одна буква А.

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

10. Для премии на математической олимпиаде выделено 3 экземпляра одной книги, 4 экземпляра другой и 8 экземпляров третьей. Сколькими способами могут быть распределены эти книги между 30 участниками, если каждому вручается не более одной книги?