Комбинаторика

[ewert]

Трибоначчи -- это здорово. Не очень понятно, правда, как они сочетаются с фактическими количествами комбинаций:

 n     num

 1       0
 2       0
 3       1
 4       3
 5       8
 6      20
 7      47
 8     107
 9     238
10     520
11    1121
12    2391
13    5056
14   10616
15   22159

Которые, в свою очередь, вполне сочетаются с достаточно очевидным $f_n=2f_{n-1}+(2^{n-4}-f_{n-4})$.

[Ward]

А какой вообще ответ будет?
Например для чисел Фибоначчи есть формула Бинэ.
А тут как?

[ewert]

Ward в сообщении #651364 писал(а):

Например для чисел Фибоначчи есть формула Бинэ.
А тут как?

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

[Ward]

ewert
Спасибо! Теперь все понятно! Благодарю Вас!

[ewert]

Только имейте в виду, что в ответе не буквально числа Трибоначчи (я там листал по диагонали и почему-то показалось, что подсчитываются количества чисел, в которых есть тройки из единиц). У чисел Трибоначчи другие начальные условия.

[Slip]

ewert в сообщении #651362 писал(а):

Трибоначчи -- это здорово. Не очень понятно, правда, как они сочетаются с фактическими количествами комбинаций:

Замечательно сочетаются, учитывая, что Вы выписали количество комбинаций, в которых есть 3 идущих подряд единицы ;)

1   2   = 2^1 - 0
2   4   = 2^2 - 0
3   7   = 2^3 - 1
4   13 = 2^4 - 3    = 2 + 4 + 7
5   24 = 2^5 - 8    = 4 + 7 + 13
6   44 = 2^6 - 20   = 7 + 13 + 24

о, Вы уже и сами это же написали :)

[VAL]

ewert в сообщении #651362 писал(а):

Трибоначчи -- это здорово. Не очень понятно, правда, как они сочетаются с фактическими количествами комбинаций:

 n     num

 1       0
 2       0
 3       1
 4       3
 5       8
 6      20
 7      47
 8     107
 9     238
10     520
11    1121
12    2391
13    5056
14   10616
15   22159

Которые, в свою очередь, вполне сочетаются с достаточно очевидным $f_n=2f_{n-1}+(2^{n-4}-f_{n-4})$.

По-моему, кто-то из нас невнимательно прочитал условие.
Перечитав, его еще раз, склонен полагать, что это не я.

-- 29 ноя 2012, 14:23 --

Ward в сообщении #651369 писал(а):

ewert
Спасибо! Теперь все понятно! Благодарю Вас!

А Вас не смутило, что даже первые, легко вычисляемые в уме значения, из данных, приведенных ewert'ом, противоречат условию?

[Deggial]

Сообщение megamix отделено в новую тему как не относящееся к данной теме.