szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 lip 2015, o 13:59 
Użytkownik

Posty: 59
Lokalizacja: Polska
Czy są jakieś sposoby i tricki przydatne przy wyznaczaniu postaci współczynnika przy x^k (lub odpowiednio innych dla funkcji tworzących wielu zmiennych) w enumeratorze?

Dla przykładu, w zadaniu:
Na ile sposobów można zamówić dwanaście porcji lodów spośród pięciu rodzajów, jeśli nie wolno wziąć więcej niż czterech porcji jednego rodzaju?

Funkcja tworząca to (\sum_{k=0}^{4} x^{k})^{5}, a szukaną odpowiedzą jest współczynnik przy x^12. Jest sposobem policzenie tego ręcznie, ale odpowiedź podana do zadania, czyli {16 \choose 12} - 5 {11 \choose 7} +  {5 \choose 2} {6 \choose 2} nie została raczej otrzymana w ten sposób. Jak to policzyć?
Góra
Mężczyzna Offline
PostNapisane: 12 lip 2015, o 14:48 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Na pewno tak to wygląda? Z tego co pamiętam to stosowałem funkcje tworzące ale wtedy gdy nie było podanego ograniczenia ( tu 4). Na pewno wyjdzie metodą - na ile sposobów możesz rozmieścić
12 porcji lodów w pięciu ich rodzajach. Znasz tą metodę?

-- 12 lip 2015, o 14:50 --

Skorzystaj z tego

x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=12
gdzie x_{i} \le 4 Po prostu od wyniku będziesz musiał odjąć te opcje,gdzie do jednego "pudełka i " trafiło więcej niż 4 porcje
Góra
Mężczyzna Offline
PostNapisane: 12 lip 2015, o 15:38 
Użytkownik

Posty: 59
Lokalizacja: Polska
Ok, byłem w tym miejscu, ale nie potrafiłem znaleźć prostego sposobu na odrzucenie niepoprawnych rozwiązań równania i sobie odpuściłem, ale teraz widzę, że rozwiązanie z jednym iksem większym od 4, to jak rozwiązanie analogiczego równania, tyle, że z prawą stroną pomniejszoną o 5. A potem włączanie-wyłączanie. Dzięki.

A co do sposobu funkcji tworzących z ograniczeniem: Mamy pięć nawiasów, każdy reprezentuje jeden rozdaj lodów. W każdym nawiasie jest x^{0}+x^{1}+x^{2}+x^{3}+x^{4}, gdzie potęga przy x mówi, ile wybranych zostało lodów tego rodzaju (od 0 do 4). Po wymnożeniu tego i odczytaniu współczynnika przy x^{r} odstajemy ilość możliwości wyboru r lodów z zadanymi ograniczeniami. Dlaczego to działa? Weźmy pięć nawiasów takich jak wyżej, tyle, że w każdym niech będzie inna niewiadoma i interpretujmy je tak samo jak wcześniej, czyli jako ilość wystąpień w naszej kombinacji. Po wymnożeniu dostaniemy wielomian będący sumą jednomianów postaci x^{a} y^{b} z^{c} w^{d} t^{e}, każdy z nich reprezentuje jedną możliwą kombinację. Rozwiązaniem byłoby zliczenie jednomianów, dla których a+b+c+d+e=r, czyli rozwiązanie podanego przez Ciebie równania z ograniczeniami. Zamiana wszystkich zmiennych na jedną powoduję, że współczynnikiem przy x^{r} jest liczba takich jednomianów, więc jest ona odpowiedzią.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilość zer z silni przy dowolnej podstawie systemu.  Kacperdev  0
 Miejsca przy stole  Exceleent  4
 Przy stole siedzi 7 osób  Ruahyin  5
 przy stole ...  wilk  0
 Postać jawna sumy  StokrotkaG  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl