[Kombinatoryka] Fajna Kombinatoryka

[Burii]

Niech \(\displaystyle{ p_{1},}\) \(\displaystyle{ p_{2} ,p _{3}}\) będą różnymi liczbami pierwszymi. Znajdź liczbę funkcji \(\displaystyle{ f:\left\{ 1,2,...2n\right\} \rightarrow \left\{ p _{1}, p _{2}, p _{3} \right\}}\) dla których \(\displaystyle{ f\left( 1\right)f\left( 2\right)...f\left( 2n\right)}\) jest kwadratem liczby naturalnej.

[kp1311]

\(\displaystyle{ 3^n}\), zaraz dopisze dlaczego.
W rozwiązaniu przyda nam się dwumian newtona uogólniony na wielomiany wyższych stopni. (
Oznaczymy \(\displaystyle{ I=f(1)f(2) \cdot ... \cdot f(2n)}\).
\(\displaystyle{ I=p^{2A}_{1}p^{2B}_{2}p^{2C}_{1}}\), \(\displaystyle{ A,B,C}\) są liczbami ze zbioru \(\displaystyle{ 0,1,2,3,4,..,n}\) i \(\displaystyle{ A+B+C=n}\).
Pytamy ile jest takich uporządkowanych trójek \(\displaystyle{ A,B,C}\).
Teraz przydaje się uogólniony dwumian.
\(\displaystyle{ \sum_{A+B+C=n}^{} \frac{n!}{A!B!C!} = (1+1+1)^n = 3^n}\).

[Burii]

Myślę, że ta liczba ma wynosić \(\displaystyle{ \sum_{a _{1}+a _{2}+a _{3}=2n , a _{1}, a_{2}, a _{3} parzyste }^{}{2n \choose a _{1},a _{2},a _{3} }}\) czyli jak dobrze wyliczyłem \(\displaystyle{ \frac{ 3^{2n}+3 }{4}}\), gdzie \(\displaystyle{ a _{i}}\) jest liczbą możliwych argumentów \(\displaystyle{ x}\) takich że \(\displaystyle{ f\left( x\right)=a _{i}}\)
dla \(\displaystyle{ i \in \left\{ 1,2,3\right\}}\).

[kp1311]

Sprawdziłeś swój wzór dla \(\displaystyle{ n=2}\)?
\(\displaystyle{ I= p^{2A}_{1}p^{2B}_{2}p^{2C}_{3}}\)

\(\displaystyle{ 2A+2B+2C=4 \Leftrightarrow A+B+C=2}\)


Widzimy że jedna z tych liczb jest zerem (3 sposoby na wybór takiej liczby).
Pozostałem dwie sumują się do \(\displaystyle{ 2}\) mamy więc pary: \(\displaystyle{ (0,2),(1,1),(2,0)}\).
Więc dla \(\displaystyle{ n=2}\) mamy \(\displaystyle{ 3^2}\) funkcji spełniających warunki zadania.

[Burii]

Moim zdaniem suma ta jest również równa sumie współczynników przy wyrazach w potędze parzystej wyrażenia \(\displaystyle{ \left( x+y+z\right) ^{2n}}\).

[kp1311]

Twierdziłeś że liczba tych funkcji to \(\displaystyle{ \frac{3^{2n}+3}{4}}\) podałem ci kontrprzykład. Dla n=2 dostajesz 21 funkcji zamiast 9.

[Burii]

Aby obliczyć sumę tych współczynników rozważmy wyrażenie;
\(\displaystyle{ h\left( a,b,c\right) = \frac{1}{8} \sum_{p,q,r \in \left\{ 1,-1\right\} } } \left( pa+qb+rc\right) ^{2n}}\). Wielomian \(\displaystyle{ h}\) nie ma wyrazu w nieparzystej potędze, oraz wszystkie jego współczynniki przy wyrazach w potędze parzystej równe są odpowiednim współczynnikom \(\displaystyle{ \left( a+b+b\right) ^{2n}}\) Stąd suma tych współczynników będzie równa \(\displaystyle{ h\left( 1,1,1\right)}\).-- 6 maja 2011, o 21:08 --:Wychodzi łacznie \(\displaystyle{ \frac{ 3^{2n}+3 }{4}}\).

[kp1311]

Twierdziłeś że liczba tych funkcji to \(\displaystyle{ \frac{3^{2n}+3}{4}}\) podałem ci kontrprzykład. Dla n=2 dostajesz 21 funkcji zamiast 9.
Dowód indukcyjny.
\(\displaystyle{ I_{n}=f(1)f(2) \cdot ... \cdot f(2n)}\)
Dla \(\displaystyle{ n=1}\) są trzy takie funkcje.
Jeśli liczby \(\displaystyle{ f(1),f(2),..,f(2n)}\) możemy dobrać na \(\displaystyle{ 3^n}\) tak aby \(\displaystyle{ I_{n}}\) było kwadratem.
To \(\displaystyle{ I_{n+1} = I_{n}f(2n+1)f(2n+2)}\)
Iloczyn \(\displaystyle{ f(2n+1)f(2n+2)}\) musi być kwadratem którejś z liczb \(\displaystyle{ p_{1},p_{2},p_{3}}\)(w innym wypadku \(\displaystyle{ I_{n+1}}\) nie jest kwadratem) więc \(\displaystyle{ f(2n+1), f(2n+2)}\) możemy dobrać na 3 sposoby.
Zatem wszystkie liczby:\(\displaystyle{ f(1),f(2),..,f2(n+2)}\) możemy dobrać na \(\displaystyle{ 3^n \cdot 3=3^{n+1}}\) sposobów.

[Burii]

A widzisz gdzieś błąd w moim rozumowaniu??

-- 6 maja 2011, o 21:25 --

Chyba źle policzyłeś dla n=2. Dla tej wartości jeśliby komuś się chciało liczyć to wychodzi dokładnie 21.

[kp1311]

Ok to pokaż jak ty liczysz ze ci wychodzi 21.

[Burii]

\(\displaystyle{ f\left( 1\right) =f\left( 2\right) =f\left( 3\right) =f\left( 4\right) =p _{i}}\) - 3 funkcje
\(\displaystyle{ f\left( 1\right) =f\left( 2\right) =p _{i}}\) -trzy możliwości a potem \(\displaystyle{ f\left( 3\right) =f\left( 4\right)=p _{j}}\)-dwie możliwości łacznie 6. wyborów dwóch elementów z czterech jest \(\displaystyle{ 6}\) zatem mamy \(\displaystyle{ 6 \cdot 6}\) ale liczymy dwa razy więc \(\displaystyle{ \frac{6 \cdot 6}{2} =18}\)
Razem 21.

[binaj]

niech \(\displaystyle{ f:\left\{ 1,2,...2n\right\} \rightarrow \left\{ p _{1}, p _{2}, p _{3} \right\}}\)
będzie ciągiem 2n wyrazowym \(\displaystyle{ b_n}\), takim, że \(\displaystyle{ b_n}\) to \(\displaystyle{ f(n)}\)
oraz niech \(\displaystyle{ a_n}\) oznacza ilość dobrych ciągów (takich jak pasuje w zadaniu)
zatem złych ciągów jest \(\displaystyle{ 3^{2n}-a_n}\)

będziemy rozumować indukcyjnie:

\(\displaystyle{ a_{n+1}=3a_n+2(3^{2n}-a_n)}\)

(do każdego dobrego ciągu możemy dodać p1p1, p2p2 lub p3p3), a do każdego złego możemy dodać pxpy lub pypx, gdzie px i py to te liczby pierwsze, których była nieparzysta ilość w złym ciągu)

zatem: \(\displaystyle{ a_{n+1}-a_n=2 \cdot 3^{2n}}\)

a stąd już łatwo policzyć \(\displaystyle{ a_{n+1}}\)z sumy teleskopowej i ciągu geom. pamiętając, że \(\displaystyle{ a_1=3}\)

[Burii]

A więc jednak mój wynik jest prawdziwy:D

[kp1311]

Ok, byłem w błędzie.