Сайт підготовки до олімпіади з інформатики

ема. КОМБІНАТОРНІ ОБ'ЄКТИ

Тема. Комбінаторні задачі

Комбінаторика - розділ математиків, в якому вивчаються найпростіші «з'єднання» чисел.

1) Формули комбінаторики

Задачі:

1.        Скількома способами можна скласти розклад на день з  5 різних предметів, якщо в класі вивчається 10 предметі?

2.        Скільки різних чотирицифрових чисел можна скласти з чотирьох різних заданих цифр, не повторюючи їх?

3.        Скільки діагоналей має опуклий n-кутник?

1.Перестановки - з'єднання, які можна скласти з  n предметів, міняючи всіма можливими способами їх порядок.

Pn=n!

2.Розміщення - з'єднання, що містять по  n предметів з числа  m даних, що розрізняються або порядком предметів, або самими предметами.

An,k=n!/(n-k)!

3. Комбінації - з'єднання, що містять по  n предметів з  m, що розрізняються один від одного, принаймні, одним предметом.

Cn,k=n!/((n-k)!k!)

Додаткові завдання:

1. Скількома способами можна розподілити n тем наукових робіт серед m учнів (тем більше, ніж учнів). Написати програму.

2. Перевірити справедливість рівності C0,k+c1,k+...+Ck.k=2^k для m<10.

3. Скількома способами можна розмістити n осіб за столом, біля якого поставлено nстільців?  Написати програму.

4. Двоє хлопчиків Роман і Діма мають по N друзів (1<=N<=200). Вирішили вони позмагатися хто з них більше організує вечірок. Роман вирішив запрошувати кожен раз до себе в гості по K(1<= K<= N) друзів, а Діма - по М (1<= М<= N) друзів. Хто з хлопчиків більше організує вечірок і на скільки, якщо вони домовились, що кожен раз компанія має бути іншою.

Наприклад.

Якщо є четверо друзів (1, 2, 3, 4) і вони мають приходити в гості по троє, то таких вечірок буде чотири ( (1, 2, 3); (1, 2, 4); (1, 3, 4); (2, 3, 4) ).

5. Скількома способами можна вибрати делегацію в складі n представників з m чоловік. Написати програму.

6. Побудувати трикутник Паскаля з n рядків

1

1 2 1

1 3 3 1

.....