КІЛЬКІСТЬ СЛІВ ДОВЖИНИ k ІЗ ДАНИХ n БУКВ,

КІЛЬКІСТЬ СЛІВ ДОВЖИНИ k ІЗ ДАНИХ n БУКВ,

ЩО НЕ МІСТЯТЬ ДАНЕ ПІДСЛОВО ДОВЖИНИ m

Задача. Скласти алгоритм, щоб підрахувати кількість слів  з довжиною в  К будь-яких літер при цьому їх порядок не важливий  із даних N різних букв, що не містять літери слова, яке має довжину M будь-яких літер при цьому їх порядок не важливий , якщо M<=К<=N.

Технічні умови. Цілі числа K,  N,  M такі, що   0<K<4, 1<N<20, 0<M<4

Розв′язання. Для початкових значень запишемо таблицю:

	К=0	К=1	К=2	К=3	К=4
М=0	0	n	nk	nk	nk
М=1	0	n-1	nk-kmn+mk
М=2	0	0	nk-kmnk-1+mk
М=3	0	0	0

Дане завдання, взагалі   вимагає особливого алгоритму, тому

 Покажемо, як можна міркувати, якщо не потрібно надрукувати всі слова, а тільки дізнатися їх число.

Простий випадок. Елементи вихідної послідовності-алфавіту різні, слово залежить від порядку букв. Якщо у вихідній послідовності є однакові літери, то треба буде дещо підкоригувати (їх-то порядок не важливий буде в слові, якщо стоять поруч). Це зробимо потім. Кожен елемент алфавіту ми можемо використовувати в слові із  m літер один раз.

По ідеї всі слова розміру К з N літер буде обчислюватися так: для К=1  маємо N усіх можливих  випадків, для к=2 маємо N²  усіх можливих  випадків,  і так далі,  - для слова на К літер із N букв   загалом (1) N^k.

З цього треба відняти всі послідовності, що містять дану підпослідовність із  m літер. Скільки таких?

Шукаємо усі підпослідовності довжини m  до К фікс. Частиною довжини m.

    Нехай фікс. частина на початку - фіксована частина слова із m букв – тоді  можемо переставляти к- m+1 раз

Можливостей для зміни - n^k-m. Далі можна зрушити k-m раз вправо сю фікс. частина, отримавши таким чином ще (k-m)n^k-m слів. Тоді всього можливо (2) (k-m + 1)n^k-m   слів довжини К з N букв, що містять дану підпослідовність довжини m.

Віднімаємо (1) з (2):   1+ N^k - (k-m + 1)n^k-m   - отримуємо шукане число.