Distribute distinct objects in identical boxes
$begingroup$
Number of ways to distribute $6$ distinct objects to $3$ identical boxes such that each box should have atleast one?
$mathbf {Is there any standard formula for these sums}$, as we have for $langle identical object, distinct boxrangle$ pair as $$N+R-1choose R-1$$
combinatorics stirling-numbers balls-in-bins
edited Oct 5 '13 at 19:25
dibyendu
356318
asked Sep 4 '12 at 6:14
AizenAizen
14917
$endgroup$
add a comment |
$begingroup$
Number of ways to distribute $6$ distinct objects to $3$ identical boxes such that each box should have atleast one?
$mathbf {Is there any standard formula for these sums}$, as we have for $langle identical object, distinct boxrangle$ pair as $$N+R-1choose R-1$$
combinatorics stirling-numbers balls-in-bins
edited Oct 5 '13 at 19:25
dibyendu
356318
asked Sep 4 '12 at 6:14
AizenAizen
14917
$endgroup$
add a comment |
$begingroup$
Number of ways to distribute $6$ distinct objects to $3$ identical boxes such that each box should have atleast one?
$mathbf {Is there any standard formula for these sums}$, as we have for $langle identical object, distinct boxrangle$ pair as $$N+R-1choose R-1$$
combinatorics stirling-numbers balls-in-bins
edited Oct 5 '13 at 19:25
dibyendu
356318
asked Sep 4 '12 at 6:14
AizenAizen
14917
$endgroup$
Number of ways to distribute $6$ distinct objects to $3$ identical boxes such that each box should have atleast one?
$mathbf {Is there any standard formula for these sums}$, as we have for $langle identical object, distinct boxrangle$ pair as $$N+R-1choose R-1$$
combinatorics stirling-numbers balls-in-bins
combinatorics stirling-numbers balls-in-bins
edited Oct 5 '13 at 19:25
dibyendu
356318
asked Sep 4 '12 at 6:14
AizenAizen
14917
edited Oct 5 '13 at 19:25
dibyendu
356318
asked Sep 4 '12 at 6:14
AizenAizen
14917
edited Oct 5 '13 at 19:25
dibyendu
356318
edited Oct 5 '13 at 19:25
dibyendu
356318
edited Oct 5 '13 at 19:25
dibyendu
356318
356318
asked Sep 4 '12 at 6:14
AizenAizen
14917
asked Sep 4 '12 at 6:14
AizenAizen
14917
asked Sep 4 '12 at 6:14
AizenAizen
14917
14917
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
These numbers are the Stirling numbers of the second kind; the specific one that you mention is denoted by $left{6atop 3right}$ or $S(6,3)$. These numbers satisfy a fairly simple recurrence relation that is reminiscent of the relation $dbinom{n+1}k=dbinom{n}k+dbinom{n}{k-1}$ satisfied by the binomial coefficients:
$$left{n+1atop kright}=kleft{natop kright}+left{natop k-1right};,$$
with initial conditions $left{0atop 0right}=1$ and $left{natop 0right}=left{0atop nright}=0$ for $n>0$.
Added: This recurrence isn’t hard to prove. Consider the ways of partitioning the integers $1,dots,n+1$ into $k$ non-empty sets. We can start with a partition of ${1,dots,n}$ into $k-1$ non-empty sets and make ${n+1}$ the $k$-th set; there are $left{natop k-1right}$ ways to do this. Or we can partition ${1,dots,n}$ into $k$ non-empty sets and add $n+1$ to one of those $k$ sets; there are $kleft{natop kright}$ ways to do this. The total number of possibilities is therefore $kleft{natop kright}+left{natop k-1right}$.
There is an explicit formula for $left{natop kright}$, but it’s rather ugly:
$$left{natop kright}=frac1{k!}sum_{i=0}^k(-1)^{k-i}binom{k}ii^n;.$$
answered Sep 4 '12 at 6:23
Brian M. ScottBrian M. Scott
459k38513916
$endgroup$
$begingroup$
If its asked not at least 1 but any numbers then or for at least 2 ??
$endgroup$
– Aizen
Sep 4 '12 at 6:38
$begingroup$
@Aizen: If each box must contain at least two objects, an inclusion-exclusion argument shows that the number of arrangements is $$sum_{i=1}^{k-1}(-1)^{k-1}binom{n}ileft{n-iatop k-iright};.$$ It’s entirely possible that this can be simplified, but I don’t immediately see anything nice. After the ‘at least $2$’ case it looks to be getting really messy; I’d probably try to work with generating functions at that point.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:24
$begingroup$
But inclusion-exclusion is valid when both are distinct.
$endgroup$
– Aizen
Sep 4 '12 at 7:37
$begingroup$
@Aizen: I don’t understand what you’re trying to say. Inclusion-exclusion is a general technique that is applicable in a wide variety of situations.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:40
add a comment |
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%2f190820%2fdistribute-distinct-objects-in-identical-boxes%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
These numbers are the Stirling numbers of the second kind; the specific one that you mention is denoted by $left{6atop 3right}$ or $S(6,3)$. These numbers satisfy a fairly simple recurrence relation that is reminiscent of the relation $dbinom{n+1}k=dbinom{n}k+dbinom{n}{k-1}$ satisfied by the binomial coefficients:
$$left{n+1atop kright}=kleft{natop kright}+left{natop k-1right};,$$
with initial conditions $left{0atop 0right}=1$ and $left{natop 0right}=left{0atop nright}=0$ for $n>0$.
Added: This recurrence isn’t hard to prove. Consider the ways of partitioning the integers $1,dots,n+1$ into $k$ non-empty sets. We can start with a partition of ${1,dots,n}$ into $k-1$ non-empty sets and make ${n+1}$ the $k$-th set; there are $left{natop k-1right}$ ways to do this. Or we can partition ${1,dots,n}$ into $k$ non-empty sets and add $n+1$ to one of those $k$ sets; there are $kleft{natop kright}$ ways to do this. The total number of possibilities is therefore $kleft{natop kright}+left{natop k-1right}$.
There is an explicit formula for $left{natop kright}$, but it’s rather ugly:
$$left{natop kright}=frac1{k!}sum_{i=0}^k(-1)^{k-i}binom{k}ii^n;.$$
answered Sep 4 '12 at 6:23
Brian M. ScottBrian M. Scott
459k38513916
$endgroup$
$begingroup$
If its asked not at least 1 but any numbers then or for at least 2 ??
$endgroup$
– Aizen
Sep 4 '12 at 6:38
$begingroup$
@Aizen: If each box must contain at least two objects, an inclusion-exclusion argument shows that the number of arrangements is $$sum_{i=1}^{k-1}(-1)^{k-1}binom{n}ileft{n-iatop k-iright};.$$ It’s entirely possible that this can be simplified, but I don’t immediately see anything nice. After the ‘at least $2$’ case it looks to be getting really messy; I’d probably try to work with generating functions at that point.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:24
$begingroup$
But inclusion-exclusion is valid when both are distinct.
$endgroup$
– Aizen
Sep 4 '12 at 7:37
$begingroup$
@Aizen: I don’t understand what you’re trying to say. Inclusion-exclusion is a general technique that is applicable in a wide variety of situations.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:40
add a comment |
$begingroup$
These numbers are the Stirling numbers of the second kind; the specific one that you mention is denoted by $left{6atop 3right}$ or $S(6,3)$. These numbers satisfy a fairly simple recurrence relation that is reminiscent of the relation $dbinom{n+1}k=dbinom{n}k+dbinom{n}{k-1}$ satisfied by the binomial coefficients:
$$left{n+1atop kright}=kleft{natop kright}+left{natop k-1right};,$$
with initial conditions $left{0atop 0right}=1$ and $left{natop 0right}=left{0atop nright}=0$ for $n>0$.
Added: This recurrence isn’t hard to prove. Consider the ways of partitioning the integers $1,dots,n+1$ into $k$ non-empty sets. We can start with a partition of ${1,dots,n}$ into $k-1$ non-empty sets and make ${n+1}$ the $k$-th set; there are $left{natop k-1right}$ ways to do this. Or we can partition ${1,dots,n}$ into $k$ non-empty sets and add $n+1$ to one of those $k$ sets; there are $kleft{natop kright}$ ways to do this. The total number of possibilities is therefore $kleft{natop kright}+left{natop k-1right}$.
There is an explicit formula for $left{natop kright}$, but it’s rather ugly:
$$left{natop kright}=frac1{k!}sum_{i=0}^k(-1)^{k-i}binom{k}ii^n;.$$
answered Sep 4 '12 at 6:23
Brian M. ScottBrian M. Scott
459k38513916
$endgroup$
$begingroup$
If its asked not at least 1 but any numbers then or for at least 2 ??
$endgroup$
– Aizen
Sep 4 '12 at 6:38
$begingroup$
@Aizen: If each box must contain at least two objects, an inclusion-exclusion argument shows that the number of arrangements is $$sum_{i=1}^{k-1}(-1)^{k-1}binom{n}ileft{n-iatop k-iright};.$$ It’s entirely possible that this can be simplified, but I don’t immediately see anything nice. After the ‘at least $2$’ case it looks to be getting really messy; I’d probably try to work with generating functions at that point.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:24
$begingroup$
But inclusion-exclusion is valid when both are distinct.
$endgroup$
– Aizen
Sep 4 '12 at 7:37
$begingroup$
@Aizen: I don’t understand what you’re trying to say. Inclusion-exclusion is a general technique that is applicable in a wide variety of situations.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:40
add a comment |
$begingroup$
These numbers are the Stirling numbers of the second kind; the specific one that you mention is denoted by $left{6atop 3right}$ or $S(6,3)$. These numbers satisfy a fairly simple recurrence relation that is reminiscent of the relation $dbinom{n+1}k=dbinom{n}k+dbinom{n}{k-1}$ satisfied by the binomial coefficients:
$$left{n+1atop kright}=kleft{natop kright}+left{natop k-1right};,$$
with initial conditions $left{0atop 0right}=1$ and $left{natop 0right}=left{0atop nright}=0$ for $n>0$.
Added: This recurrence isn’t hard to prove. Consider the ways of partitioning the integers $1,dots,n+1$ into $k$ non-empty sets. We can start with a partition of ${1,dots,n}$ into $k-1$ non-empty sets and make ${n+1}$ the $k$-th set; there are $left{natop k-1right}$ ways to do this. Or we can partition ${1,dots,n}$ into $k$ non-empty sets and add $n+1$ to one of those $k$ sets; there are $kleft{natop kright}$ ways to do this. The total number of possibilities is therefore $kleft{natop kright}+left{natop k-1right}$.
There is an explicit formula for $left{natop kright}$, but it’s rather ugly:
$$left{natop kright}=frac1{k!}sum_{i=0}^k(-1)^{k-i}binom{k}ii^n;.$$
answered Sep 4 '12 at 6:23
Brian M. ScottBrian M. Scott
459k38513916
$endgroup$
These numbers are the Stirling numbers of the second kind; the specific one that you mention is denoted by $left{6atop 3right}$ or $S(6,3)$. These numbers satisfy a fairly simple recurrence relation that is reminiscent of the relation $dbinom{n+1}k=dbinom{n}k+dbinom{n}{k-1}$ satisfied by the binomial coefficients:
$$left{n+1atop kright}=kleft{natop kright}+left{natop k-1right};,$$
with initial conditions $left{0atop 0right}=1$ and $left{natop 0right}=left{0atop nright}=0$ for $n>0$.
Added: This recurrence isn’t hard to prove. Consider the ways of partitioning the integers $1,dots,n+1$ into $k$ non-empty sets. We can start with a partition of ${1,dots,n}$ into $k-1$ non-empty sets and make ${n+1}$ the $k$-th set; there are $left{natop k-1right}$ ways to do this. Or we can partition ${1,dots,n}$ into $k$ non-empty sets and add $n+1$ to one of those $k$ sets; there are $kleft{natop kright}$ ways to do this. The total number of possibilities is therefore $kleft{natop kright}+left{natop k-1right}$.
There is an explicit formula for $left{natop kright}$, but it’s rather ugly:
$$left{natop kright}=frac1{k!}sum_{i=0}^k(-1)^{k-i}binom{k}ii^n;.$$
answered Sep 4 '12 at 6:23
Brian M. ScottBrian M. Scott
459k38513916
edited Sep 4 '12 at 6:31
answered Sep 4 '12 at 6:23
Brian M. ScottBrian M. Scott
459k38513916
answered Sep 4 '12 at 6:23
Brian M. ScottBrian M. Scott
459k38513916
answered Sep 4 '12 at 6:23
Brian M. ScottBrian M. Scott
459k38513916
459k38513916
$begingroup$
If its asked not at least 1 but any numbers then or for at least 2 ??
$endgroup$
– Aizen
Sep 4 '12 at 6:38
$begingroup$
@Aizen: If each box must contain at least two objects, an inclusion-exclusion argument shows that the number of arrangements is $$sum_{i=1}^{k-1}(-1)^{k-1}binom{n}ileft{n-iatop k-iright};.$$ It’s entirely possible that this can be simplified, but I don’t immediately see anything nice. After the ‘at least $2$’ case it looks to be getting really messy; I’d probably try to work with generating functions at that point.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:24
$begingroup$
But inclusion-exclusion is valid when both are distinct.
$endgroup$
– Aizen
Sep 4 '12 at 7:37
$begingroup$
@Aizen: I don’t understand what you’re trying to say. Inclusion-exclusion is a general technique that is applicable in a wide variety of situations.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:40
add a comment |
$begingroup$
If its asked not at least 1 but any numbers then or for at least 2 ??
$endgroup$
– Aizen
Sep 4 '12 at 6:38
$begingroup$
@Aizen: If each box must contain at least two objects, an inclusion-exclusion argument shows that the number of arrangements is $$sum_{i=1}^{k-1}(-1)^{k-1}binom{n}ileft{n-iatop k-iright};.$$ It’s entirely possible that this can be simplified, but I don’t immediately see anything nice. After the ‘at least $2$’ case it looks to be getting really messy; I’d probably try to work with generating functions at that point.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:24
$begingroup$
But inclusion-exclusion is valid when both are distinct.
$endgroup$
– Aizen
Sep 4 '12 at 7:37
$begingroup$
@Aizen: I don’t understand what you’re trying to say. Inclusion-exclusion is a general technique that is applicable in a wide variety of situations.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:40
$begingroup$
If its asked not at least 1 but any numbers then or for at least 2 ??
$endgroup$
– Aizen
Sep 4 '12 at 6:38
$begingroup$
If its asked not at least 1 but any numbers then or for at least 2 ??
$endgroup$
– Aizen
Sep 4 '12 at 6:38
$begingroup$
@Aizen: If each box must contain at least two objects, an inclusion-exclusion argument shows that the number of arrangements is $$sum_{i=1}^{k-1}(-1)^{k-1}binom{n}ileft{n-iatop k-iright};.$$ It’s entirely possible that this can be simplified, but I don’t immediately see anything nice. After the ‘at least $2$’ case it looks to be getting really messy; I’d probably try to work with generating functions at that point.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:24
$begingroup$
@Aizen: If each box must contain at least two objects, an inclusion-exclusion argument shows that the number of arrangements is $$sum_{i=1}^{k-1}(-1)^{k-1}binom{n}ileft{n-iatop k-iright};.$$ It’s entirely possible that this can be simplified, but I don’t immediately see anything nice. After the ‘at least $2$’ case it looks to be getting really messy; I’d probably try to work with generating functions at that point.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:24
$begingroup$
But inclusion-exclusion is valid when both are distinct.
$endgroup$
– Aizen
Sep 4 '12 at 7:37
$begingroup$
But inclusion-exclusion is valid when both are distinct.
$endgroup$
– Aizen
Sep 4 '12 at 7:37
$begingroup$
@Aizen: I don’t understand what you’re trying to say. Inclusion-exclusion is a general technique that is applicable in a wide variety of situations.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:40
$begingroup$
@Aizen: I don’t understand what you’re trying to say. Inclusion-exclusion is a general technique that is applicable in a wide variety of situations.
$endgroup$
– Brian M. Scott
Sep 4 '12 at 7:40
add a comment |
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.
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%2f190820%2fdistribute-distinct-objects-in-identical-boxes%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
