Комбинаторный анализ

1. Сколько всевозможных ≪слов≫ можно составить из слова ТРАНСЦЕНДЕНТНО (использовав все
буквы), в которых содержится хотя бы одно из слов ≪трон≫ и ≪театр≫?
2. Используя принцип включения и исключения, определить количество ≪слов≫, которые можно составить из слова ИНТЕЛЛИГЕНТ (использовав все буквы) так, чтобы одинаковые буквы не стояли
рядом?
3. На новогоднем костюмированном празднике Дед Мороз раздает детям шоколад шести различных
сортов: Сказка, Мишка на севере, Красная Шапочка, Аленка, Белочка, Петушок (шоколада у Деда
Мороза – неограниченное количество).
1) Сколькими способами Дед Мороз может подарить по одной шоколадке различных сортов четырем ≪одинаковым≫ Снежинкам?
2) Сколько способов угостить Бабу Ягу, Снеговика и Фею, дав каждому из них по одной шоколадке
различных сортов?
3) Сколько способов дать каждому из тех же трех сказочных героев по две различных шоколадки?
4) Сколькими способами Дед Мороз может распределить 12 ≪Сказок≫ и 7 ≪Белочек≫ между
Волком, Лисой и Зайцем, если каждый из них должен получить по крайней мере по одной
шоколадке каждого сорта?
4. Докажите, не используя алгебраических преобразований, что
∑m
k=0
C
k
mC
r+k
n = C
m+r
m+n
.
5. Оля, Алена, Настя, Дима, Максим и Таня выбирают подарки к Новому Году для своих близких и
друзей. Каждый из них должен приобрести хотя бы один подарок. Оле и Алене нужно купить не
более, чем по три подарка; Насте, Диме и Максиму потребуются как минимум по два, но не более,
чем по четыре; Таня же должна выбрать в точности четыре. Постройте производящую функцию
для подсчета количества способов, которыми ребята могут приобрести r подарков на всех. Сколько
способов выбрать 17 подарков?
6. Используя производящие функции решите рекуррентное соотношение
an = an−1 + 2(n − 1), a0 = 2.
7. Постройте ладейную доску, моделирующую перестановки из S6, в которых i не может появляться
в позициях i и 2i(mod 6). Найдите соответствующий ладейный многочлен и используйте его для
подсчета количества таких перестановок.

-