Podać kombinatoryczną interpretację

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
darek20
Użytkownik
Użytkownik
Posty: 874
Rejestracja: 4 paź 2010, o 08:16
Płeć: Mężczyzna
Lokalizacja: wszedzie
Podziękował: 248 razy
Pomógł: 10 razy

Podać kombinatoryczną interpretację

Post autor: darek20 »

Podać kombinatoryczną interpretację

\(\displaystyle{ \sum_{k=0}^{n}{{3n}\choose{3k}}=\frac{1}{3}(8^{n}+2(-1)^{n})}\)
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Podać kombinatoryczną interpretację

Post autor: xiikzodz »

Podam, co mi właśnie do głowy przyszło, choć pewnie o coś innego chodzi.

Spacerujemy po trójkącie. Są dwa możliwe posunięcia. Albo stoimy w miejscu albo robimy krok wzdłuż krawędzi zgodnie z ruchem wskazókwek zegara. W tym zadaniu chodzi o liczbę wszystkich dróg długości \(\displaystyle{ 3n}\) kończących się w punkcie wyjścia.

Wygodnie jest rozważyć macierz incydencji (chyba tak się nazywa) grafu skierowanego będącego trójkątem zorientowanym zgodnie z ruchem wskazówek zegara z dolepionymi pętelkami w każdym wierzchołku, czyli macierz

\(\displaystyle{ \begin{pmatrix}1&1&0\\0&1&1\\1&0&1\end{pmatrix}}\).

Interesuje nas liczba na przekątnej \(\displaystyle{ 3n}\)-tej potęgi tej macierzy, czyli \(\displaystyle{ 1/3}\) śladu tej macierzy ze względu na symetrię.

Zauważamy, że macierz jest diagonalizowalna do postaci

\(\displaystyle{ D=\begin{pmatrix}2&0&0\\0&1+\varepsilon&0\\0&0&1+\overline\varepsilon\end{pmatrix}}\)

gdzie \(\displaystyle{ \varepsilon=\frac{-1+i\sqrt 3}2}\).

Mamy

\(\displaystyle{ D^{n}=\begin{pmatrix}2^{n}&0&0\\0&(1+\varepsilon)^{n}&0\\0&0&(1+\overline\varepsilon)^{n}\end{pmatrix}}\)

czyli

\(\displaystyle{ \mbox{tr}(D^{n})=\frac 13\left(2^n+(1+\varepsilon)^n+(1+\overline\varepsilon)^n\right)=
\frac 13\left(2^n+(-\overline\varepsilon)^n+(-\varepsilon)^n\right)=
\frac 13\left(2^n+(-1)^n\cdot 2\cos\frac{n\pi}3\right)}\)
.

Jeśli do wzoru zamiast \(\displaystyle{ n}\) wstawimy \(\displaystyle{ 3n}\), otrzymamy to co należy.
darek20
Użytkownik
Użytkownik
Posty: 874
Rejestracja: 4 paź 2010, o 08:16
Płeć: Mężczyzna
Lokalizacja: wszedzie
Podziękował: 248 razy
Pomógł: 10 razy

Podać kombinatoryczną interpretację

Post autor: darek20 »

ok dzieki
ODPOWIEDZ