Комбинаторика. Тройки слов...

[rhggco]

Пипл, помогите плиз разобраться с такой задачей:
Определить число троек слов ( \alpha, \beta ,\gamma ) длины 12 в латинском алфавите, таких что два слова имеют 4 общих буквы и два слова имеют 3 позиции, символы в которых совпадают.
Подскажите ход решения. Заранее спасибо.

[Евгений Б.]

Латинский алфавит имеет 26 букв: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Три 12-тибуквенных слова:


В 8-ой позиции первого и второго слов символы совпадают(A=A)
Таких позиций должно быть 3 (символы, разумеется, могут быть и любые другие кроме A, и не обязательно у первых двух слов)

Первое и третье слово имеют 4 общих буквы: (F R K N). Они не обязательно должны быть на одинаковых позициях, хотя и могут, кроме того, надо учесть, что одновременно могут быть равны буквы на определённой позиции и они же могут быть общими.

[Архипов]

Молодец, Евгений Б.
Так должно оформляться условие составителями.задачи.
Или так:
а) 1.. 2.. 3.. 4.. 5.. 6.. 7.. 8.. 9..10 11 12
б) 3.. 4.. 5.. 6.. 7.. 8.. 9.. 1.. 2..10 11 12
в) 13 14 15 16 17 18 19 20..1.. 2.. 3.. 4..
Требуется уточнение условий задачи.
Сказано:
1) только три символа в верхней паре имеют одинаковые позиции и одинаковый вид (остальные символы одинаковые, но не совпадают в позициях).
2) только четыре символа в нижней паре имеют одинаковый вид (остальные символы в нижнем слове отличны от верхних двух, одинаковых по набору символов)
Соблюдая эти условия, израсходовали 20 символов, в запасе осталось 6.
Вопрос: чем должна отличаться эта тройка слов от следующей возможной тройки?
В задаче не сказано.
"Определите число троек слов" следует понимать как "найдите максимально возможное количество троек слов, отличающихся набором символов"?
Тогда можно подставлять 1 или 2 или 3 или 4 или 5 или 6 оставшихся символов, то есть 7 вариантов возможны (включая образцовый). Либо 6*5*4*3*2*1 вариантов замещающих умножить 20*19*18*17*16*15 вариантов заменяемых.

[rhggco]

А можно ли ее решить "деревом" случаев, как-то так зовется этот метод. В принципе интересует именно этот метод. Каков принцип в общих чертах?

Цитата:

Вопрос: чем должна отличаться эта тройка слов от следующей возможной тройки?
В задаче не сказано.

Сложно сказать, так как кроме имеющегося условия не известно ничего...
Спасибо за ответы

[Danila88]

$m$-число букв в алфавите
$n$-размерность слова
$k$-число совпадающих букв
$z$-число совпадающих позиций

Число слов с $k$ фиксированными буквами
$C_k^n$$C_{m-k}^m=A$
Число возможных пар слов с $k$совпавшими буквами
$3AA$
Число слов с совпавшими по позиции с $z$ букв из $k$
$3C_z^kC_k^n$
Как объеденить два последних выражения, мозги никак не сообразят...

[Архипов]

rhggco в сообщении #175545 писал(а):

А можно ли ее решить "деревом" случаев, как-то так зовется этот метод. В принципе интересует именно этот метод. Каков принцип в общих чертах?

Это и есть основной метод решения задач комбинаторики
В задаче указывается пример двух комбинаций, откуда мы начинаем строить "дерево", различая предыдущую комбинацию от следующей.
Например:
дан набор букв АБВГД
Нужно набрать максимальное количество слов из 3 букв, отличающихся друг от друга одной буквой. Строим:
АБВ
АБГ
теперь следующую букву из наболра вставляем в следущее слово....
И так далее, пока все возможные варианты не переберем.
Потом считаем их количество (заметив закономерность, можем вывести формулу для вычисления этого количества через сложение или умножение).