Zadanie Willy Wonka

[arek1357]

Wpadło mi ostatnio nietrudne ale fajne zadanie celem odmulenia działu. Znajdź na ile sposobów można zjeść czekoladę...

Dana jest czekolada tradycyjna gorzka o zawartości 80% kakaa, jest podzielona na \(\displaystyle{ m \times n}\) kostek...
Kostki są ponumerowane od \(\displaystyle{ 1,2,3,...,mn}\)....

jemy czekoladę w ten sposób, że odłamujemy z dowolnego boku jeden pasek, a potem z paska odłamujemy kostki ale możemy odłamać z każdego paska tylko kostki końcowe, aż do zjedzenia całego paska, potem odłamujemy następny pasek i analogicznie kostki z niego...
Postępujemy tak aż zjemy całą czekoladę...
Na ile sposobów możemy zjeść czekoladę?

[Gosda]

Przyjemne zadanie Chociaż nie wiem, czy do policzenia. Niech \(\displaystyle{ f(m, n)}\) oznacza liczbę sposobów, wtedy

\(\displaystyle{ f(m, n) = f(n, m)}\)

\(\displaystyle{ f(m, 1) = 2^{m-1}}\)

Jeśli \(\displaystyle{ m, n \ge 2}\), to

\(\displaystyle{ f(m, n) = 2 [f(m, 1) f(m, n-1) + f(1, n)f(m-1, n)]}\)

Stąd wynika, że

\(\displaystyle{ f(n, n) = 2^{n^2 + 1} a_{301560}(n)}\),

gdzie drugi czynnik pochodzi oczywiście z bazy ciągów OEIS (Matching number of the n-odd grap):

Kod: Zaznacz cały

http://oeis.org/A301560

[arek1357]

Jasne , \(\displaystyle{ że f(m,n)=f(n,m)}\)

oraz, że:

\(\displaystyle{ f(n,1)=2^{n-1}}\)

Wszystko ok tylko teraz fajnie by było zapisać wzorem jawnym , ale szczerze nie rozumiem ostatniego a z indeksem jakimś wielkim co to w ogóle jest??

[arek1357]

Pokażę co można było zrobić w celu znalezienia wzoru jawnego:

\(\displaystyle{ f(n+1,m+1)=f(n+1,m)2^{n+1}+f(n,m+1)2^{m+1} / * \sum_{n=1}^{ \infty }x^n }\)

obkładamy to sumą...:

przyjmijmy , że:

(*) \(\displaystyle{ f_{m}(x)= \sum_{n=1}^{ \infty }f(n,m)x^n }\)


\(\displaystyle{ \frac{1}{x} \sum_{n=1}^{ \infty }f(n+1,m+1)x^{n+1} =\sum_{n=1}^{ \infty }f(n+1,m)x^{n+1}2^{n+1}x^n+\sum_{n=1}^{ \infty }f(n,m+1)2^{m+1}x^n}\)

\(\displaystyle{ \frac{1}{x} \left[ \sum_{n=1}^{ \infty }f(n,m+1)x^n-f((1,m+1)x \right]= \frac{1}{x} \sum_{n=1}^{ \infty }f(n+1,m)2^{n+1}x^{n+1}+2^{m+1}f_{m+1}(x) }\)

\(\displaystyle{ \frac{1}{x} \sum_{n=1}^{ \infty } f(n,m+1)x^n-2^m= \frac{1}{x}\left[ \sum_{n=1}^{ \infty } f(n,m)2^nx^n -f(1,m)2x\right] +2^{m+1}f_{m+1}(x) }\)

biorąc pod uwagę (*) otrzymamy:

\(\displaystyle{ \frac{1}{x}f_{m+1}(x)-2^m= \frac{1}{x} \sum_{n=1}^{ \infty } f(n,m)(2x)^n-2^m+2^{m+1}f_{m+1}(x) }\)

można to tak zapisać:

\(\displaystyle{ f_{m+1}(x)( \frac{1}{x}-2^{m+1})= \frac{1}{x}f_{m}(2x) }\)

po przekształceniach mamy:

\(\displaystyle{ f_{m+1}(x)= \frac{f_{m}(2x)}{1-2^{m+1}x} }\)

łatwo dowieść, że:

\(\displaystyle{ f_{1}(x)= \frac{x}{1-2x} }\)

po rozwinięciu w szereg łatwo zauważyć , że:

\(\displaystyle{ f(1,n)=2^{n-1}}\)

po podstawieniach mamy:

\(\displaystyle{ f_{1}(2x)= \frac{2x}{1-4x} }\)

\(\displaystyle{ f_{2}(x)= \frac{2x}{(1-4x)^2} }\)

Indukcujnie łatwo zauważyć , że:

\(\displaystyle{ f_{m}(x)= \frac{2^{m-1}x}{(1-2^mx)^m} }\)

rozwijając w szereg łatwo produkować wzory jawne dla tego ciągu...

Dodano po 8 godzinach 50 minutach 59 sekundach:
Dokończe to:

Zapiszmy to tak:

\(\displaystyle{ h(x)= \frac{1}{2} \frac{2^mx}{(1-2^mx)^m} , t=2^mx }\)

i parę razy przekształćmy to:

\(\displaystyle{ g(t)= \frac{1}{2} \frac{t}{(1-t)^m} = \frac{1}{2} \sum_{n=1}^{ \infty } \frac{1}{(n-1)!}m(m+1)(m+2)...(m+n-2)t^n= \frac{1}{2}\sum_{n=1}^{ \infty } {m+n-2 \choose m-1}t^n= \sum_{n=1}^{ \infty } 2^{mn-1} {m+n-2 \choose m-1} }\)

co daje ostateczny fajny wzór jawny:

\(\displaystyle{ f(m,n)=f(n,m)=2^{mn-1} {m+n-2 \choose m-1}}\)...

Dodano po 16 minutach 23 sekundach:
Biorąc pod uwagę zapis Gosdy i mój wzór:

\(\displaystyle{ f(n,n)=2^{n^2+1}a_{301560}(n)=2^{n^2-1} {2n-2 \choose n-1} }\)

otrzymamy:

\(\displaystyle{ a_{301560}(n)= \frac{1}{4}{2n-2 \choose n-1} }\)

Wreszcie się wyjaśniło czym jest tajemniczy współczynnik , ale jeszcze nie znam tajemnicy numeru:

301560...