zasada właczeń i wyłączeń
-
- Użytkownik
- Posty: 163
- Rejestracja: 28 paź 2018, o 17:31
- Płeć: Mężczyzna
- Podziękował: 70 razy
- Pomógł: 2 razy
zasada właczeń i wyłączeń
Witam, jak podejść do tego zadanka metodą włączeń i wyłączeń? Mógłbym ktoś wyjaśnic?
Ile jest różnych zestawów składających się z siedmiu owoców, jeżeli mamy do dyspozycji 10 bananów, 8 jabłek i 6 pomarańczy, a każdy zestaw musi zawierać przynajmniej dwa banany i nie może zawierać więcej niż trzy jabłka?
Prosze o wytłumaczenie, pozdrawiam
Ile jest różnych zestawów składających się z siedmiu owoców, jeżeli mamy do dyspozycji 10 bananów, 8 jabłek i 6 pomarańczy, a każdy zestaw musi zawierać przynajmniej dwa banany i nie może zawierać więcej niż trzy jabłka?
Prosze o wytłumaczenie, pozdrawiam
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: zasada właczeń i wyłączeń
\(\displaystyle{ x+y+z=7 , x \ge 2, y \le 3}\)
\(\displaystyle{ x}\)- banany
\(\displaystyle{ y}\) - jabłka
\(\displaystyle{ z}\)- pomarańcze
Wielomian charakterystyczny:
\(\displaystyle{ (x^2+x^3+x^4+...+x^{10})(1+x+x^2+x^3)(1+x+x^2+...+x^6)=}\)
\(\displaystyle{ x^{19} + 3 x^{18} + 6 x^{17} + 10 x^{16} + 14 x^{15} + 18 x^{14} + 22 x^{13} + 25 x^{12} + 27 x^{11} + 27 x^{10} + 25 x^9 + 22 x^8 + 18 x^7 + 14 x^6 + 10 x^5 + 6 x^4 + 3 x^3 + x^2}\)
Współczynnik przy \(\displaystyle{ x^7=18}\) rozwiązuje zadanie..
Zakładam, że jabłek i i pomarańczy może być zero...
Ale poco ci tu zasada włączeń i wyłączeń...
Tylko poco ci zasada włączeń i wyłączeń...
\(\displaystyle{ x}\)- banany
\(\displaystyle{ y}\) - jabłka
\(\displaystyle{ z}\)- pomarańcze
Wielomian charakterystyczny:
\(\displaystyle{ (x^2+x^3+x^4+...+x^{10})(1+x+x^2+x^3)(1+x+x^2+...+x^6)=}\)
\(\displaystyle{ x^{19} + 3 x^{18} + 6 x^{17} + 10 x^{16} + 14 x^{15} + 18 x^{14} + 22 x^{13} + 25 x^{12} + 27 x^{11} + 27 x^{10} + 25 x^9 + 22 x^8 + 18 x^7 + 14 x^6 + 10 x^5 + 6 x^4 + 3 x^3 + x^2}\)
Współczynnik przy \(\displaystyle{ x^7=18}\) rozwiązuje zadanie..
Zakładam, że jabłek i i pomarańczy może być zero...
Ale poco ci tu zasada włączeń i wyłączeń...
Tylko poco ci zasada włączeń i wyłączeń...
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: zasada właczeń i wyłączeń
Dla mnie tu są kombinacje z ograniczeniami szczerze nie mam pojęcia o stosowaniu tu zasady włączeń...
Może i jest jakiś sztuczny sposób nie przeczę...
Może i jest jakiś sztuczny sposób nie przeczę...
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: zasada właczeń i wyłączeń
Powinno być tak:
Najpierw wybierasz z ciągu elementów te w których występują tylko i wyłącznie elementy:
\(\displaystyle{ \left\{ 1,3,6\right\}}\)
Robisz to na:
\(\displaystyle{ {n \choose k}}\)
Elementy ze zbioru:\(\displaystyle{ \left\{ \left\{ 1,3,6\right\} \right\}}\) występują wyłącznie na \(\displaystyle{ k}\) miejscach,
a resztą obsadzasz elementami:
\(\displaystyle{ \left\{ 0,2,4,5,7,8,9,\right\}}\) na sposobów: \(\displaystyle{ 7^{n-k}}\)
Teraz musisz zadbać, żeby wystąpiły wszystkie elementy:
\(\displaystyle{ \left\{ 1,3,6\right\}}\)
Ale one mogą takie trójki występować w liczbie:
\(\displaystyle{ \left[ \frac{k}{3} \right]}\) maksymalnie...
I na sposobów:
\(\displaystyle{ {k \choose 3s}}\) wybierasz miejsca w których będą trójki, pozostałe miejsca obdzielasz byle jak elementami ze zbioru: \(\displaystyle{ \left\{ 1,3,6\right\}}\) na sposobów:
\(\displaystyle{ 3^{k-3s}}\), oczywiście trójki które wystąpią mogą permutować, więc to wszystko mnożysz przez.: \(\displaystyle{ 3!}\) jeszcze...
No i teraz stosujesz swoją ulubioną zasadę włączania i wyłączania, bo musisz odrzucać, żeby się nie powtarzały...
Reasumując to do kupy otrzymasz coś takiego:
\(\displaystyle{ a_{n}= \sum_{k=3}^{n} {n \choose k}\left[ \sum_{s=1}^{\left[ \frac{k}{3} \right] } {k \choose 3s}3! \cdot 3^{k-3s}(-1)^{s+1} \right] \cdot 7^{n-k}}\)
Może coś przeoczyłem po noc późna a ja upojony świętem i nie tylko...
Najpierw wybierasz z ciągu elementów te w których występują tylko i wyłącznie elementy:
\(\displaystyle{ \left\{ 1,3,6\right\}}\)
Robisz to na:
\(\displaystyle{ {n \choose k}}\)
Elementy ze zbioru:\(\displaystyle{ \left\{ \left\{ 1,3,6\right\} \right\}}\) występują wyłącznie na \(\displaystyle{ k}\) miejscach,
a resztą obsadzasz elementami:
\(\displaystyle{ \left\{ 0,2,4,5,7,8,9,\right\}}\) na sposobów: \(\displaystyle{ 7^{n-k}}\)
Teraz musisz zadbać, żeby wystąpiły wszystkie elementy:
\(\displaystyle{ \left\{ 1,3,6\right\}}\)
Ale one mogą takie trójki występować w liczbie:
\(\displaystyle{ \left[ \frac{k}{3} \right]}\) maksymalnie...
I na sposobów:
\(\displaystyle{ {k \choose 3s}}\) wybierasz miejsca w których będą trójki, pozostałe miejsca obdzielasz byle jak elementami ze zbioru: \(\displaystyle{ \left\{ 1,3,6\right\}}\) na sposobów:
\(\displaystyle{ 3^{k-3s}}\), oczywiście trójki które wystąpią mogą permutować, więc to wszystko mnożysz przez.: \(\displaystyle{ 3!}\) jeszcze...
No i teraz stosujesz swoją ulubioną zasadę włączania i wyłączania, bo musisz odrzucać, żeby się nie powtarzały...
Reasumując to do kupy otrzymasz coś takiego:
\(\displaystyle{ a_{n}= \sum_{k=3}^{n} {n \choose k}\left[ \sum_{s=1}^{\left[ \frac{k}{3} \right] } {k \choose 3s}3! \cdot 3^{k-3s}(-1)^{s+1} \right] \cdot 7^{n-k}}\)
Może coś przeoczyłem po noc późna a ja upojony świętem i nie tylko...
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: zasada właczeń i wyłączeń
Inne podejście:
Równoważnie:
Ile jest różnych zestawów składających się z pięciu owoców, jeżeli mamy do dyspozycji banany, jabłka i pomarańcze, a zestaw nie może zawierać więcej niż trzy jabłka?
\(\displaystyle{ {5+3-1 \choose 3-1}- {5-5+2-1 \choose 2-1} -{5-4+2-1 \choose 2-1}=21-1-2=18}\)
Od wszystkich zestawów odejmuję te z 5 jabłkami i te z 4 jabłkami.
Zasada włączeń i wyłączeń dla pierwotnej treści zadania.
(Wszystkie trójowocowe zestawy)-(zestawy z 7 pomarańczami)-(zestawy z 0 lub 1 bananem)-(zestawy z 4 lub 5 lub 6 lub 7 jabłkami)+(zestawy z 7 pomarańczami i z 0 lub 1 bananem)+(zestawy z 7 pomarańczami i z 4 lub 5 lub 6 lub 7 jabłkami)+(zestawy z 0 lub 1 bananem i z 4 lub 5 lub 6 lub 7 jabłkami)-(zestawy z 7 pomarańczami i z 0 lub 1 bananem i z 4 lub 5 lub 6 lub 7 jabłkami)
Równoważnie:
Ile jest różnych zestawów składających się z pięciu owoców, jeżeli mamy do dyspozycji banany, jabłka i pomarańcze, a zestaw nie może zawierać więcej niż trzy jabłka?
\(\displaystyle{ {5+3-1 \choose 3-1}- {5-5+2-1 \choose 2-1} -{5-4+2-1 \choose 2-1}=21-1-2=18}\)
Od wszystkich zestawów odejmuję te z 5 jabłkami i te z 4 jabłkami.
Zasada włączeń i wyłączeń dla pierwotnej treści zadania.
(Wszystkie trójowocowe zestawy)-(zestawy z 7 pomarańczami)-(zestawy z 0 lub 1 bananem)-(zestawy z 4 lub 5 lub 6 lub 7 jabłkami)+(zestawy z 7 pomarańczami i z 0 lub 1 bananem)+(zestawy z 7 pomarańczami i z 4 lub 5 lub 6 lub 7 jabłkami)+(zestawy z 0 lub 1 bananem i z 4 lub 5 lub 6 lub 7 jabłkami)-(zestawy z 7 pomarańczami i z 0 lub 1 bananem i z 4 lub 5 lub 6 lub 7 jabłkami)
Ostatnio zmieniony 12 lis 2018, o 12:30 przez kerajs, łącznie zmieniany 1 raz.