Комбинаторна задача

[poankare56]

Колко са десетцифрените числа, записани само с цифрите 2 и 5, такива че няма две цифри 2 една до друга?
Задачата и преди е пускана във форума, но е решена само чрез съображения за свойствата на числата на Фибоначи.

[vezni]

Да, има връзка с числа на Фибоначи, но не е необходимо да ползваме някакви факти, свързани с тях. Ако с [tex]a_n[/tex] означим броят на [tex]n[/tex]-цифрените числа, записани с [tex]2[/tex] и [tex]5[/tex], в които няма съседни двойки, намираме [tex]a_1=2,a_2=3[/tex] и се извежда, че [tex]a_n=a_{n-1}+a_{n-2}[/tex] (като се разделят [tex]n[/tex]-цифрените числа на две групи: завършващи на [tex]5[/tex] и завършващи на [tex]52[/tex]). Оттук можем да намерим [tex]a_3=a_1+a_2=5,a_4=a_3+a_2=8,\dots,a_{10}=144[/tex] и редицата в случая е тази на Фибоначи, изместена с [tex]2[/tex] члена. Ако задачата беше друга, можеше примерно да излезе [tex]a_n=a_{n-1}+n^2[/tex], което е съвсем различна редица. В крайна сметка не виждам защо трябва да се мъчим със случаи, броене и т.н., след като има такова просто решение.

И все пак един вариант за директно броене: разглеждаме случаи според броя на двойките. Има "само" [tex]6[/tex] случая (от [tex]0[/tex] до [tex]5[/tex] двойки).

[peyo]

Това може да е малка приятно задача по програмиране с рекурсивно решение. Така един начин без Фибоначи е да ги преброим с програма:

Код: Избери целия код

In [21]: def count(previous=None,n=0):
    ...:         if n == 10:
    ...:             return 1
    ...:         if previous is 2:
    ...:             return count(5,n+1)
    ...:         else:
    ...:             return count(2,n+1) + count(5,n+1)
    ...:
    ...: count()
    ...:
Out[21]: 144

[poankare56]

Така е, vezni, ако човек съобрази рекурентната връзка, то задачата няма да е трудна за решение. И все пак, току-що чрез характеристичното у-ие изведох обща формула, която, за да се получи краен отговор, трябва да се повдига на 10 степен.