Задачи для самостоятельного решения

1. Пусть имеются три кандидата на место президента фирмы П1, П2, П3 и два кандидата на место вице-президента В1 и В2. Сколькими способами можно осуществить выбор руководящего состава фирмы?

2. У Саши десять марок, а у Вани – двадцать. Сколькими способами можно осуществить обмен одной Сашиной марки на одну Ванину?

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

4. Сколько существует двузначных чисел с разными цифрами?

5. Сколько имеется четырехзначных чисел, составленных из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9, причем:

а) цифры в записи числа не повторяются;

б) числа четны и соседние цифры в записи числа не повторяются.

6. В классе изучают десять предметов. В понедельник шесть уроков, причем все уроки разные. Сколько существует способов составления расписания на понедельник?

7. В классе двадцать человек – десять девочек и десять мальчиков. Сколькими способами можно составить график дежурств по классу на десять дней так, чтобы каждый день дежурил один мальчик и одна девочка, и при этом никто из ребят не дежурил дважды?

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

Размещения

Размещением без повторений из n элементов по k называется кортеж длины k, составленный из неповторяющихся элементов множества в котором n элементов. Два размещения отличаются либо составом элементов, либо порядком следования элементов. Число всех возможных размещений без повторений обозначается  (A – первая буква фр. аrrangement – размещение) и вычисляется по формуле:

или .

Если некоторые элементы кортежа повторяются, то кортеж называется размещением из n элементов по k с повторениями. Число всевозможных размещений с повторениями из n элементов по k равно .

Пример. У Ани есть семь цветных карандашей. Мама нарисовала на листке бумаги девочку и предложила Ане раскрасить ее шапочку, платье и туфельки, используя для каждого предмета одежды один цвет. Сколькими способами Аня сможет раскрасить картинку, если:

а) она решила, что шапочка, платье и туфельки должны быть раскрашены в разные цвета;

б) она готова раскрашивать шапочку, платье и туфельки, как в разные, так и в одинаковые цвета?

Решение. а) Чтобы раскрасить картинку, Аня должна не только выбрать три карандаша, но и решить, каким из них она будет раскрашивать шапочку, каким – платье, каким туфельки. Если мысленно сопоставить картинки, соответствующие разным способам раскрашивания, то они будут отличаться как набором цветов, так и местом их использования. Следовательно, каждый из способов раскрашивания можно интерпретировать как упорядоченную выборку без повторений из 7 элементов по 3. Число таких размещений найдем по формуле .

б) Отличие от ситуации, рассмотренной в пункте а), состоит в том, что для раскраски различных предметов одежды Аня может использовать один карандаш. Значит, каждый способ раскрашивания можно рассматривать как упорядоченную выборку с повторениями из 7 элементов по 3. Число размещений найдем по формуле