57 школа, 9 класс
20 апреля 2002 г.
Комбинаторика

1.    Сколько различных слов (не обязательно осмысленных) можно получить, переставляя буквы в слове АБРАКАДАБРА?

2.    а)    Чему будет равен коэффициент при xa yb после раскрытия скобок  и приведения подобных в выражении (x + y)n?
б)    Найдите коэффициент при xaybzc в многочлене (x + y + z)n.
в)    Найдите коэффициент при xaybzctd в многочлене (x + y + z + t)n.

3.    Даны числа n и N. Найдите количество решений:    
а)    неравенства X1 < X2 < ... < Xn < N в натуральных числах;
б)    неравенства X1 + X2 + ... + Xn < N в натуральных числах;
в)    уравнения X1 + X2 + ... + Xn = N в натуральных числах;
 г)    уравнения X1 + X2 + ... + Xn = N в целых неотрицательных числах.

4.    Одновременно бросают 6 разных игральных костей. Существует 66 возможных результатов броска.
Среди всех возможных результатов броска выделим те случаи, где выпало хотя бы три двойки. Обозначим через n количество таких случаев. Число n/66 называется вероятностью того, что выпадет хотя бы 3 двойки.
Найдите вероятность того, что выпадет:
а)    хотя бы три двойки
б)    (Каре) ровно четыре одинаковых числа
в)    ровно пять одинаковых чисел
г)    шесть одинаковых чисел
д)    (Стрит) 1, 2, 3, 4, 5 и 6
е)    две тройки одинаковых чисел (и нет четырех одинаковых)
ж)    три пары одинаковых чисел (и нет четырех одинаковых)
з)    (Шведка) одна пара и одна тройка одинаковых чисел (нет четырех одинаковых)
и)    сравните полученные вероятности.

5.    Найдите коэффициент при xk, где k < 100, в многочлене (1 + x + x2 + ... + x100)n.

6.    Найдите количество представлений числа N в виде суммы нескольких натуральных слагаемых (представления, отличающиеся порядком слагаемых, считаются различными).

7.    В парламенте N депутатов. Нужно установить на двери зала заседаний несколько замков и каждому депутату выдать свой набор ключей, так чтобы депутаты могли войти в зал в том и только том случае, если у них есть кворум, то есть пришло по крайней мере k депутатов. Какое наименьшее число замков необходимо установить, кому какие ключи нужно раздать?

8.    Сколькими способами можно раскрасить вершины данного n-угольника, если имеется q тюбиков с разными красками, и нельзя красить соседние вершины в один цвет?