Jak zliczyć ilość macierzy wymiaru 5x5, której elementy są 0 lub 1 i:
1. element \(\displaystyle{ a _{i,i}}\) jest zawsze = 0
2. każdy wiersz i każda kolumna ma 2 jedynki i 3 zera
3. \(\displaystyle{ a _{i,j} \neq a _{j,i}}\)?
Zliczanie macierzy
-
Kartezjusz
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
Zliczanie macierzy
Ile masz miejsc już znanych, a ile do obsadzenia. Na ile sposobów można obstawić każde z nich?
-
Auster
- Użytkownik
- Posty: 20
- Rejestracja: 6 maja 2015, o 17:46
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 5 razy
Zliczanie macierzy
Średnio pomaga mi ta podpowiedź. Znam całą przekątną bo wynosi 0. Jeśli w pierwszym wierszu postawie 2 zera (równoważnie 2 jedynki) to możliwości takich jest 6 (4 po 2). Automatycznie wypełniam w ten sposób pierwszą kolumnę. Później możliwości mamy 3 (3 po 2).
Nie wiem natomiast jak rozpatrzyć dalszą część. Wszystko zależy czy wypełniamy kolumnę która posiada już jedynkę czy nie...
Nie wiem natomiast jak rozpatrzyć dalszą część. Wszystko zależy czy wypełniamy kolumnę która posiada już jedynkę czy nie...
-
Kartezjusz
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
Zliczanie macierzy
Na ile sposobów obstawisz jedno pole?-- 12 listopada 2015, 17:13 --To są trzy podpunkty czy trzy warunki do spełnienia jednocześnie?
-
arek1357
- Użytkownik
- Posty: 5736
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Zliczanie macierzy
Ja bym ci radził ułożyć układ 10 równań z 20 niewiadomymi trochę liczenia ale do przejścia,
Wyliczyć co się da a potem zaostrzyć na trzeci warunek.
Każda niewiadoma przyjmuje wartość jeden lub zero!
\(\displaystyle{ 0+x_{1,2}+...+x_{1,5}=2}\)
\(\displaystyle{ x_{2,1}+0+...+x_{2,5}=2}\)
....................................
\(\displaystyle{ x_{5,1}+x_{5,2}+...+0=2}\)
A potem kolumny:
...............................................................
Po redukcji otrzymasz:
\(\displaystyle{ \left( x_{1,2}+x_{2,1}\right) +\left( x_{1,3}+x_{3,1}\right) +...+\left( x_{3,4}+x_{4,3}\right)+x_{5,1}+x_{5,2}+x_{5,3}=8}\)
Sumy w nawiasach wynoszą jeden z warunków zadania
Nawiasów masz sześć plus ostanie trzy składniki dowolne
Zredukuje się równanie do:
\(\displaystyle{ x_{5,1}+x_{5,2}+x_{5,3}=2}\)
Jak widać masz trzy przypadki, któreś z nich musi być zero!
I tak dalej redukuj sobie i sprawdzaj!
Zresztą masz jeszcze:
\(\displaystyle{ x_{i,j}+x_{j,i}=1}\)
Sprowadziło mi się to do dwóch niezależnych równań:
\(\displaystyle{ x_{1,2}+x_{1,3}+\left( x_{1,4}+x_{1,5}\right)=2}\)
\(\displaystyle{ x_{2,4}+x_{3,4}+ x_{2,5}+x_{3,5}+\left( x_{1,4}+x_{1,5}\right)=2}\)
I wszystko sprowadza się do policzenia ilości tych równań co nie jest trudne.
Suma w nawiasie może być równa:
\(\displaystyle{ 0,1,2}\)
Co daje 20 możliwości!
Wyliczyć co się da a potem zaostrzyć na trzeci warunek.
Każda niewiadoma przyjmuje wartość jeden lub zero!
\(\displaystyle{ 0+x_{1,2}+...+x_{1,5}=2}\)
\(\displaystyle{ x_{2,1}+0+...+x_{2,5}=2}\)
....................................
\(\displaystyle{ x_{5,1}+x_{5,2}+...+0=2}\)
A potem kolumny:
...............................................................
Po redukcji otrzymasz:
\(\displaystyle{ \left( x_{1,2}+x_{2,1}\right) +\left( x_{1,3}+x_{3,1}\right) +...+\left( x_{3,4}+x_{4,3}\right)+x_{5,1}+x_{5,2}+x_{5,3}=8}\)
Sumy w nawiasach wynoszą jeden z warunków zadania
Nawiasów masz sześć plus ostanie trzy składniki dowolne
Zredukuje się równanie do:
\(\displaystyle{ x_{5,1}+x_{5,2}+x_{5,3}=2}\)
Jak widać masz trzy przypadki, któreś z nich musi być zero!
I tak dalej redukuj sobie i sprawdzaj!
Zresztą masz jeszcze:
\(\displaystyle{ x_{i,j}+x_{j,i}=1}\)
Sprowadziło mi się to do dwóch niezależnych równań:
\(\displaystyle{ x_{1,2}+x_{1,3}+\left( x_{1,4}+x_{1,5}\right)=2}\)
\(\displaystyle{ x_{2,4}+x_{3,4}+ x_{2,5}+x_{3,5}+\left( x_{1,4}+x_{1,5}\right)=2}\)
I wszystko sprowadza się do policzenia ilości tych równań co nie jest trudne.
Suma w nawiasie może być równa:
\(\displaystyle{ 0,1,2}\)
Co daje 20 możliwości!
-
norwimaj
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Zliczanie macierzy
Byłby to skandal, gdyby wynik nie dzielił się przez \(\displaystyle{ 6.}\) Wynik jest równy sześć razy liczba możliwych uzupełnień macierzy:
\(\displaystyle{ \begin{pmatrix}
0 & 0 & 0 & 1 & 1 \\
1 & 0 & ? & ? & ? \\
1 & ? & 0 & ? & ? \\
0 & ? & ? & 0 & ? \\
0 & ? & ? & ? & 0
\end{pmatrix}.}\)
Ostatecznie wychodzi na to, że wszystkie rozwiązania są takie same z dokładnością do jednoczesnej permutacji wierszy i kolumn.
\(\displaystyle{ \begin{pmatrix}
0 & 0 & 0 & 1 & 1 \\
1 & 0 & ? & ? & ? \\
1 & ? & 0 & ? & ? \\
0 & ? & ? & 0 & ? \\
0 & ? & ? & ? & 0
\end{pmatrix}.}\)
Ostatecznie wychodzi na to, że wszystkie rozwiązania są takie same z dokładnością do jednoczesnej permutacji wierszy i kolumn.
-
arek1357
- Użytkownik
- Posty: 5736
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Zliczanie macierzy
Podsumowanie:
\(\displaystyle{ a+b=x_{1,2}+x_{1,4}=2-x_{1,3}-x_{1,5}}\)
\(\displaystyle{ A+B=x_{2,5}+x_{4,5}=2-x_{3,5}-x_{1,5}}\)
\(\displaystyle{ x-y= x_{3,4}+x_{2,3}=2-x_{1,3}-x_{3,5}}\)
oraz:
\(\displaystyle{ 1+x_{4,5}-x_{1,4}-x_{3,4}=x_{2,4}=0 \vee 1}\)
co generalnie daje nam dwa równania:
\(\displaystyle{ x_{1,4}+x_{3,4}=x_{4,5}}\)
lub:
\(\displaystyle{ x_{1,4}+x_{3,4}=1+x_{4,5}}\)
w wersji uproszczonej:
\(\displaystyle{ b+x=B}\)
lub:
\(\displaystyle{ b+x=1+B}\)
Biorąc do kupy:
\(\displaystyle{ a+b=2-x_{1,3}-x_{1,5}}\)
\(\displaystyle{ A+B=2-x_{3,5}-x_{1,5}}\)
\(\displaystyle{ x-y=2-x_{1,3}-x_{3,5}}\)
oraz:
(*) \(\displaystyle{ b+x=B \vee b+x=1+B}\)
Teraz nic nie zostaje jak liczyć przypadki:
\(\displaystyle{ I. (x_{1,3},x_{1,5},x_{3,5})=(0,0,0)}\)
wtedy:
\(\displaystyle{ a+b=2}\)
\(\displaystyle{ A+B=2}\)
\(\displaystyle{ x-y=0}\) -, oraz (*) mamy dwa rozwiązania
\(\displaystyle{ II. (x_{1,3},x_{1,5},x_{3,5})=(0,1,0)}\)
wtedy:
\(\displaystyle{ a+b=1}\)
\(\displaystyle{ A+B=1}\)
\(\displaystyle{ x-y=0}\) -, oraz (*) mamy 6 rozwiązań łatwo sprawdzić
\(\displaystyle{ III. (x_{1,3},x_{1,5},x_{3,5})=(0,0,1)}\)
wtedy:
\(\displaystyle{ a+b=2}\)
\(\displaystyle{ A+B=1}\)
\(\displaystyle{ x-y=1}\) -, oraz (*) mamy 2 rozwiązania
\(\displaystyle{ IV. (x_{1,3},x_{1,5},x_{3,5})=(0,1,1)}\)
wtedy:
\(\displaystyle{ a+b=1}\)
\(\displaystyle{ A+B=0}\)
\(\displaystyle{ x-y=-1}\) -, oraz (*) mamy 2 rozwiązania
\(\displaystyle{ V. (x_{1,3},x_{1,5},x_{3,5})=(1,0,1)}\)
wtedy:
\(\displaystyle{ a+b=1}\)
\(\displaystyle{ A+B=1}\)
\(\displaystyle{ x-y=1}\) -, oraz (*) mamy 6 rozwiązań
\(\displaystyle{ VI. (x_{1,3},x_{1,5},x_{3,5})=(1,1,0)}\)
wtedy:
\(\displaystyle{ a+b=0}\)
\(\displaystyle{ A+B=1}\)
\(\displaystyle{ x-y=1}\) -, oraz (*) mamy 2 rozwiązania
\(\displaystyle{ VII. (x_{1,3},x_{1,5},x_{3,5})=(1,0,0)}\)
wtedy:
\(\displaystyle{ a+b=1}\)
\(\displaystyle{ A+B=2}\)
\(\displaystyle{ x-y=1}\) -, oraz (*) mamy 2 rozwiązania
\(\displaystyle{ VIII. (x_{1,3},x_{1,5},x_{3,5})=(1,1,1)}\)
wtedy:
\(\displaystyle{ a+b=0}\)
\(\displaystyle{ A+B=0}\)
\(\displaystyle{ x-y=0}\) -, oraz (*) mamy 2 rozwiązania
Razem daje:
\(\displaystyle{ 2+6+2+2+6+2+2+2=24}\) - rozwiązania
Już nie będzie skandalu!
\(\displaystyle{ a+b=x_{1,2}+x_{1,4}=2-x_{1,3}-x_{1,5}}\)
\(\displaystyle{ A+B=x_{2,5}+x_{4,5}=2-x_{3,5}-x_{1,5}}\)
\(\displaystyle{ x-y= x_{3,4}+x_{2,3}=2-x_{1,3}-x_{3,5}}\)
oraz:
\(\displaystyle{ 1+x_{4,5}-x_{1,4}-x_{3,4}=x_{2,4}=0 \vee 1}\)
co generalnie daje nam dwa równania:
\(\displaystyle{ x_{1,4}+x_{3,4}=x_{4,5}}\)
lub:
\(\displaystyle{ x_{1,4}+x_{3,4}=1+x_{4,5}}\)
w wersji uproszczonej:
\(\displaystyle{ b+x=B}\)
lub:
\(\displaystyle{ b+x=1+B}\)
Biorąc do kupy:
\(\displaystyle{ a+b=2-x_{1,3}-x_{1,5}}\)
\(\displaystyle{ A+B=2-x_{3,5}-x_{1,5}}\)
\(\displaystyle{ x-y=2-x_{1,3}-x_{3,5}}\)
oraz:
(*) \(\displaystyle{ b+x=B \vee b+x=1+B}\)
Teraz nic nie zostaje jak liczyć przypadki:
\(\displaystyle{ I. (x_{1,3},x_{1,5},x_{3,5})=(0,0,0)}\)
wtedy:
\(\displaystyle{ a+b=2}\)
\(\displaystyle{ A+B=2}\)
\(\displaystyle{ x-y=0}\) -, oraz (*) mamy dwa rozwiązania
\(\displaystyle{ II. (x_{1,3},x_{1,5},x_{3,5})=(0,1,0)}\)
wtedy:
\(\displaystyle{ a+b=1}\)
\(\displaystyle{ A+B=1}\)
\(\displaystyle{ x-y=0}\) -, oraz (*) mamy 6 rozwiązań łatwo sprawdzić
\(\displaystyle{ III. (x_{1,3},x_{1,5},x_{3,5})=(0,0,1)}\)
wtedy:
\(\displaystyle{ a+b=2}\)
\(\displaystyle{ A+B=1}\)
\(\displaystyle{ x-y=1}\) -, oraz (*) mamy 2 rozwiązania
\(\displaystyle{ IV. (x_{1,3},x_{1,5},x_{3,5})=(0,1,1)}\)
wtedy:
\(\displaystyle{ a+b=1}\)
\(\displaystyle{ A+B=0}\)
\(\displaystyle{ x-y=-1}\) -, oraz (*) mamy 2 rozwiązania
\(\displaystyle{ V. (x_{1,3},x_{1,5},x_{3,5})=(1,0,1)}\)
wtedy:
\(\displaystyle{ a+b=1}\)
\(\displaystyle{ A+B=1}\)
\(\displaystyle{ x-y=1}\) -, oraz (*) mamy 6 rozwiązań
\(\displaystyle{ VI. (x_{1,3},x_{1,5},x_{3,5})=(1,1,0)}\)
wtedy:
\(\displaystyle{ a+b=0}\)
\(\displaystyle{ A+B=1}\)
\(\displaystyle{ x-y=1}\) -, oraz (*) mamy 2 rozwiązania
\(\displaystyle{ VII. (x_{1,3},x_{1,5},x_{3,5})=(1,0,0)}\)
wtedy:
\(\displaystyle{ a+b=1}\)
\(\displaystyle{ A+B=2}\)
\(\displaystyle{ x-y=1}\) -, oraz (*) mamy 2 rozwiązania
\(\displaystyle{ VIII. (x_{1,3},x_{1,5},x_{3,5})=(1,1,1)}\)
wtedy:
\(\displaystyle{ a+b=0}\)
\(\displaystyle{ A+B=0}\)
\(\displaystyle{ x-y=0}\) -, oraz (*) mamy 2 rozwiązania
Razem daje:
\(\displaystyle{ 2+6+2+2+6+2+2+2=24}\) - rozwiązania
Już nie będzie skandalu!