Mixing
You are given K different boxes and N different balls? In how many ways can one distribute the balls so that...
0
You are given K different boxes and N different balls? In how many ways can one distribute the balls so that no box is empty?
I think I can start off by putting 1 ball into each box so I get n-k balls left.
K out of the N balls can be put in the boxes in n!/(n-k)! ways and that's the farthest I got. I don't know how to proceed. Any help appreciated.
combinatorics
asked Nov 20 '18 at 20:08
Sartr
949
|
show 2 more comments
0
You are given K different boxes and N different balls? In how many ways can one distribute the balls so that no box is empty?
I think I can start off by putting 1 ball into each box so I get n-k balls left.
K out of the N balls can be put in the boxes in n!/(n-k)! ways and that's the farthest I got. I don't know how to proceed. Any help appreciated.
combinatorics
asked Nov 20 '18 at 20:08
Sartr
949
1
This would be difficult to count directly, because you would need to take into account what happens if you "pick" a ball, say ball 1, to put into, say, box 1, and then later put ball 2 in box 1 during the remainder procedure; but you would also count it if you pick ball 2 to put in box 1 first, and then later happen to put ball 1 later. Perhaps better would be to just count the total number of ways of placing the balls into the boxes, then count the number of ways in which at least one box is definitely empty, and subtract.
– Arturo Magidin
Nov 20 '18 at 20:14
And how would I do what you suggested?
– Sartr
Nov 20 '18 at 20:44
1
Inclusion-exclusion? Counting the number of ways of putting $k$ distinguishable balls into $n$ distinguishable boxes with repetitions allowed and no restrictions is straightforward. Then pick one box to keep empty and put $k$ distinguishable balls into the remaining $n-1$ distinguishable boxes. Then pick two boxes to keep empty, and put $k$ distinguishable balls into the remaining $n-2$ boxes, etc.
– Arturo Magidin
Nov 20 '18 at 20:50
1
Just because a problem sounds simple doesn't mean it has a simple solution. There are certainly other ways, but you'll run into issues in any of them. With your method, for example, say you have $12$ balls and $10$ boxes. First, put $10$ of the balls into the boxes: $12!/2!$. Then put the remaining two balls into any of the boxes: $10^2$. But now, say you placed balls $1$-$10$ in boxes $1$-$10$, and then you put ball 11 in box 1, and ball 12 in box 2. You counted this twice, because you you also counted it when you put balls 3-10 in their boxes, then ball 11 in 1 and 12 in 2; then balls 1,2.
– Arturo Magidin
Nov 20 '18 at 21:08
1
So you would need to account for the multiple counts in this situation, too. And if you put both two "extra" balls in the same box, then you counted that particular set up 3 times.
– Arturo Magidin
Nov 20 '18 at 21:09
|
show 2 more comments
0
0
0
You are given K different boxes and N different balls? In how many ways can one distribute the balls so that no box is empty?
I think I can start off by putting 1 ball into each box so I get n-k balls left.
K out of the N balls can be put in the boxes in n!/(n-k)! ways and that's the farthest I got. I don't know how to proceed. Any help appreciated.
combinatorics
asked Nov 20 '18 at 20:08
Sartr
949
You are given K different boxes and N different balls? In how many ways can one distribute the balls so that no box is empty?
I think I can start off by putting 1 ball into each box so I get n-k balls left.
K out of the N balls can be put in the boxes in n!/(n-k)! ways and that's the farthest I got. I don't know how to proceed. Any help appreciated.
combinatorics
combinatorics
asked Nov 20 '18 at 20:08
Sartr
949
asked Nov 20 '18 at 20:08
Sartr
949
asked Nov 20 '18 at 20:08
Sartr
949
asked Nov 20 '18 at 20:08
Sartr
949
asked Nov 20 '18 at 20:08
Sartr
949
949
1
This would be difficult to count directly, because you would need to take into account what happens if you "pick" a ball, say ball 1, to put into, say, box 1, and then later put ball 2 in box 1 during the remainder procedure; but you would also count it if you pick ball 2 to put in box 1 first, and then later happen to put ball 1 later. Perhaps better would be to just count the total number of ways of placing the balls into the boxes, then count the number of ways in which at least one box is definitely empty, and subtract.
– Arturo Magidin
Nov 20 '18 at 20:14
And how would I do what you suggested?
– Sartr
Nov 20 '18 at 20:44
1
Inclusion-exclusion? Counting the number of ways of putting $k$ distinguishable balls into $n$ distinguishable boxes with repetitions allowed and no restrictions is straightforward. Then pick one box to keep empty and put $k$ distinguishable balls into the remaining $n-1$ distinguishable boxes. Then pick two boxes to keep empty, and put $k$ distinguishable balls into the remaining $n-2$ boxes, etc.
– Arturo Magidin
Nov 20 '18 at 20:50
1
Just because a problem sounds simple doesn't mean it has a simple solution. There are certainly other ways, but you'll run into issues in any of them. With your method, for example, say you have $12$ balls and $10$ boxes. First, put $10$ of the balls into the boxes: $12!/2!$. Then put the remaining two balls into any of the boxes: $10^2$. But now, say you placed balls $1$-$10$ in boxes $1$-$10$, and then you put ball 11 in box 1, and ball 12 in box 2. You counted this twice, because you you also counted it when you put balls 3-10 in their boxes, then ball 11 in 1 and 12 in 2; then balls 1,2.
– Arturo Magidin
Nov 20 '18 at 21:08
1
So you would need to account for the multiple counts in this situation, too. And if you put both two "extra" balls in the same box, then you counted that particular set up 3 times.
– Arturo Magidin
Nov 20 '18 at 21:09
|
show 2 more comments
1
This would be difficult to count directly, because you would need to take into account what happens if you "pick" a ball, say ball 1, to put into, say, box 1, and then later put ball 2 in box 1 during the remainder procedure; but you would also count it if you pick ball 2 to put in box 1 first, and then later happen to put ball 1 later. Perhaps better would be to just count the total number of ways of placing the balls into the boxes, then count the number of ways in which at least one box is definitely empty, and subtract.
– Arturo Magidin
Nov 20 '18 at 20:14
And how would I do what you suggested?
– Sartr
Nov 20 '18 at 20:44
1
Inclusion-exclusion? Counting the number of ways of putting $k$ distinguishable balls into $n$ distinguishable boxes with repetitions allowed and no restrictions is straightforward. Then pick one box to keep empty and put $k$ distinguishable balls into the remaining $n-1$ distinguishable boxes. Then pick two boxes to keep empty, and put $k$ distinguishable balls into the remaining $n-2$ boxes, etc.
– Arturo Magidin
Nov 20 '18 at 20:50
1
Just because a problem sounds simple doesn't mean it has a simple solution. There are certainly other ways, but you'll run into issues in any of them. With your method, for example, say you have $12$ balls and $10$ boxes. First, put $10$ of the balls into the boxes: $12!/2!$. Then put the remaining two balls into any of the boxes: $10^2$. But now, say you placed balls $1$-$10$ in boxes $1$-$10$, and then you put ball 11 in box 1, and ball 12 in box 2. You counted this twice, because you you also counted it when you put balls 3-10 in their boxes, then ball 11 in 1 and 12 in 2; then balls 1,2.
– Arturo Magidin
Nov 20 '18 at 21:08
1
So you would need to account for the multiple counts in this situation, too. And if you put both two "extra" balls in the same box, then you counted that particular set up 3 times.
– Arturo Magidin
Nov 20 '18 at 21:09
1
1
This would be difficult to count directly, because you would need to take into account what happens if you "pick" a ball, say ball 1, to put into, say, box 1, and then later put ball 2 in box 1 during the remainder procedure; but you would also count it if you pick ball 2 to put in box 1 first, and then later happen to put ball 1 later. Perhaps better would be to just count the total number of ways of placing the balls into the boxes, then count the number of ways in which at least one box is definitely empty, and subtract.
– Arturo Magidin
Nov 20 '18 at 20:14
This would be difficult to count directly, because you would need to take into account what happens if you "pick" a ball, say ball 1, to put into, say, box 1, and then later put ball 2 in box 1 during the remainder procedure; but you would also count it if you pick ball 2 to put in box 1 first, and then later happen to put ball 1 later. Perhaps better would be to just count the total number of ways of placing the balls into the boxes, then count the number of ways in which at least one box is definitely empty, and subtract.
– Arturo Magidin
Nov 20 '18 at 20:14
And how would I do what you suggested?
– Sartr
Nov 20 '18 at 20:44
And how would I do what you suggested?
– Sartr
Nov 20 '18 at 20:44
1
1
Inclusion-exclusion? Counting the number of ways of putting $k$ distinguishable balls into $n$ distinguishable boxes with repetitions allowed and no restrictions is straightforward. Then pick one box to keep empty and put $k$ distinguishable balls into the remaining $n-1$ distinguishable boxes. Then pick two boxes to keep empty, and put $k$ distinguishable balls into the remaining $n-2$ boxes, etc.
– Arturo Magidin
Nov 20 '18 at 20:50
Inclusion-exclusion? Counting the number of ways of putting $k$ distinguishable balls into $n$ distinguishable boxes with repetitions allowed and no restrictions is straightforward. Then pick one box to keep empty and put $k$ distinguishable balls into the remaining $n-1$ distinguishable boxes. Then pick two boxes to keep empty, and put $k$ distinguishable balls into the remaining $n-2$ boxes, etc.
– Arturo Magidin
Nov 20 '18 at 20:50
1
1
Just because a problem sounds simple doesn't mean it has a simple solution. There are certainly other ways, but you'll run into issues in any of them. With your method, for example, say you have $12$ balls and $10$ boxes. First, put $10$ of the balls into the boxes: $12!/2!$. Then put the remaining two balls into any of the boxes: $10^2$. But now, say you placed balls $1$-$10$ in boxes $1$-$10$, and then you put ball 11 in box 1, and ball 12 in box 2. You counted this twice, because you you also counted it when you put balls 3-10 in their boxes, then ball 11 in 1 and 12 in 2; then balls 1,2.
– Arturo Magidin
Nov 20 '18 at 21:08
Just because a problem sounds simple doesn't mean it has a simple solution. There are certainly other ways, but you'll run into issues in any of them. With your method, for example, say you have $12$ balls and $10$ boxes. First, put $10$ of the balls into the boxes: $12!/2!$. Then put the remaining two balls into any of the boxes: $10^2$. But now, say you placed balls $1$-$10$ in boxes $1$-$10$, and then you put ball 11 in box 1, and ball 12 in box 2. You counted this twice, because you you also counted it when you put balls 3-10 in their boxes, then ball 11 in 1 and 12 in 2; then balls 1,2.
– Arturo Magidin
Nov 20 '18 at 21:08
1
1
So you would need to account for the multiple counts in this situation, too. And if you put both two "extra" balls in the same box, then you counted that particular set up 3 times.
– Arturo Magidin
Nov 20 '18 at 21:09
So you would need to account for the multiple counts in this situation, too. And if you put both two "extra" balls in the same box, then you counted that particular set up 3 times.
– Arturo Magidin
Nov 20 '18 at 21:09
|
show 2 more comments
0
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
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%2f3006821%2fyou-are-given-k-different-boxes-and-n-different-balls-in-how-many-ways-can-one%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
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
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%2f3006821%2fyou-are-given-k-different-boxes-and-n-different-balls-in-how-many-ways-can-one%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
1
This would be difficult to count directly, because you would need to take into account what happens if you "pick" a ball, say ball 1, to put into, say, box 1, and then later put ball 2 in box 1 during the remainder procedure; but you would also count it if you pick ball 2 to put in box 1 first, and then later happen to put ball 1 later. Perhaps better would be to just count the total number of ways of placing the balls into the boxes, then count the number of ways in which at least one box is definitely empty, and subtract.
– Arturo Magidin
Nov 20 '18 at 20:14
And how would I do what you suggested?
– Sartr
Nov 20 '18 at 20:44
1
Inclusion-exclusion? Counting the number of ways of putting $k$ distinguishable balls into $n$ distinguishable boxes with repetitions allowed and no restrictions is straightforward. Then pick one box to keep empty and put $k$ distinguishable balls into the remaining $n-1$ distinguishable boxes. Then pick two boxes to keep empty, and put $k$ distinguishable balls into the remaining $n-2$ boxes, etc.
– Arturo Magidin
Nov 20 '18 at 20:50
1
Just because a problem sounds simple doesn't mean it has a simple solution. There are certainly other ways, but you'll run into issues in any of them. With your method, for example, say you have $12$ balls and $10$ boxes. First, put $10$ of the balls into the boxes: $12!/2!$. Then put the remaining two balls into any of the boxes: $10^2$. But now, say you placed balls $1$-$10$ in boxes $1$-$10$, and then you put ball 11 in box 1, and ball 12 in box 2. You counted this twice, because you you also counted it when you put balls 3-10 in their boxes, then ball 11 in 1 and 12 in 2; then balls 1,2.
– Arturo Magidin
Nov 20 '18 at 21:08
1
So you would need to account for the multiple counts in this situation, too. And if you put both two "extra" balls in the same box, then you counted that particular set up 3 times.
– Arturo Magidin
Nov 20 '18 at 21:09