Альтернативный подход к задаче с буквами и словами

Математика Комбинаторика
1

Допустим, нам надо определить, сколькими способами мы можем собрать слова, состоящие из 5 букв из 10 разных букв, при условии, что буквы не должны повторяться, а порядок нам важен (т.е АБВГД и АБВДГ не идентичны друг другу). Мне бы хотелось конкретнее узнать, как можно по другому решить эту задачу, не прибегая к формуле \frac{n!}{(n-k)!} . Вот мой способ :

В первую букву слова мы можем написать 10 букв, во вторую букву слова 9 букв, в третью букву слова 8 букв, и так в последнюю, пятую букву слова мы можем написать 6 букв. Теперь, пойдем от обратного. Рассчитаем, сколькими способами можно собрать слово, состоящее из одной буквы , имея при этом 6 букв. Ответ ясен и без расчета, 6.
Затем, рассчитаем, сколькими способами можно собрать слово, состоящее из двух букв, имея при этом 7 букв, и так, чтобы буквы не повторялись. В первую букву слова мы можем написать 7 букв, а во вторую букву слова можем написать лишь 6 букв. Поскольку все 7 вариантов первой буквы будут иметь 6 вариантов написания со второй буквой, в итоге имеем 7*6 способов
Попробуем рассчитать, сколькими способами можно собрать слово, состоящее из трех букв, имея при этом 8 букв, и так, чтобы буквы не повторялись. В первую букву слова мы можем написать 8 букв. Поскольку есть 7*6 способов собрать слово, состоящее из двух букв, при этом не повторяющихся, все 8 вариантов первой буквы будут иметь 7*6 вариантов написания со второй и третьей буквами. В итоге имеем 8*7*6 способов.
По такой цепочке можно дойти до интересующего нас вопроса, и ответом будет являться 10*9*8*7*6 способов, что и получается при использовании готовой формулы.

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

1 лайк
2

Да, и этого достаточно, и не нужно так детально объяснять, что эти значения надо перемножить)

Но вообще, если объяснять произведение, можно так:
Если есть две ячейкич, и для них есть n и m вариантов соответственно, то для каждого варианта первой ячейки есть m вариантов второй. Поэтому в общем mn вариантов.

4 лайка
3

Так ты не смотрел игру в слова что ли? Я ее столько раз скидывал уже :slightly_frowning_face:.

Ну вообще, искать “более простой” способ незачем, потому что твой довольно интуитивный и объясняет, почему мы должны все числа перемножать. Но есть еще способ.

Я немного переделаю твой пример ради забавы, надеюсь, аналогия будет понятна. Допустим, у нас n букв, которые соревнуются за награду “идущий к реке” на этом форуме. Вот они:

\underbrace{A_1 \quad A_2 \quad C \quad D \quad E \quad F \quad G \quad H \dots}_{n}

Скажем, k из них случайным образом ее получат. Тем буквам, которые получат эту награду, мы присвоим шапки, дабы выделить их среди простого народа. Ну один из вариантов такой:

\underbrace{\overbrace{\hat{A_1} \quad \hat{A_2} \quad\dots \quad \hat{D} \quad \hat{E}}^{k} \quad F \quad G \quad H \quad I \quad J \dots}_{n}

Все, что нам интересно — сколько есть способов распределить эти k шапок среди n букв. Ты уже доказал, что это будет n! (количество перестановок этих букв), но мы не говорили, что нам важна их очередь. Нам было важно только то, выдаем ли мы награду букве, поэтому все шапочники идентичны, ровно как и все бесшапочники.

Каждое из уникальных распределений повторится ровно k! \cdot (n-k)! раз. (Чтобы не делать пост слишком длинным, возьму это как данное. Объяснение показал Трушин в видео из самого начала.)

Значит уникальных способов распределить эти шапки существует \displaystyle\frac{n!}{(n-k)! \ k!}. Но ты сказал, что очередь нас волнует. Поэтому, внесем одно изменение в мою аналогию — пусть шапки будут не одинаковыми; пусть тот, кто получит награду первым, будет носить шапку с надписью “ПЕРВЫЙ!”, кто получит вторым — с надписью “2”, третьим – “3” и так далее до шапки с надписью “k”. Тогда для каждого способа из \displaystyle\frac{n!}{(n-k)! \ k!} способов мы можем выстроить “идущие к реке” буквы в отдельную очередь. Сделать это можно, как мы поняли, k! способами. Тогда и получим формулу, которую ты показывал изначально.

\frac{n!}{(n-k)! \ k!} \cdot k! = \frac{n!}{(n-k)!}

Можно понимать это так, но на самом деле нам бы просто не пришлось делить все на k!, что будет понятно если понимать для чего мы в принципе делили на него. На (n-k)! домножать не надо, потому что нам все еще без разницы, в какую очередь выстроят себя простые буквы; нас волнуют только “идущие к реке”.

Некоторые знают, почему там две буквы A. В любом случае, никого не хотел никать задеть, все только ради забавы :slightly_smiling_face:.

6 лайков