Сколько можно составить различных 3 буквенных слов из данных букв

Question

Есть набор символов (букв): Д (5 шт), Ф (7 шт), К (2 шт), Н (3 шт), А (4 шт). Нужно вычислить количество уникальных последовательностей из этих символов длиной 3 и длиной 4. Помогите, пожалуйста! Это задача, которую никак не могу решить программно методом комбинаторики, без перебирания вариантов. Реализация пойдет через Python, однако, это не играет никакой роли, так как нужен не код, а логика подсчета вариантов.

Answer 1

Можно подсчитать рекурсивно.

В общем случае:

Мы должны посчитать количество уникальных слов длинны l (l>0). Пусть k — количество наборов букв, а b - минимальное количество букв (B) в наборе.

Тогда:

В случае если b >= l, то количество уникальных слов равно k^l (Т.к. b минимально).

В случае если b < l:

Пусть i — количество букв B в конечном слове.

Для каждого i ( 0 <= i <= b ) количество вариантов того, как располагаются буквы B в конечном слове, можно определить количеством сочетаний: С^l_i.

Общее количество конечных слов для каждого варианта можно найти, если перемножить его на количество слов длинны l-i, составленных из наборов букв, среди которых нет набора с буквой B.

Суммарное количество будет искомым.

Таким образом:

import math

def uniq_seq_count(array, length):    
    if not array:
        return 0;
    
    b = array.pop()
    
    if b >= length:
        return pow(len(array)+1, length)
        
    count = 0
    
    for i in range(b+1):
        count += math.comb(length, i) * uniq_seq_count(array[:], length-i)
        
    return count;

a = [5, 7, 2, 3, 4]
l = 3

a.sort(reverse=True)

print (uniq_seq_count(a, l))

БЛОГ НА HUSL

Сколько можно составить различных 3 буквенных слов из данных букв

Ответы (1 шт):