Macierz i wielomiany szachowe

[niewiemcosiedzieje]

Dzień dobry,

Mam problem z tymi dwoma zadaniami. Nie mam pojęcia jak zacząć. Byłbym wdzięczny, gdyby ktoś mógł udzielić mi jakichś wskazówek, przykładów, aby te zadania wykonać.
Z góry dziękuję

Zadanie 1:
Wyznaczyć liczbę macierzy o wymiarach n × n i wyrazach 0, 1 lub -1, w których przynajmniej jeden wiersz składa się z samych zer.

Zadanie 2:
Obliczyć wielomian szachowy tablicy (pola z x są zabronione, a pola z o dostępne):
o x x x x x o
x o x x x o x
x x x o x x x
x x x o x x x
x o x x x o x
x x o o o x x
o x x x x x o
Link do rysunku (przepraszam, ale nie wiem dlaczego nie mogę go wstawić między img]:

Kod: Zaznacz cały

https://i.imgur.com/wdf3Btz.png

[matmatmm]

Zadanie 1.

Pomysł 1: Obliczamy na ile sposobów można wypełnić macierz tak, żeby

Pierwszy wiersz składał się z samych zer: \(\displaystyle{ 3^{n(n-1)}}\)
Pierwsze dwa wiersze składały się z samych zer: \(\displaystyle{ 3^{n(n-2)}}\)
\(\displaystyle{ \vdots}\)
Ogólnie pierwsze \(\displaystyle{ k}\) wiersze składają się z samych zer: \(\displaystyle{ 3^{n(n-k)}}\)

wynik końcowy:    

\(\displaystyle{ n3^{n(n-1)}-{n \choose 2}3^{n(n-2)}+\ldots+ (-1)^{k+1}{n \choose k} 3^{n(n-k)}+\ldots +(-1)^{n+1}}\)

Pomysł 2: Obliczamy na ile sposobów można wypełnić jeden wiersz tak, aby nie składał się z samych zer: \(\displaystyle{ 3^n-1}\).

wynik końcowy:    

\(\displaystyle{ 3^{n^2}-(3^n-1)^n}\)

[niewiemcosiedzieje]

Pozwolę sobie zapytać, bo nie wiem czy dobrze zrozumiałem. W pomyślę drugim:
"Obliczamy na ile sposobów można wypełnić jeden wiersz tak, aby nie składał się z samych zer: \(\displaystyle{ 3^{n} - 1 }\) "
Rozumiem, to tak: \(\displaystyle{ 3^{n}}\) to są wszystkie możliwości rozstawienia liczb -1, 0, 1 dla jednego wiersza, a \(\displaystyle{ -1}\) to jest ta jedyna opcja, gdzie występują same zera.
Następnie w wyniku końcowym mamy:
\(\displaystyle{ 3^{n^{2}}}\) domyślam się, że są to wszystkie możliwości rozstawienia tych liczb dla całej macierzy n x n, a \(\displaystyle{ (3^{n} - 1)^{n}}\) są to te możliwości, gdzie występują wiersze z samymi zerami. Jeśli się nie mylę, a moje rozumowanie jest słuszne, to czy mógłbyś mi wytłumaczyć, dlaczego \(\displaystyle{ 3^{n^{2}}}\) podnosimy tutaj do potęgi 2 znowu, a nie mnożymy to wyrażenie razy n (ilośc wierszy w macierzy)? To samo pytanie tyczy się \(\displaystyle{ (3^{n} - 1)^{n}}\), dlaczego do potęgi n?

Dodano po 39 minutach 15 sekundach:
Okej. Chyba juz zrozumiałem. Dla pewności przedstawię jak sobie to "rozjaśniłem"
Załóżmy, że mamy macierz 2 x 2. Wziąłem sobie -1, 0, 1 i zacząłem tworzyć pary.
Dostałem: {1, 1} , {1, 0) , {1, -1} , {0, 1} , {0, 0} , {0, -1} , {-1, 1} , {-1, 0}, {-1, -1}. Jeśli się nie pomyliłem, to wychodzi nam \(\displaystyle{ 3^{2} }\) możliwości. Od tego odejmujemy 1, bo mamy jedną możliwość z samymi zerami. Teraz potraktujmy te "pary" jako pojedyncze elementy (możliwe wiersze), z której możemy stworzyć naszą macierz. Tych elementów jest 9, jak wyszło nam ze wzoru, a zauważmy, że jest to właśnie \(\displaystyle{ 3^{2^{2}}}\). Teraz \(\displaystyle{ (3^{n} - 1)^{n}}\). Jak wiemy nawias ten mówi nam o wszystkich możliwościach, gdzie ów wiersz z zerami się nie pokazuje. Cały nawias podnosimy do potęgi n, bo te własnie wiersze możemy rozstawić na n możliwości (każdy wiersz można postawić na n miejscach, bo macierz jest n x n). Odejmujemy jedno od drugiego i wychodzi nam wynik, który mówi nam ile jest takich macierzy, gdzie wiersz z samymi zerami występuję.
Mam nadzieję, że teraz dobrze

[matmatmm]

Pozwolę sobie zapytać, bo nie wiem czy dobrze zrozumiałem. W pomyślę drugim:
"Obliczamy na ile sposobów można wypełnić jeden wiersz tak, aby nie składał się z samych zer: \(\displaystyle{ 3^{n} - 1 }\) "
Rozumiem, to tak: \(\displaystyle{ 3^{n}}\) to są wszystkie możliwości rozstawienia liczb -1, 0, 1 dla jednego wiersza, a \(\displaystyle{ -1}\) to jest ta jedyna opcja, gdzie występują same zera.
Następnie w wyniku końcowym mamy:
\(\displaystyle{ 3^{n^{2}}}\) domyślam się, że są to wszystkie możliwości rozstawienia tych liczb dla całej macierzy n x n, a \(\displaystyle{ (3^{n} - 1)^{n}}\) są to te możliwości, gdzie występują wiersze z samymi zerami.

Dokładnie tak.

Jeśli się nie mylę, a moje rozumowanie jest słuszne, to czy mógłbyś mi wytłumaczyć, dlaczego \(\displaystyle{ 3^{n^{2}}}\) podnosimy tutaj do potęgi 2 znowu, a nie mnożymy to wyrażenie razy n (ilośc wierszy w macierzy)?

Nie rozumiem. Co tutaj podnosimy do potęgi \(\displaystyle{ 2}\)?

To samo pytanie tyczy się \(\displaystyle{ (3^{n} - 1)^{n}}\), dlaczego do potęgi n?

To wynika z reguły mnożenia: Pierwszy wiersz nie składa się z samych zer, drugi wiersz nie składa się z samych zer, trzeci itd. W sumie mnożymy \(\displaystyle{ n}\) razy.

[a4karo]

Policzmy ile jest macierzy, które maja dokładnie `k` (`k=1,2,...,n`) wierszy zerowych: `k` wierszy możemy wybrać na \(\displaystyle{ \binom{n}{k}}\) sposobów. Pozostałe wiersze możemy wypełnić niezerowymi wierszami dowolnie - to można zrobić na `(3^n-1)^{n-k}` sposobów. Macierzy takich jest więc
\(\displaystyle{ \binom{n}{k}(3^n-1)^{n-k}}\).
Wszystkich macierzy, które maja co najmniej jeden wiersz zerowy jest zatem
\(\displaystyle{ \sum_{k=1}^n \binom{n}{k}(3^n-1)^{n-k}=\sum_{k=0}^n \binom{n}{k}(3^n-1)^{n-k}-\binom{n}{0}(3^n-1)^{n}=3^{n^2}-3^n+1 }\)

[matmatmm]

\(\displaystyle{ \ldots=\sum_{k=0}^n \binom{n}{k}(3^n-1)^{n-k}-\binom{n}{0}(3^n-1)^{n} =3^{n^2}-3^n+1 }\)

Chyba coś tutaj nie pykło.

[a4karo]

Czemu?

Dodano po 5 minutach 31 sekundach:
Faktycznie.
Powinno być
\(\displaystyle{ 3^{n^2}-(3^n-1)^n}\)