Международный научно-образовательный электронный журнал «образование и наука в XXI веке». Выпуск №10 (том 1)

5. Комбинаторные задачи. Игры 
Комбинаторика имеет дело с перебором вариантов и подсчетом их числа. Рассмотрим 
несколько стандартных задач, которые решаются типичными для комбинаторики 
рассуждениями. 
Задача 1.
Размещения с повторениями.
Рассмотрим алфавит А из n букв. Сколько k-
буквенных слов можно составить из букв этого алфавита? 
Ясно, что число однобуквенных слов равно m( числу букв в алфавите). Пусть А
n
обозначает 
число n-буквенных слов. Как получить все (n+1) - буквенных слова? Надо взять одно n-
буквенное слово и приписать к нему одну букву. Таким образом, с одним и тем же началом 
из n букв у нас получится m различных (n+1) - буквенных слов. Итак, А
n+1
=n•А
n
. Т. К. А
1
=n, 
то А
2
=n•n=n
2
, А
3
=n
3
и т. д. Получаем А
k
=n
k
, т. е. число k - буквенных слов в алфавите из n 
букв равно n
k
. 
Полезно запомнить один частный случай: число последовательностей длины k из символов 0 
и 1 равно 2
k
. 

---

114 
Задача 2.
Размещения без повторений.
Сколько k-буквенных слов с разными буквами можно 
составить из алфавита, содержащего n букв? 
Число однобуквенных слов равно n. Чтобы получить двухбуквенное слово, надо к 
выбранному однобуквенному слову приписать любую букву, кроме той, которая уже 
использована, т. е. одну из оставшихся (n-1) букв. Продолжая процесс дальше, для числа B
k
k - буквенных слов с неповторяющимися буквами получим произведение целых чисел, 
начинающееся с числа n и такое, что каждый следующий множитель на 1 меньше 
предшествующего. Т. к. общее число множителей равно k, то последний будет равен n – (k – 
1)= n-k+1, т. е. B
k
=n(n-1)…(n-k+1), k