Задачи к лекциям по ТВ.
Элементарная комбинаторика

Задачи к лекциям по ТВ. Элементарная комбинаторика
Основное в теории и примеры решения задач.
Задачи (утверждения), которые надо уметь решать (доказывать) на экзамене/зачете.
В РАБОТЕ !!!
1. Элементарная перечислительная комбинаторика
>
>
Теор
минимум
Задачи с
решениями
Типичные
задачи
К зачету
экзамену
Определения
Основная теорема
Идея подсчета количества разных выборок
Урновые задачи
Задачи размещения по ящикам
1. Из множества всех последовательностей длины n, состоящих из цифр 0, 1, 2, случайно выбирается одна. Найти число возможных последовательностей:
а) последовательность содержит ровно m + 2 нуля, причем два из них находятся на концах последовательности,
б) последовательность содержит ровно m единиц,
в) в последовательности ровно m_0 нулей, m_1 единиц, m_2 двоек.
Решение.
A – начало последовательности никак не зависит от продолжения, поэтому P(A)=1/3
B – Последовательностей, которые начинаются и заканчиваются нулем, 1/9=1/3*1/3 от общего числа последовательностей. Всего таких последовательностей 3^{n-2}. Из них C_{n-2}^{m}*2^{n-m-2} содержат нули (n\geq m+2). Итого P(B)=(1/9)* C_{n-2}^{m}/3^{n-2}.
C – Если выбрать из n C_n^m , то их можно положить равными 1, тогда оставшихся наборов из n-m элементов (n\geq m), составленных из 0 и 2 будет 2^{n-m} штук. Всего требуемых наборов будет C_n^m*2^{n-m} штук. P(C)= C_n^m*2^{n-m}/3^n.
D – нули выбрать можно C_n^{m_0} способами. Из оставшихся n-m_0 элементов единицы можно выбрать C_{n-m_0}^{m_1} способами, а остальными и так будут двойки, т.к. m_0+m_1+m_2=n, так что всего имеем C_n^{m_0} C_{n-m_0}^{m_1} способов. P(D)= C_n^{m_0} C_{n-m_0}^{m_1}/3^n.
1. Доказать, что:
а) трёхзначных чисел бывает 9 • 10 • 10 = 900;
б) трёхзначных чисел, все цифры которых различны, существует 9 • 9• 8.

2. Найти количество различных результатов в следующих экспериментах:
а) из алфавита выбирают три разные буквы и составляют слово;
б) из различных ненулевых цифр составляют трёхзначное число;

3. Найти количество различных результатов в следующих экспериментах:
а) из колоды в 36 карт выдают три карты одному игроку;
б) из двадцати учеников класса выбирают троих дежурных.

4. Найти количество различных результатов в следующих экспериментах:
а) пятизначное число составляют из одних нечётных цифр.
б) обезьяна напечатала на машинке слово из десяти букв;
в) составляют слово длиной в 10 символов из нулей и единиц;

5. Найти:
а) количество способов разложить число k \in N в сумму n целых неотрицательных слагаемых, если важен порядок следования слагаемых;
б) число возможных результатов подбрасывания двух игральных костей, если кости считаются неразличимыми. То же самое для трёх игральных костей.

1) Сколько различных производных порядка k дифференцируемой функции n переменных.
2) Сколькими способами можно разместить n неразличимых между собой частиц в N различимых ячейках (ящиках), пронумерованных номерами от 1 до N.
2. Элементарный подсчет вероятностей
>
>
Теорминимум