Limited combination problem












1














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(










share|cite|improve this question
























  • 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
















1














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(










share|cite|improve this question
























  • 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














1












1








1


1





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(










share|cite|improve this question















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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 25 '18 at 16:32

























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


















  • 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















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
});


}
});














draft saved

draft discarded


















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
















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Human spaceflight

Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

張江高科駅