Limited combination problem
Problem:
Imagine you have N balls, that you want to put into M boxes. How many ways are there to put N balls into M boxes, if every box can store no more than K balls.
For convinience, I named the number of ways to put N balls into M boxes as "W"
You can't leave any box empty.
Boxes are labeled, balls are not.
There is no difference in which order you put balls.
What I found:
I started by simply counting the number of these ways for boxes with K=2.
K=2 results diagram
W-s seem to form a Pascal's triangle, so I continued for K=3
K=3 results diagram
With K=3 it seems that W-s form a variation of Pascal's triangle, but instead of summing up 2 numbers above, you sum up 3.This is how it works
The same goes for K=4
K=4 results diagram
Question:
I can't find a rigorous proof, that algorithm with these Pascal triangles is true. Please help(
combinatorics balls-in-bins
asked Dec 21 '18 at 20:19
Umurzak
65
add a comment |
Problem:
Imagine you have N balls, that you want to put into M boxes. How many ways are there to put N balls into M boxes, if every box can store no more than K balls.
For convinience, I named the number of ways to put N balls into M boxes as "W"
You can't leave any box empty.
Boxes are labeled, balls are not.
There is no difference in which order you put balls.
What I found:
I started by simply counting the number of these ways for boxes with K=2.
K=2 results diagram
W-s seem to form a Pascal's triangle, so I continued for K=3
K=3 results diagram
With K=3 it seems that W-s form a variation of Pascal's triangle, but instead of summing up 2 numbers above, you sum up 3.This is how it works
The same goes for K=4
K=4 results diagram
Question:
I can't find a rigorous proof, that algorithm with these Pascal triangles is true. Please help(
combinatorics balls-in-bins
asked Dec 21 '18 at 20:19
Umurzak
65
en.m.wikipedia.org/wiki/…
– ablmf
Dec 21 '18 at 20:23
2
In balls-and-boxes problems you must clarify which objects are considered distinct if any. Are all the balls labeled? Are all the balls indistinguishable from one another? Are all the boxes labeled? Are all the boxes indistinguishable from one another?
– JMoravitz
Dec 21 '18 at 20:23
and (in addition to what specified by JMoraitz), what do you exactly mean by put ? because to "throw" undistinguishable balls one after the other is not the same as "laying" (pouring) the balls
– G Cab
Dec 21 '18 at 20:29
Welcome to Math SE. In addition to the other comments above, please also tell us what you've tried so far, any particular aspects you are unsure of, etc. Thanks.
– John Omielan
Dec 21 '18 at 20:39
Start by putting one ball in each box and then analyzing remainder. It is simpler if all balls are identical and you are concerned only about counts.
– herb steinberg
Dec 21 '18 at 22:22
add a comment |
Problem:
Imagine you have N balls, that you want to put into M boxes. How many ways are there to put N balls into M boxes, if every box can store no more than K balls.
For convinience, I named the number of ways to put N balls into M boxes as "W"
You can't leave any box empty.
Boxes are labeled, balls are not.
There is no difference in which order you put balls.
What I found:
I started by simply counting the number of these ways for boxes with K=2.
K=2 results diagram
W-s seem to form a Pascal's triangle, so I continued for K=3
K=3 results diagram
With K=3 it seems that W-s form a variation of Pascal's triangle, but instead of summing up 2 numbers above, you sum up 3.This is how it works
The same goes for K=4
K=4 results diagram
Question:
I can't find a rigorous proof, that algorithm with these Pascal triangles is true. Please help(
combinatorics balls-in-bins
asked Dec 21 '18 at 20:19
Umurzak
65
Problem:
Imagine you have N balls, that you want to put into M boxes. How many ways are there to put N balls into M boxes, if every box can store no more than K balls.
For convinience, I named the number of ways to put N balls into M boxes as "W"
You can't leave any box empty.
Boxes are labeled, balls are not.
There is no difference in which order you put balls.
What I found:
I started by simply counting the number of these ways for boxes with K=2.
K=2 results diagram
W-s seem to form a Pascal's triangle, so I continued for K=3
K=3 results diagram
With K=3 it seems that W-s form a variation of Pascal's triangle, but instead of summing up 2 numbers above, you sum up 3.This is how it works
The same goes for K=4
K=4 results diagram
Question:
I can't find a rigorous proof, that algorithm with these Pascal triangles is true. Please help(
combinatorics balls-in-bins
combinatorics balls-in-bins
asked Dec 21 '18 at 20:19
Umurzak
65
asked Dec 21 '18 at 20:19
Umurzak
65
edited Dec 25 '18 at 16:32
asked Dec 21 '18 at 20:19
Umurzak
65
asked Dec 21 '18 at 20:19
Umurzak
65
asked Dec 21 '18 at 20:19
Umurzak
65
65
en.m.wikipedia.org/wiki/…
– ablmf
Dec 21 '18 at 20:23
2
In balls-and-boxes problems you must clarify which objects are considered distinct if any. Are all the balls labeled? Are all the balls indistinguishable from one another? Are all the boxes labeled? Are all the boxes indistinguishable from one another?
– JMoravitz
Dec 21 '18 at 20:23
and (in addition to what specified by JMoraitz), what do you exactly mean by put ? because to "throw" undistinguishable balls one after the other is not the same as "laying" (pouring) the balls
– G Cab
Dec 21 '18 at 20:29
Welcome to Math SE. In addition to the other comments above, please also tell us what you've tried so far, any particular aspects you are unsure of, etc. Thanks.
– John Omielan
Dec 21 '18 at 20:39
Start by putting one ball in each box and then analyzing remainder. It is simpler if all balls are identical and you are concerned only about counts.
– herb steinberg
Dec 21 '18 at 22:22
add a comment |
en.m.wikipedia.org/wiki/…
– ablmf
Dec 21 '18 at 20:23
2
In balls-and-boxes problems you must clarify which objects are considered distinct if any. Are all the balls labeled? Are all the balls indistinguishable from one another? Are all the boxes labeled? Are all the boxes indistinguishable from one another?
– JMoravitz
Dec 21 '18 at 20:23
and (in addition to what specified by JMoraitz), what do you exactly mean by put ? because to "throw" undistinguishable balls one after the other is not the same as "laying" (pouring) the balls
– G Cab
Dec 21 '18 at 20:29
Welcome to Math SE. In addition to the other comments above, please also tell us what you've tried so far, any particular aspects you are unsure of, etc. Thanks.
– John Omielan
Dec 21 '18 at 20:39
Start by putting one ball in each box and then analyzing remainder. It is simpler if all balls are identical and you are concerned only about counts.
– herb steinberg
Dec 21 '18 at 22:22
en.m.wikipedia.org/wiki/…
– ablmf
Dec 21 '18 at 20:23
en.m.wikipedia.org/wiki/…
– ablmf
Dec 21 '18 at 20:23
2
2
In balls-and-boxes problems you must clarify which objects are considered distinct if any. Are all the balls labeled? Are all the balls indistinguishable from one another? Are all the boxes labeled? Are all the boxes indistinguishable from one another?
– JMoravitz
Dec 21 '18 at 20:23
In balls-and-boxes problems you must clarify which objects are considered distinct if any. Are all the balls labeled? Are all the balls indistinguishable from one another? Are all the boxes labeled? Are all the boxes indistinguishable from one another?
– JMoravitz
Dec 21 '18 at 20:23
and (in addition to what specified by JMoraitz), what do you exactly mean by put ? because to "throw" undistinguishable balls one after the other is not the same as "laying" (pouring) the balls
– G Cab
Dec 21 '18 at 20:29
and (in addition to what specified by JMoraitz), what do you exactly mean by put ? because to "throw" undistinguishable balls one after the other is not the same as "laying" (pouring) the balls
– G Cab
Dec 21 '18 at 20:29
Welcome to Math SE. In addition to the other comments above, please also tell us what you've tried so far, any particular aspects you are unsure of, etc. Thanks.
– John Omielan
Dec 21 '18 at 20:39
Welcome to Math SE. In addition to the other comments above, please also tell us what you've tried so far, any particular aspects you are unsure of, etc. Thanks.
– John Omielan
Dec 21 '18 at 20:39
Start by putting one ball in each box and then analyzing remainder. It is simpler if all balls are identical and you are concerned only about counts.
– herb steinberg
Dec 21 '18 at 22:22
Start by putting one ball in each box and then analyzing remainder. It is simpler if all balls are identical and you are concerned only about counts.
– herb steinberg
Dec 21 '18 at 22:22
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3048857%2flimited-combination-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3048857%2flimited-combination-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
en.m.wikipedia.org/wiki/…
– ablmf
Dec 21 '18 at 20:23
2
In balls-and-boxes problems you must clarify which objects are considered distinct if any. Are all the balls labeled? Are all the balls indistinguishable from one another? Are all the boxes labeled? Are all the boxes indistinguishable from one another?
– JMoravitz
Dec 21 '18 at 20:23
and (in addition to what specified by JMoraitz), what do you exactly mean by put ? because to "throw" undistinguishable balls one after the other is not the same as "laying" (pouring) the balls
– G Cab
Dec 21 '18 at 20:29
Welcome to Math SE. In addition to the other comments above, please also tell us what you've tried so far, any particular aspects you are unsure of, etc. Thanks.
– John Omielan
Dec 21 '18 at 20:39
Start by putting one ball in each box and then analyzing remainder. It is simpler if all balls are identical and you are concerned only about counts.
– herb steinberg
Dec 21 '18 at 22:22