zasada właczeń i wyłączeń

[rivit]

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

[arek1357]

\(\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ń...

[rivit]

Też się zastanawiam po co, ale jest w temacie o tej zasadzie i trzeba ją zrobić właśnie dzięki tej zasadzie (mimo że inaczej może być prościej)

[arek1357]

Też nie wiem poco

[rivit]

A masz moze pomysł jak zrobić to przez tą zasadę właśnie? Takiego rozwiązania będą ode mnie wymagać raczej na zajęciach

[arek1357]

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ę...

[rivit]

A ktoś może wie jak to z wykorzystaniem tej zasady zrobic?

[arek1357]

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...

[kerajs]

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)

[rivit]

Bardzo dziękuję!