Hallo,
Ik ben al even aan het rekenen en aan het proberen, maar ik kom niet uit het volgende vraagstuk:
We verdelen \(N\) identieke knikkers over \(A\) verschillende bakjes, zodat er in elk bakje minstens 1 knikker zit. In elk bakje passen maximaal \(Q\) knikkers. Geef de formule voor het aantal manieren waarop dit mogelijk is.
Zonder de restrictie \(Q\) is het aantal combinaties \(C = {{N-1} \choose {A-1}}\). De restrictie zorgt er echter voor dat alle combinaties waarvoor \(N_i>Q\) ongeldig worden, en geeft dus een lager resultaat.
De vraag wordt een stuk ingewikkelder door de restrictie dat elk bakje een maximaal aantal knikkers kan bevatten, en ik vind geen algemene formule om dit te implementeren. Wie kan mij helpen? Gezien ik het moet toepassen in een breder vraagstuk vind ik bij voorkeur een formule die verder geen aannames maakt (dus ook werkt voor bijvoorbeeld \(N<A\) of \(N>A*Q\), maar in die gevallen als resultaat '\(C=0\)' geeft), maar echt alle hulp is welkom op dit moment.
Alvast bedankt,
Wafers
Knikkers in bakken +
Re: Knikkers in bakken +
Hoi iedereen,
Na een lading gecijfer en nadenkwerk ben ik erachter dat de formule
\(C = {{N-1} \choose {A-1}} - A*\sum\limits_{n = A-2}^{N-Q-2} {n \choose {A-2}}\) werkt volgens mij. Mijn vraag nu is nog of dit misschien te vereenvoudigen is?
Groeten,
Wafers
Na een lading gecijfer en nadenkwerk ben ik erachter dat de formule
\(C = {{N-1} \choose {A-1}} - A*\sum\limits_{n = A-2}^{N-Q-2} {n \choose {A-2}}\) werkt volgens mij. Mijn vraag nu is nog of dit misschien te vereenvoudigen is?
Groeten,
Wafers
Re: Knikkers in bakken +
Weer een klein stukje verder, met behulp van wat bronnen van de UU die ik online vond. Ik heb het nu vereenvoudigd tot:
\(C = {{N - 1} \choose {A - 1}} - A*{{N - Q - 1} \choose {N - Q - A}} = {{N - 1} \choose {A - 1}} - A*{{N - Q - 1} \choose {A - 1}}\). Als het kan zou ik het graag als 1 combinatie schrijven, maar daar zie ik zo snel geen mogelijkheid toe. Toch denk ik dat het mogelijk moet zijn. Hulp wordt nog altijd gewaardeerd.
Ik dacht heel even dat diezelfde bron van de UU me bijna nog een nuttige hint had gegeven, toen het beweerde dat \({n \choose m}*{m \choose k} = {{n-k} \choose {m-k}}\), maar als ik dit met cijfers of algebraïsch controleer, lijkt het onzin te zijn... toch?
Groeten,
Wafers
\(C = {{N - 1} \choose {A - 1}} - A*{{N - Q - 1} \choose {N - Q - A}} = {{N - 1} \choose {A - 1}} - A*{{N - Q - 1} \choose {A - 1}}\). Als het kan zou ik het graag als 1 combinatie schrijven, maar daar zie ik zo snel geen mogelijkheid toe. Toch denk ik dat het mogelijk moet zijn. Hulp wordt nog altijd gewaardeerd.
Ik dacht heel even dat diezelfde bron van de UU me bijna nog een nuttige hint had gegeven, toen het beweerde dat \({n \choose m}*{m \choose k} = {{n-k} \choose {m-k}}\), maar als ik dit met cijfers of algebraïsch controleer, lijkt het onzin te zijn... toch?
Groeten,
Wafers
Re: Knikkers in bakken +
En weer een stuk verder. De oplossing die ik eerder vond klopt niet helemaal: deze trekt alle configuraties waarvoor 1 van de A bakjes teveel heeft van het totaal af... maar daarbij worden alle configuraties met meerdere 'overvolle bakjes' er dubbel vanaf getrokken. Daarom tellen we er het aantal configuraties met meer dan 2 overvolle bakjes weer bij op, en trekken we vervolgens het aantal dubbel getelde configuraties met meer dan 3 overvolle bakjes er vanaf etc. Het resultaat is:
\(C = \sum_{i=0}^{i=A} (-1)^i * {A \choose i}*{{N-1-i*Q}\choose {A-1}}\). Als ik dit plot, zie ik dat het heel erg lijkt op een normale verdeling rond \(\frac{A*(Q+1)}{2}\), maar ik ben er nog niet achter hoe dat zo komt. Als nu iemand deze som herkent en denkt "oh dat lost gewoon op tot dit" hoor ik het graag!
Groeten,
Wafers
\(C = \sum_{i=0}^{i=A} (-1)^i * {A \choose i}*{{N-1-i*Q}\choose {A-1}}\). Als ik dit plot, zie ik dat het heel erg lijkt op een normale verdeling rond \(\frac{A*(Q+1)}{2}\), maar ik ben er nog niet achter hoe dat zo komt. Als nu iemand deze som herkent en denkt "oh dat lost gewoon op tot dit" hoor ik het graag!
Groeten,
Wafers
Re: Knikkers in bakken +
Let op: de binomiaalcoefficient \({\alpha \choose k}\) is ook gedefinieerd voor \(\alpha \in \mathbb{R}\),
zie bijvoorbeeld https://en.wikipedia.org/wiki/Binomial_ ... ial_series.
Voor negatieve n levert dit (neem \(\alpha = -n)\):
\({-n \choose k} = (-1)^k \cdot { n+k-1 \choose k}\)
Als bovengrens van jouw sommatie-formule kom ik daarom uit op \(i = \lfloor \frac{N-A}{Q} \rfloor\)
(in plaats van \(i=A\)).
Dat is de grootste gehele waarde kleiner of gelijk aan \(\frac{N-A}{Q}\)
(zie https://en.wikipedia.org/wiki/Floor_and ... _functions)
Voorbeeld:
N=4
A=2
Q=2
Voor de sommatie geldt dan:
i=0 levert: \(1 \cdot {2 \choose 0} \cdot {3 \choose 1} = 3 \)
i=1 levert: \(-1 \cdot {2 \choose 1} \cdot {1 \choose 1} = -2 \)
i=2 levert: \(1 \cdot {2 \choose 2} \cdot {-1 \choose 1} = {-1 \choose 1} = -1 \cdot {1+1-1 \choose 1} = -1 \)
Als we sommeren van \(i=0\) t/m \(i = \lfloor \frac{4-2}{2} \rfloor = 1\) krijgen we C = 3 - 2 = 1.
En er is inderdaad 1 oplossing: 2 knikkers in het eerste en 2 knikkers in het tweede bakje.
PS:
Ik zie vooralsnog geen vereenvoudiging voor deze sommatie...
zie bijvoorbeeld https://en.wikipedia.org/wiki/Binomial_ ... ial_series.
Voor negatieve n levert dit (neem \(\alpha = -n)\):
\({-n \choose k} = (-1)^k \cdot { n+k-1 \choose k}\)
Als bovengrens van jouw sommatie-formule kom ik daarom uit op \(i = \lfloor \frac{N-A}{Q} \rfloor\)
(in plaats van \(i=A\)).
Dat is de grootste gehele waarde kleiner of gelijk aan \(\frac{N-A}{Q}\)
(zie https://en.wikipedia.org/wiki/Floor_and ... _functions)
Voorbeeld:
N=4
A=2
Q=2
Voor de sommatie geldt dan:
i=0 levert: \(1 \cdot {2 \choose 0} \cdot {3 \choose 1} = 3 \)
i=1 levert: \(-1 \cdot {2 \choose 1} \cdot {1 \choose 1} = -2 \)
i=2 levert: \(1 \cdot {2 \choose 2} \cdot {-1 \choose 1} = {-1 \choose 1} = -1 \cdot {1+1-1 \choose 1} = -1 \)
Als we sommeren van \(i=0\) t/m \(i = \lfloor \frac{4-2}{2} \rfloor = 1\) krijgen we C = 3 - 2 = 1.
En er is inderdaad 1 oplossing: 2 knikkers in het eerste en 2 knikkers in het tweede bakje.
PS:
Ik zie vooralsnog geen vereenvoudiging voor deze sommatie...
Re: Knikkers in bakken +
De laatste reactie; ik ben erachter, en bedankt voor je reactie @arie (ietwat laat, maar beter dan nooit). Dit probleem 'knikkers in bakken' is eigenlijk veel beter te beschrijven in dobbelsteenworpen: Op hoe veel manieren kan je A dobbelstenen gooien, met elk Q zijden, zodat het totaal van de worpen gelijk is aan N. De oplossing van dit probleem is niet eenvoudig, maar wel erg bekend. https://en.wikipedia.org/w/index.php?ti ... robability