19:06 

Трибоначчи такой Трибоначчи...

Раздели Наноль
Я знаю только то, что ничего не знаю. А если подумать - то и этого не знаю.
В конце рабочего дня возникла мысль совместить приятное с полезным, а именно - посетить планерку (дабы не строить иллюзий относительно положения компании), а на ней заняться комбинаторикой.

Вопрос стоял таким образом: имея 1, 2 и 3-х буквенные слоги, сколько комбинаций этих слогов, с учетом последовательности, можно составить для слова известной длины?

Так как я уже заемучался выписывать варианты в столбик, то решил нарисовать дерево. Наверное это граф... в общем строится он таким способом - из 0, то есть пенька растет три веточки, длиной в 1, 2 и 3 буквы, возле кончика ставится длина этой веточки. Потом из каждого кончика растет еще по три веточки тоже длиной 1, 2 и 3 буквы. И возле кончика ставится длина с учетом длины "родительной" веточки. И так далее, пока длина не будет равна количеству букв в слове. При чем надо заметить, что если веточка имеет длину 5, а надо дорасти до 7, то веточка длиной 3 - уже из нее не вырастит, ибо перебор, а вырастет две веточки по 2 и по 1 букве.

Изрисовав страницу, я понял, что весьма накосячил и стал рисовать уже не одно дерево, а три отдельных, которые начинались с одной веточки, длиной соответственно 1, 2 и 3 буквы. Напомню, что я ставил цифры, которые обозначали текущую длину веточки. Потом подсчитал количество этих цифр. И вот что получилось:
1 - 1
2 - 1
3 - 2
4 - 4
5 - 7
6 - 13
7 - 24
для дерева, которое начиналось с однобуквенной веточки.
1 - 0
2 - 1
3 - 1
4 - 2
5 - 4
6 - 7
7 - 13
для начинающегося с двубуквенной веточки,
и для трехбуквенной:
1 - 0
2 - 0
3 - 1
4 - 1
5 - 2
6 - 4
7 - 7
Видно, что начиная с четвертого члена в этой последовательности любой член является суммой трех предыдущих (не считая нули). У этой последовательности забавное название Tribonacci numbers. Если проссумировать все три последовательности (что логично, так как нас интересует общее число комбинаций), получится следующее:
1 - 1
2 - 2
3 - 4
4 - 7
5 - 13
6 - 24
7 - 44
Видим что последовательность как была Трибоначчи, так в принципе ей и осталась) И это очень радует, так как теперь я знаю, что для слова из 7 букв существует 44 комбинации из 1,2 и 3-х буквенных слогов)

Под комбинацией понимается принципиальная схема, а не реальные слоги.

URL
   

Мои прохладные дни

главная