Matematické Fórum

Tomy · 09. 12. 2009 18:02

Dobrý den, nemohl by mě někdo prosím poradit jak na tento příklad?
Kolik x-ciferných čísel lze sestavit z číslic 3,4,5 aby vedle sebe nestály dvě 3.

check_drummer · 09. 12. 2009 20:06

Zkusíme pomocí rekurentní rovnice:
Nechť $T_3(x)$ značí, kolik čísel délky x lze dle zadání sestavit tak, aby první číslicí byla 3.
Nechť $T_y(x)$ značí, kolik čísel délky x lze dle zadání sestavit tak, aby první číslicí nebyla 3.
(Požadovaný počet čísel délky x je potom $T_3(x) + T_y(x)$ .)

Potom: $T_3(1) = 1$ , $T_y(1) = 2$ , $T_3(x) = T_y(x-1)$ , $T_y(x) = 2(T_3(x-1)+T_y(x-1))$

Eliminujme $T_y$ dosazením do druhé rovnice: $T_3(x+1) = 2(T_3(x-1)+T_3(x))$ .
Počáteční podmínky jsou: $T_3(1) = 1$ , $T_3(2) = 2$
A požadovaný počet čísel tedy: $T_3(x) + T_3(x+1)$ , což je $T_3(x+2)/2$

Tedy jsme dostali modifikovanou fbonnaciho posloupnost, kdy předchozí dvě čísla posloupnosti nejen sečteme, ale následně i vynásobíme dvěma. Zjištění hodnoty $T_3(x)$ explicitně bez rekurentního odkazu na předchůdce by mohlo být možné - snad by k tomu posloužila modifikace postupu použitého u fibonacciho posloupnosti využívajícího vytvořujících funkčí. Ale to už bych nechal na někoho jiného. :-)

Kondr · 09. 12. 2009 21:04

Jo, taky bych to řešil rekurzí, akorát jen s jednou funkcí T(x) udávající počet vyhovujících čísel délky x. Vyhovující číslo buď má na konci trojku, před ní některou ze zbylých dvou cifer a před tím některé z T(x-2) vyhovujících čísel, nebo končí čtyřkou či pětkou, před kterými je jedno z T(x-1)vyhovujících čísel. Máme tak T(x)=2T(x-1)+2T(x-2).

Možná ale bylo myšleno použít princip inkluze a exkluze.

Tomy · 13. 12. 2009 18:43

Děkuji za pěkné vysvětlení, avšak jsem chtěl vyzkoušet ty vzorce a jestliže chci zjistit kolik lze takto sestavit 3 ciferných čísel vychází mí podle vzorce T3(3+2)/2 = 18. Ale když si možnosti vypíšu tak jich mám 22 :-( Nevíte kde dělám chybu?

3xx |x3x |xx3 |xxx |
-----|-----|-----|-----|
345 |434 |443 |454 |
344 |535 |553 |545 |
355 |435 |453 |444 |
354 |534 |543 |555 |
| |343 |445 |
| |353 |554 |
| | |544 |
| | |455 |

check_drummer · 13. 12. 2009 19:41

↑ Tomy:

Ale T3(3+2) = 44. Posloupnost T3 vypadá: 1, 2, 6, 16, 44, ...

Tomy · 13. 12. 2009 23:48

check_drummer, díky pravda, neuvědomil jsem si to s tou fibbonaciho posloupností. Můžu se ještě zeptat jak jsi se dostal k $T_3(x) + T_3(x+1)$ ?

check_drummer · 14. 12. 2009 17:50

To je T3 + Ty.

Matematické Fórum

#1 09. 12. 2009 18:02

kombinatorika

#2 09. 12. 2009 20:06

Re: kombinatorika

#3 09. 12. 2009 21:04

Re: kombinatorika

#4 13. 12. 2009 18:43

Re: kombinatorika

#5 13. 12. 2009 19:41

Re: kombinatorika

#6 13. 12. 2009 23:48

Re: kombinatorika

#7 14. 12. 2009 17:50

Re: kombinatorika

Zápatí