szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 gru 2014, o 20:33 
Użytkownik

Posty: 126
Lokalizacja: Kraków
Witajcie!

Mam takie zadanie, z którymi nie do końca wiem, co zrobić.

Cytuj:
W znalezionym rano pudełku od św. Mikołaja były czekoladki o 6 smakach (po 20 sztuk każdego). Kubuś zamierza zjadać jedną czekoladkę co godzinę przez 14 godzin (potem mama każe mu iść spać), ale koniecznie tak, by spróbować wszystkich smaków. Na ile różnych sposobów (kolejność zjadania jest istotna) moze to zrobić?


Czekoladki danego rodzaju między sobą są nierozróżnialne. Wobec tego mamy 14-elementowy ciąg (kolejność zjadania ma znaczenie) do obsadzenia czekoladkami tak, żeby z każdego rodzaju wystąpiła przynajmniej jedna.

Tutaj można zauważyć, że wystarczy wyznaczyć S(14, 6), gdzie S oznacza liczbę Stirlinga 2. rodzaju (liczbę k niepustych podzbiorów zbioru n-elementowego). Dostaniemy więc 6 zbiorów, których moc należy traktować jako liczbę wziętych czekoladek danego rodzaju.

Powiedzmy, że mamy wygenerowaną konfigurację czekoladek:

x_1, x_1, x_1, x_1, x_2, x_2, x_3, x_3, x_4, x_5, x_6, x_6, x_6, x_6

Należałoby teraz zapewnić, że pod każdy indeks trafiają wszystkie możliwe rodzaje czekoladek, czyli przemnażamy wynik przez 6!.

Ale jak w takim razie policzyć to, że zmiana kolejności czekoladek generuje kolejny przypadek, skoro liczba wystąpień danego rodzaju czekoladek może się zmieniać?

Z góry dzięki za pomoc.
Góra
Mężczyzna Offline
PostNapisane: 3 gru 2014, o 23:12 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
Każdej z ośmiu godzin pozostałych można przyporządkować dokładnie jeden z sześciu dowolnych smaków co da:

6^8 - możliwości czyli razem będzie:


{14 \choose 6} \cdot 6! \cdot 6^8

Bo najpierw wybieramy z czternastu godzin sześć godzin w których na pewno zje wszystkie smaki na sześć silnia sposobów!

Widzę że na forum królują liczby stirlinga nawet ja się dałem nabrać!
Góra
Mężczyzna Offline
PostNapisane: 4 gru 2014, o 11:54 
Użytkownik

Posty: 126
Lokalizacja: Kraków
Ale to sprawia, że zliczamy niektóre możliwości podwójnie lub nawet więcej razy.

Dla przykładu:

\underline{1}, \underline{2}, \underline{3}, \underline{4}, \underline{5}, \underline{6}, 1, 1, 1, 2, 2, 2, 3, 4

Niech pokreślone oznaczają czekoladki, które wybieramy, jako koniecznych reprezentantów, żeby dany rodzaj został zjedzony przynajmniej raz.

Konfiguracja taka sama jak:

1, \underline{2}, \underline{3}, \underline{4}, \underline{5}, \underline{6}, \underline{1}, 1, 1, 2, 2, 2, 3, 4

Ale liczymy je podwójnie.
Góra
Mężczyzna Offline
PostNapisane: 4 gru 2014, o 13:43 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
Tak w sumie masz rację tego nie wziąłem pod uwagę

Mam inny pomysł niepotrzebnie dzieliłem na to co musi zjeść i na to co może zjeść weźmy globalnie:

i - x_{i} , 0 < x_{i} , i=1,2,3,4,5,6

znaczy to, że:

i - oznacza rodzaj smaku a x_{i} ile razy ten smak wystąpi w czasie czternastu godzin i zakładam, że każdy smak ma wystąpić więcej niż zero razy bo wtedy będziemy mieć pewność, że zje każdy rodzaj czekolady

Doprowadzi nas to do równania w całkowitych większych od zera:

x_{1}+ x_{2}+ x_{3}+ x_{4}+ x_{5}+ x_{6}=14

I teraz z każdego rozkładu sumujemy permutacje z powtórzeniami

Bo nie tylko ile smaków jakiego rodzaju mamy ale te smaki mogą się permutować
w zależności od godziny w której jemy daną czekoladę.

coś takiego:

(*) \sum_{x_{1}+ x_{2}+ x_{3}+ x_{4}+ x_{5}+ x_{6}=14 , x_{i}>0}^{} \frac{14!}{x_{1}! x_{2}! x_{3}! x_{4}! x_{5}! x_{6}!}


Liczby stirlinga nie rozróżniałyby tych czternastu godzin

Pytanie czy można bardziej tę sumę zwinąć


No tak znalazłem mogło być szybciej to są suriekcje przecież. Zbioru godzin na smaki czekolad.
Jakąś zaćmę miałem i myślałem przy tym zadaniu na odwrót i dlatego nie chciało wyjść.
Na siłę przyporządkowywałem godzinom smaki a nie smakom godziny.


(**) \sum_{i=1}^{6}(-1)^{6-i} {6 \choose i}i^{14}

Na mniejszych liczbach sprawdziłem dla 4 - godzin i trzech smaków liczyłem na piechotę
oraz ze wzoru i działa!

Np:
Literki to smaki a miejsca to godziny:

a,b,c,a - permutacji 12

a,b,c,b - permutacji 12

a,b,c,c - permutacji 12

razem daje 36 - możliwości

teraz ze wzoru:

smaków - n=3

godzin - m=4

\sum_{i=1}^{3}(-1)^{3-i} {3 \choose i}i^4=3-3 \cdot 2^4+3^4=36

Jasne jest że zachodzi równość między (*) a (**)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 kombinatoryka. Na ile sposobów...  megtus  1
 liczby stucyfrowe  Billie Jean  4
 Liczby Catalana - zadanie 2  marcin0045  1
 Pitagoras - na ile sposobów można wybrać krótsze boki  Katarzyna1111  4
 Ile sposobów ustawienia  Paragon16  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl