Размещения с повторениями

«Опять восьмёрка!» - горестно воскликнул председатель клуба велосипедистов, взглянув на погнутое колесо своего велосипеда. «А всё почему? Да потому, что при вступлении в клуб мне выдали билет за номером 008. И теперь месяца не проходит, чтобы то на одном, то на другом колесе не появилась восьмёрка. Надо менять номер билета. А чтобы меня не обвиняли в суеверии, проведука я перерегистрацию всех членов клуба и буду выдавать только билеты с номерами, в которые ни восьмёрка, ни нуль не входят».

Сказано – сделано, и на другой день он заменил все билеты. Сколь членов было в клубе, если известно, что использованы все трёхзначные номера, не содержащие ни одной восьмёрки и ни одного нуля?

Для решения этой задачи определим сначала, сколько будет однозначных номеров. Ясно, что таких номеров будет восемь: 1 2 3 4 5 6 7 9.

А теперь найдём все двузначные номера, для чего возьмём любой из найденных однозначных номеров и припишем к нему любую из восьми цифр:

11 12 13 14 15 16 17 19

21 22 23 24 25 26 27 29

31 32 33 34 35 36 37 39

41 42 43 44 45 46 47 49

51 52 53 54 55 56 57 59

61 62 63 64 65 66 67 69

71 72 73 74 75 76 77 79

91 92 93 94 95 96 97 99

Очевидно, двузначных номеров будет . Но за каждым из них снова можно поставить любую из восьми допустимых цифр. В результате получим трёхзначных номеров. Значит, в клубе было 512 велосипедистов.

Задача о велосипедистах относится к следующему типу задач. Даны предметы, относящиеся к различным видам. Из них составляют всевозможные расстановки по предметов в каждой, при этом в расстановки могут входить и предметы одного вида, а две расстановки считаются различными, если они отличаются друг от друга или видом входящих в них предметов, или порядком этих предметов. Надо найти общее число таких расстановок.

Расстановки описанного типа называются k - размещениями с повторениями из элементов видов и обозначается .

Естественно предположить, что если число видов равно , а в каждое размещение входит элементов, то можно составить размещений с повторениями. Итак,