logowanie

matematyka » forum » forum zadaniowe - zadania różne » zadanie

Zadania tekstowe, zadanie nr 170

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

enikon
postów: 2
2014-08-31 17:20:33

Kombinatoryka

Witam mam problem z zadaniem.

Maciek ma n kredek w p kolorach. Kredek z każdego koloru jest ip. Pewnego dnia postanowił zabrać do szkoły dokładnie k z nich. Na ile sposobów jest w stanie wykonać to zadanie jeśli:

a) n=6 p=3 i1=3 i2=2 i3=1 k=3?
b) n=10 p=5 i1=1 i2=1 i3=2 i4=3 i5=3 k=4?

Kredki o jednym kolorze są nieodróżnialne, Maciek może zabrać maksymalnie i1 kredek pierwszego koloru, i2 drugiego itd.

Bardzo zależy mi na wzorze i szczegółowym rozwiązaniu.
Niestety nie potrafię znaleźć tego w internecie.

Obstawiam że trzeba wymyślić sprytny sposób na połączenie wzorów na permutację z powtórzeniami i kombinację bez powtórzeń


tumor
postów: 8070
2014-08-31 18:27:28

Dla tak niewielkich liczb da się w miarę szybko wypisać rozwiązanie.
Nie wiem, czy są na to wzory proste, ale zawsze też można machnąć metodę rekurencyjną, która będzie wcale nie najgorsza do stosowania ręcznego.

Jeśli wybieramy $k$ kredek spośród n kredek, gdy w kolejnych kolorach jest $i_1,i_2,...$ kredek, to oznaczmy to
$S^n_k(i_1,i_2,...)$, liczby p pamiętać w zasadzie nie trzeba, jest ilością argumentów)


Z pierwszego koloru bierzemy $x$ kredek, możemy wziąć najwięcej $min(k,i_1)$ elementów (bo bierzemy najwyżej tyle ile Maciek chce wziąć i najwyżej tyle, ile jest w danym kolorze), natomiast najmniej możemy wziąć $max(0, k+i_1-n)$ (ponieważ nie możemy wziąć oczywiście mniej niż $0$, natomiast pozostałych kredek, czyli $n-i_1$, musi być nie mniej niż planowanych do wzięcia k-x, czyli $n-i_1\ge k-x$).
Gdy weźmiemy x kredek, to trzeba będzie wybierać w sytuacji, gdy kolorów jest o 1 mniej, liczba kredek jest o i_1 mniejsza, liczba kredek do wzięcia jest o x mniejsza. Czyli

$S_k^n(i_1,i_2,i_3,...,i_t)=\sum_{x=max(0,k+i_1-n)}^{min(k,i_1)}S_{k-x}^{n-i_1}(i_2,i_3,...,i_t)$

Dla przykładu
$S_3^6(3,2,1)=
S_3^3(2,1)+S_2^3(2,1)+S_1^3(2,1)+S_0^3(2,1)$

Przy tym $S_z^z=1$, $S_0^z=1$, czyli mamy
$S_3^6(3,2,1)=
S_3^3(2,1)+S_2^3(2,1)+S_1^3(2,1)+S_0^3(2,1)=
1+S_2^3(2,1)+S_1^3(2,1)+1=
1+S_1^1(1)+S_0^1(1)+S_1^1(1)+S_0^1(1)+1=6$

Odpowiada to oczywiście sytuacji, gdy mamy kredki w kolorach
111,22,3, możemy wziąć
111
112
113
122
123
223
(sześć możliwości)

Dodatkowo mamy $S_1^z(i_1,...,i_t)=t$, to też uprości liczenie możliwości, no i jeśli został 1 kolor, to już mamy zawsze tylko jedną możliwość.

Analogicznie liczymy dla
$S_4^{10}(1,1,2,3,3)=
S_4^9(1,2,3,3)+
S_3^9(1,2,3,3)=$
$S_4^8(2,3,3)+
S_3^8(2,3,3)+
S_3^8(2,3,3)+
S_2^8(2,3,3)=$
$S_4^6(3,3)+
S_3^6(3,3)+
S_2^6(3,3)+
...$

Więcej tu pisania niż liczenia. Ponadto gdy zostaną dwa kolory, łatwo liczyć w pamięci ilość możliwości.

Wiadomość była modyfikowana 2014-08-31 18:31:50 przez tumor

enikon
postów: 2
2014-08-31 20:29:03

Dzięki tumor za błyskawiczną odpowiedź.

Tak sobie patrząc na rekurencję pomyślałem że jednak jakiś wzór mógłby istnieć (sporo ze wzorów rekurencyjnych da się zapisać wzorem prostym).
Oczywiście po modyfikacji ilości kredek jak napisano post wyżej żeby każde ip wynosiło min(k,ip).

Oczywiście znalezienie wzoru byłoby świetnym wyzwaniem.

Myślałem o czymś o wyglądzie mniej więcej w tym stylu ( to NIE jest żaden wzór ):

$ \frac{n!}{\frac{k\cdot(n-i1)}{k-i1}+\frac{k\cdot(n-i2)}{k-i1}+\cdots}$





strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj