Кодирование. Комбинаторика.

Основы комбинаторики

Количество возможных слов

1. Если каждая буква выбирается независимо:

   • Слово длины L, где:

     • n₁ — вариантов первой буквы,

     • n₂ — второй, ...,

     • nₖ — k-й буквы.

   • Формула:

     \(N=n_1\times n_2\times …\times n_L\)

2. Если все буквы выбираются из одного алфавита (n способов на каждую букву):

   • Формула:

     \(N=n^L\)

Пример

• Сколько слов из 3 букв руского алфавита можно составить, если:

  • Первая буква — гласная (10 вариантов),

  • Вторая — согласная (21),

  • Третья — любая (33)?

• Решение:

  N=10×21×33=6930 слов

Аналогия с циклами в программировании

Если в программе есть L вложенных циклов, то:

• Внешний выполняется n₁ раз,

• Второй — n₂ раз,

• ...

• Внутренний — nL раз.

Общее число итераций:

Пример:

for i in range(2):       # 2 варианта
    for j in range(3):   # 3 варианта
        print(i, j)

Число итераций: 2 × 3 = 6.