Ile jest różnych ciągów długości \(\displaystyle{ n}\) złożonych z cyfr \(\displaystyle{ \{0, 1, ..., 9\}}\), w których każda z cyfr \(\displaystyle{ 1, 3, 6}\) występuje co najmniej raz?
Skorzystać z zasady włączeń i wyłączeń?
Jak to ugryźć?
zasada właczeń i wyłączeń - ciągi liczbowe
-
rivit
- 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ń - ciągi liczbowe
Ostatnio zmieniony 11 lis 2018, o 22:29 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm . Poprawa wiadomości: co najmniej.
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm . Poprawa wiadomości: co najmniej.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: zasada właczeń i wyłączeń - ciągi liczbowe
Ciągów, w których występuje co najmniej jedna jedynka, trójka lub szóstka masz po prostu \(\displaystyle{ 10^n-7^n}\) – od liczby wszystkich ciągów o \(\displaystyle{ n}\) wyrazach utworzonych z cyfr \(\displaystyle{ \left\{ 0,1\ldots 9\right\}}\) odjąłem liczbę tych, które nie mają ani jedynki, ani trójki, ani szóstki.
Teraz odejmujesz od tego takie, które coś mają, ale nie mają trójki itd. – jest ich \(\displaystyle{ 9^n-7^n}\) (analogicznie dla jedynki i szóstki), a potem zauważ, że jeśli jakiś ciąg zarówno nie ma trójki, jak i nie ma szóstki (przykładowo), to został odjęty dwa razy: takich jest \(\displaystyle{ 8^n-7^n}\) (i podobnie dla pozostałych), stąd odpowiedź to
\(\displaystyle{ 10^n-7^n-3\cdot \left( 9^n-7^n\right) +3\cdot (8^n-7^n)=\\=10^n-3\cdot 9^n+3\cdot 8^n-7^n}\)
Takie podejście jest nieco mozolne, ale pozwala uniknąć wielokrotnego zliczania pewnych układów, co jest zmorą w elementarnej kombinatoryce.
Teraz odejmujesz od tego takie, które coś mają, ale nie mają trójki itd. – jest ich \(\displaystyle{ 9^n-7^n}\) (analogicznie dla jedynki i szóstki), a potem zauważ, że jeśli jakiś ciąg zarówno nie ma trójki, jak i nie ma szóstki (przykładowo), to został odjęty dwa razy: takich jest \(\displaystyle{ 8^n-7^n}\) (i podobnie dla pozostałych), stąd odpowiedź to
\(\displaystyle{ 10^n-7^n-3\cdot \left( 9^n-7^n\right) +3\cdot (8^n-7^n)=\\=10^n-3\cdot 9^n+3\cdot 8^n-7^n}\)
Takie podejście jest nieco mozolne, ale pozwala uniknąć wielokrotnego zliczania pewnych układów, co jest zmorą w elementarnej kombinatoryce.
-
arek1357
- Użytkownik
- Posty: 5744
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Re: zasada właczeń i wyłączeń - ciągi liczbowe
Mam inne podejście;
może 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\}}\)
\(\displaystyle{ 3^k-32^{k}+3}\)
zastosowana tu zasada włączania i wyłączania w formie szczątkowej...
Reasumując to do kupy otrzymasz coś takiego:
\(\displaystyle{ a_{n}= \sum_{k=3}^{n} {n \choose k}\left[ 3^k-3 \cdot 2^k+3 \right] \cdot 7^{n-k}}\)
No niestety spierniczyłem wychodziło podwójnie nałożyłem wariacje i kombinacje, niestety po takim święcie nie myśli się normalnie...
Dużo lepsze i krótsze Premislava...
może 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\}}\)
\(\displaystyle{ 3^k-32^{k}+3}\)
zastosowana tu zasada włączania i wyłączania w formie szczątkowej...
Reasumując to do kupy otrzymasz coś takiego:
\(\displaystyle{ a_{n}= \sum_{k=3}^{n} {n \choose k}\left[ 3^k-3 \cdot 2^k+3 \right] \cdot 7^{n-k}}\)
No niestety spierniczyłem wychodziło podwójnie nałożyłem wariacje i kombinacje, niestety po takim święcie nie myśli się normalnie...
Dużo lepsze i krótsze Premislava...