Паскаль. Основы программирования

Перестановки с повторениями


Пример 8. Сколько различных слов, каждое из которых состоит из семи букв, можно составить из букв слова "коробок".

В отличие от предыдущего примера здесь не все буквы слова различны (там были все цифры разными). Если бы все буквы были различны, то из них можно было бы составить 7! различных слов.

Однако не все перестановки букв дают новые слова. Очевидно, что перестановка букв "к", так же как и букв "о", между собой не дают нового слова. Следовательно, рассматриваемая задача свелась к тому, чтобы определить число перестановок, в результате которых получается одно и то же слово. Число перестановок буквы "к" между собой, в результате которых получаются одинаковые слова равно 2! После каждой такой перестановки буква "о" может быть переставлена 3! способами. Применяя правило произведения, получим, что каждое новое слово будет повторяться

 раз, и поэтому число различных слов, которое можно составить из слова "коробок", равно
.

Вообще, пусть дано множество M = {a, b, c, ...}, состоящее из n элементов, из которых элемент a повторяется n1 раз, элемент b - n2 раз, элемент c - n3 раз, ... так, что

Требуется найти число перестановок с заданным числом повторений входящих в него элементов.

Число перестановок в этом случае определяется по формуле:

где

Если
 то из этой формулы получается: 

Программа

 

Program Problem8;

     uses WinCrt;



     var

        s, k1, k2 : longint;

{----------------------------------------------------------------------------------------}

     Procedure Factorial(n : integer;  var f : longint);

           var

              i : integer;

          begin

             f := 1;

             if n = 0 then f := 1

                          else  for i := 1 to n do f := f*i

          end;

{----------------------------------------------------------------------------------------}

     begin

        Factorial(7, s);  Factorial(3, k1);  Factorial(2, k2);

        s := s div (k1*k2);

        writeln('Из слова "КОРОБОК" можно составить ', s, ' различных слов')

    end.



Содержание раздела