Kombinacje z powtórzeniami a klasy abstrakcji

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
matfix
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 6 wrz 2017, o 22:34
Płeć: Kobieta
Lokalizacja: Iława
Podziękował: 1 raz

Kombinacje z powtórzeniami a klasy abstrakcji

Post autor: matfix »

Mam problem z takim oto zadankiem, miałam kilka podejść i nie wiem, czy w ogóle zmierzam w dobrą stronę.

W zbiorze wszystkich ciągów długości \(\displaystyle{ 5}\) o wyrazach ze zbioru \(\displaystyle{ \{0,1,2,3,4,5,6,7,8,9\}}\) wprowadzono relację \(\displaystyle{ \sim}\) taką, że dwa ciągi będą w relacji \(\displaystyle{ \sim}\) wtedy i tylko wtedy, gdy jeden jest pewną permutacją drugiego. Przykładowo ciągi \(\displaystyle{ 10075, 10750}\) i \(\displaystyle{ 00751}\) są parami w relacji \(\displaystyle{ \sim}\). Jak można zobaczyć niewielkim kosztem relacja ta jest relacją równoważności.
a) Wyznacz liczbę klas abstrakcji relacji \(\displaystyle{ \sim}\).
b) Wyznacz liczbę klas abstrakcji relacji \(\displaystyle{ \sim}\), w których cyfry \(\displaystyle{ 5, 7}\) i \(\displaystyle{ 9}\) mogą się pojawić co najwyżej raz.

Moje rozwiązanie:
a) jako, że każda kombinacja \(\displaystyle{ k}\)-elementowa z powtórzeniami zbioru \(\displaystyle{ n}\)-elementowego jest klasą abstrakcji wszystkich \(\displaystyle{ k}\)-elemenowych wariacji z powtórzeniami zbioru \(\displaystyle{ n}\)-elementowego różniących się między sobą tylko kolejnością elementów to ten podpunkt jest prosty. Tych klas jest \(\displaystyle{ {10+5-1 \choose 5}= {14 \choose 5}=2002}\)
b) tutaj zaczynają się problemy, chciałam zrobić tak, że od wszystkich klas abstrakcji odejmę wszystkie, gdzie \(\displaystyle{ 5, 7}\) i \(\displaystyle{ 9}\) występują co najmniej \(\displaystyle{ 2}\) razy (to zliczam za pomocą zasady włączeń i wyłączeń)
\(\displaystyle{ A_{i}}\) to zbiór gdzie \(\displaystyle{ i}\) występuje \(\displaystyle{ 2, 3, 4}\) lub \(\displaystyle{ 5}\) razy
Zaczynając od końca \(\displaystyle{ |A_{5}\cap A_{7}\cap A_{9}|= 0}\) bo nie mogą jednocześnie być po \(\displaystyle{ 2}\) wszystkie \(\displaystyle{ 3}\). \(\displaystyle{ |A_{i}\cap A_{j}|=10}\), bo np mamy \(\displaystyle{ 5577*}\) (\(\displaystyle{ *}\) to jedna z \(\displaystyle{ 8}\) pozostałych cyfr), \(\displaystyle{ 55777, 55577}\), czyli łącznie \(\displaystyle{ 10}\).
Przy pojedynczych zbiorach się gubię, zobaczmy sytuację dla \(\displaystyle{ A_{5)}\).
Nasze opcje:
- \(\displaystyle{ 5}\) razy występuje \(\displaystyle{ 55555}\) (jedna możliwość)
- \(\displaystyle{ 4}\) razy występuje \(\displaystyle{ 5555*}\) (\(\displaystyle{ 9}\) możliwości, bo każda z pozostałych cyfr może być \(\displaystyle{ *}\))
- \(\displaystyle{ 3}\) razy występuje \(\displaystyle{ 555**}\) czy tutaj myślę dobrze, że za \(\displaystyle{ **}\) mogę podstawić kombinacje \(\displaystyle{ 2}\)-elementowe z powtórzeniami ze zbioru \(\displaystyle{ 9}\)-elementowego ?? wtedy jest ich \(\displaystyle{ {10 \choose 2}=45}\)
- \(\displaystyle{ 2}\) razy występuje \(\displaystyle{ 55***}\) (rozumowanie jak przy poprzednim punkcie) \(\displaystyle{ {12 \choose 3} =220}\)

Wtedy ostateczny wynik to \(\displaystyle{ 2002- 3 \cdot (220+45+9+1)+{3 \choose 2} \cdot 10 =2002-275 \cdot 3+30=1207}\)

Jeżeli popełniłam jakieś błędy to nie mam bladego pojęcia gdzie i jakie, bo niestety ten dział matematyki nie jest moją mocną stroną.
Ostatnio zmieniony 7 wrz 2017, o 00:32 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Kombinacje z powtórzeniami a klasy abstrakcji

Post autor: arek1357 »

Pierwsze jest ok a drugie:

\(\displaystyle{ \left\{ 0,1,2,3,4,6,8\right\} \cup \left\{ 5,7,9\right\}}\)

podzielmy to jak wyżej na dwa zbiory

jeżeli mamy 5 liczb ze zbioru pierwszego a z drugiego zero to:

ilość możliwości odpowiada ilości rozwiązań równania:

\(\displaystyle{ x_{1}+x_{2}+...+x_{7}=5}\)


jeżeli mamy 4 liczby ze zbioru pierwszego a z drugiego jedną to:

ilość możliwości odpowiada ilości rozwiązań równania:

\(\displaystyle{ x_{1}+x_{2}+...+x_{7}=4}\)

pomnożone przez:

\(\displaystyle{ {3 \choose 1}}\)


jeżeli mamy 3 liczby ze zbioru pierwszego a z drugiego dwie to:

ilość możliwości odpowiada ilości rozwiązań równania:

\(\displaystyle{ x_{1}+x_{2}+...+x_{7}=3}\)

pomnożone przez:

\(\displaystyle{ {3 \choose 2}}\)


jeżeli mamy 2 liczby ze zbioru pierwszego a z drugiego trzy to:

ilość możliwości odpowiada ilości rozwiązań równania:

\(\displaystyle{ x_{1}+x_{2}+...+x_{7}=2}\)

pomnożone przez:

\(\displaystyle{ {3 \choose 3}}\)

Teraz to zsumować...
ODPOWIEDZ