Mixing
Why is my solution to stars and bars wrong?
$begingroup$
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_two
I can see that in case 2, where it is possible to have bars in the same gaps, that there are $n+1$ gaps and $k-1$ bars. But surely the binomial coefficient of ${n+1}choose{k-1}$ (number of ways of filling $n+1$ gaps with $k-1$ bars) discounts possibilities where bars are in the same gap? My formula is $$frac{(n+1)^{k-1}}{(k-1)!}$$
As we have $n+1$ choices for position of each bar and the ordering of bars doesn't matter.
Moreover, how is the binomial coefficient ${n+1}choose{k-1}$ $=$ ${n+k-1}choose{n}$? It doesn't work for the case $ n= 7, k=4$?
combinatorics proof-explanation combinations
asked Jan 24 at 20:03
Dis-integratingDis-integrating
1,043526
$endgroup$
|
show 4 more comments
$begingroup$
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_two
I can see that in case 2, where it is possible to have bars in the same gaps, that there are $n+1$ gaps and $k-1$ bars. But surely the binomial coefficient of ${n+1}choose{k-1}$ (number of ways of filling $n+1$ gaps with $k-1$ bars) discounts possibilities where bars are in the same gap? My formula is $$frac{(n+1)^{k-1}}{(k-1)!}$$
As we have $n+1$ choices for position of each bar and the ordering of bars doesn't matter.
Moreover, how is the binomial coefficient ${n+1}choose{k-1}$ $=$ ${n+k-1}choose{n}$? It doesn't work for the case $ n= 7, k=4$?
combinatorics proof-explanation combinations
asked Jan 24 at 20:03
Dis-integratingDis-integrating
1,043526
$endgroup$
$begingroup$
If $k=3,n=2$ you get $frac {3^2}2$ which isn't even an integer.
$endgroup$
– lulu
Jan 24 at 20:08
1
$begingroup$
The article you link to says the $textit {multinomial symbol} left(binom {n+1}{k-1}right)$ equals the $textit {binomial symbol} $ $binom {n+k-1}n$ The proof supplied in the article is hard to beat for elegance.
$endgroup$
– lulu
Jan 24 at 20:11
1
$begingroup$
I do not think Wikipedia is as clear as it should be on the stars and bars in theorem two. I would simply say you have $n$ stars and $k-1$ bars to put in any order (e.g. bars are allowed next to each other), so ${n+k-1 choose n}={n+k-1 choose k-1}$ ways of doing this depending on whether you choose the stars' positions first or the bars' positions first.
$endgroup$
– Henry
Jan 24 at 20:11
$begingroup$
@lulu You should not refer to $left(!binom {n}{k}!right)$ as the "multinomial symbol". The multinomial symbol is $binom{n}{n_1,n_2,dots,n_k} = frac{n!}{n_1!,n_2!dotsm n_k!}$. You sometimes hear $left(!binom {n}{k}!right)$ referred to as the multichoose number or the multiset number, of which I think the second is more clear.
$endgroup$
– Misha Lavrov
Jan 24 at 20:16
1
$begingroup$
No problem. At first glance, your formula looks sensible...these things are annoyingly unintuitive.
$endgroup$
– lulu
Jan 24 at 20:43
|
show 4 more comments
$begingroup$
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_two
I can see that in case 2, where it is possible to have bars in the same gaps, that there are $n+1$ gaps and $k-1$ bars. But surely the binomial coefficient of ${n+1}choose{k-1}$ (number of ways of filling $n+1$ gaps with $k-1$ bars) discounts possibilities where bars are in the same gap? My formula is $$frac{(n+1)^{k-1}}{(k-1)!}$$
As we have $n+1$ choices for position of each bar and the ordering of bars doesn't matter.
Moreover, how is the binomial coefficient ${n+1}choose{k-1}$ $=$ ${n+k-1}choose{n}$? It doesn't work for the case $ n= 7, k=4$?
combinatorics proof-explanation combinations
asked Jan 24 at 20:03
Dis-integratingDis-integrating
1,043526
$endgroup$
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_two
I can see that in case 2, where it is possible to have bars in the same gaps, that there are $n+1$ gaps and $k-1$ bars. But surely the binomial coefficient of ${n+1}choose{k-1}$ (number of ways of filling $n+1$ gaps with $k-1$ bars) discounts possibilities where bars are in the same gap? My formula is $$frac{(n+1)^{k-1}}{(k-1)!}$$
As we have $n+1$ choices for position of each bar and the ordering of bars doesn't matter.
Moreover, how is the binomial coefficient ${n+1}choose{k-1}$ $=$ ${n+k-1}choose{n}$? It doesn't work for the case $ n= 7, k=4$?
combinatorics proof-explanation combinations
combinatorics proof-explanation combinations
asked Jan 24 at 20:03
Dis-integratingDis-integrating
1,043526
asked Jan 24 at 20:03
Dis-integratingDis-integrating
1,043526
edited Jan 24 at 20:24
Dis-integrating
asked Jan 24 at 20:03
Dis-integratingDis-integrating
1,043526
asked Jan 24 at 20:03
Dis-integratingDis-integrating
1,043526
asked Jan 24 at 20:03
Dis-integratingDis-integrating
1,043526
1,043526
$begingroup$
If $k=3,n=2$ you get $frac {3^2}2$ which isn't even an integer.
$endgroup$
– lulu
Jan 24 at 20:08
1
$begingroup$
The article you link to says the $textit {multinomial symbol} left(binom {n+1}{k-1}right)$ equals the $textit {binomial symbol} $ $binom {n+k-1}n$ The proof supplied in the article is hard to beat for elegance.
$endgroup$
– lulu
Jan 24 at 20:11
1
$begingroup$
I do not think Wikipedia is as clear as it should be on the stars and bars in theorem two. I would simply say you have $n$ stars and $k-1$ bars to put in any order (e.g. bars are allowed next to each other), so ${n+k-1 choose n}={n+k-1 choose k-1}$ ways of doing this depending on whether you choose the stars' positions first or the bars' positions first.
$endgroup$
– Henry
Jan 24 at 20:11
$begingroup$
@lulu You should not refer to $left(!binom {n}{k}!right)$ as the "multinomial symbol". The multinomial symbol is $binom{n}{n_1,n_2,dots,n_k} = frac{n!}{n_1!,n_2!dotsm n_k!}$. You sometimes hear $left(!binom {n}{k}!right)$ referred to as the multichoose number or the multiset number, of which I think the second is more clear.
$endgroup$
– Misha Lavrov
Jan 24 at 20:16
1
$begingroup$
No problem. At first glance, your formula looks sensible...these things are annoyingly unintuitive.
$endgroup$
– lulu
Jan 24 at 20:43
|
show 4 more comments
$begingroup$
If $k=3,n=2$ you get $frac {3^2}2$ which isn't even an integer.
$endgroup$
– lulu
Jan 24 at 20:08
1
$begingroup$
The article you link to says the $textit {multinomial symbol} left(binom {n+1}{k-1}right)$ equals the $textit {binomial symbol} $ $binom {n+k-1}n$ The proof supplied in the article is hard to beat for elegance.
$endgroup$
– lulu
Jan 24 at 20:11
1
$begingroup$
I do not think Wikipedia is as clear as it should be on the stars and bars in theorem two. I would simply say you have $n$ stars and $k-1$ bars to put in any order (e.g. bars are allowed next to each other), so ${n+k-1 choose n}={n+k-1 choose k-1}$ ways of doing this depending on whether you choose the stars' positions first or the bars' positions first.
$endgroup$
– Henry
Jan 24 at 20:11
$begingroup$
@lulu You should not refer to $left(!binom {n}{k}!right)$ as the "multinomial symbol". The multinomial symbol is $binom{n}{n_1,n_2,dots,n_k} = frac{n!}{n_1!,n_2!dotsm n_k!}$. You sometimes hear $left(!binom {n}{k}!right)$ referred to as the multichoose number or the multiset number, of which I think the second is more clear.
$endgroup$
– Misha Lavrov
Jan 24 at 20:16
1
$begingroup$
No problem. At first glance, your formula looks sensible...these things are annoyingly unintuitive.
$endgroup$
– lulu
Jan 24 at 20:43
$begingroup$
If $k=3,n=2$ you get $frac {3^2}2$ which isn't even an integer.
$endgroup$
– lulu
Jan 24 at 20:08
$begingroup$
If $k=3,n=2$ you get $frac {3^2}2$ which isn't even an integer.
$endgroup$
– lulu
Jan 24 at 20:08
1
1
$begingroup$
The article you link to says the $textit {multinomial symbol} left(binom {n+1}{k-1}right)$ equals the $textit {binomial symbol} $ $binom {n+k-1}n$ The proof supplied in the article is hard to beat for elegance.
$endgroup$
– lulu
Jan 24 at 20:11
$begingroup$
The article you link to says the $textit {multinomial symbol} left(binom {n+1}{k-1}right)$ equals the $textit {binomial symbol} $ $binom {n+k-1}n$ The proof supplied in the article is hard to beat for elegance.
$endgroup$
– lulu
Jan 24 at 20:11
1
1
$begingroup$
I do not think Wikipedia is as clear as it should be on the stars and bars in theorem two. I would simply say you have $n$ stars and $k-1$ bars to put in any order (e.g. bars are allowed next to each other), so ${n+k-1 choose n}={n+k-1 choose k-1}$ ways of doing this depending on whether you choose the stars' positions first or the bars' positions first.
$endgroup$
– Henry
Jan 24 at 20:11
$begingroup$
I do not think Wikipedia is as clear as it should be on the stars and bars in theorem two. I would simply say you have $n$ stars and $k-1$ bars to put in any order (e.g. bars are allowed next to each other), so ${n+k-1 choose n}={n+k-1 choose k-1}$ ways of doing this depending on whether you choose the stars' positions first or the bars' positions first.
$endgroup$
– Henry
Jan 24 at 20:11
$begingroup$
@lulu You should not refer to $left(!binom {n}{k}!right)$ as the "multinomial symbol". The multinomial symbol is $binom{n}{n_1,n_2,dots,n_k} = frac{n!}{n_1!,n_2!dotsm n_k!}$. You sometimes hear $left(!binom {n}{k}!right)$ referred to as the multichoose number or the multiset number, of which I think the second is more clear.
$endgroup$
– Misha Lavrov
Jan 24 at 20:16
$begingroup$
@lulu You should not refer to $left(!binom {n}{k}!right)$ as the "multinomial symbol". The multinomial symbol is $binom{n}{n_1,n_2,dots,n_k} = frac{n!}{n_1!,n_2!dotsm n_k!}$. You sometimes hear $left(!binom {n}{k}!right)$ referred to as the multichoose number or the multiset number, of which I think the second is more clear.
$endgroup$
– Misha Lavrov
Jan 24 at 20:16
1
1
$begingroup$
No problem. At first glance, your formula looks sensible...these things are annoyingly unintuitive.
$endgroup$
– lulu
Jan 24 at 20:43
$begingroup$
No problem. At first glance, your formula looks sensible...these things are annoyingly unintuitive.
$endgroup$
– lulu
Jan 24 at 20:43
|
show 4 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Putting $k-1$ bars into $n+1$ gaps, putting $k-1$ balls into $n+1$ bins, and making a list of $n+1$ non-negative integers that sum to $k-1$: these are all equivalent problems, and you can draw a direct link between the solution to one and the solution to another.
But just doing bars in gaps, $(n+1)^{k-1}$ is the number of ways you can put the bars into gaps if it matters which bars are in which gap. You can confirm this with some (very small) test cases, for example write down all the ways $3$ numbered bars go in $2$ numbered gaps and all the ways $2$ numbered bars go in $3$ numbered gaps.
With stars and bars, the bars are a fictitious device in the first place. Draw just one of the possible ways of distributing the bars (with a number on each bar), showing where the stars are too, and see what result (grouping of stars you get). Now renumber the bars and see what groups of stars you get. Do the numbers on the bars make any difference?
So $(n+1)^{k-1}$ is too large. Can you fix this by dividing it by something? There are $(k-1)!$ ways to distribute the numbers when each of the first $k-1$ gaps is occupied by a bar. But there is only one way to put all the bars in the first gap. So you don’t have a nice relationship where every outcome you want to count is represented by exactly $M$ of the outcomes you have.
Faced with a dilemma like that, the best choice is to throw out everything and start over, trying to come up with a different way of attempting the problem.
I don’t even think of stars and bars as a process of “filling gaps.” I think of it as we have two kinds of objects, $k-1$ of one kind and $n$ of another, and I want to put them all in a row from left to right. If I only care what type of object is in each place in the row, there are $binom{n+k-1}{k-1}$ ways to do this. Then I call the first kind of object a bar and the second kind a star and see what grouping of stars I get.
answered Jan 24 at 21:17
David KDavid K
55.1k344120
$endgroup$
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%2f3086288%2fwhy-is-my-solution-to-stars-and-bars-wrong%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$
Putting $k-1$ bars into $n+1$ gaps, putting $k-1$ balls into $n+1$ bins, and making a list of $n+1$ non-negative integers that sum to $k-1$: these are all equivalent problems, and you can draw a direct link between the solution to one and the solution to another.
But just doing bars in gaps, $(n+1)^{k-1}$ is the number of ways you can put the bars into gaps if it matters which bars are in which gap. You can confirm this with some (very small) test cases, for example write down all the ways $3$ numbered bars go in $2$ numbered gaps and all the ways $2$ numbered bars go in $3$ numbered gaps.
With stars and bars, the bars are a fictitious device in the first place. Draw just one of the possible ways of distributing the bars (with a number on each bar), showing where the stars are too, and see what result (grouping of stars you get). Now renumber the bars and see what groups of stars you get. Do the numbers on the bars make any difference?
So $(n+1)^{k-1}$ is too large. Can you fix this by dividing it by something? There are $(k-1)!$ ways to distribute the numbers when each of the first $k-1$ gaps is occupied by a bar. But there is only one way to put all the bars in the first gap. So you don’t have a nice relationship where every outcome you want to count is represented by exactly $M$ of the outcomes you have.
Faced with a dilemma like that, the best choice is to throw out everything and start over, trying to come up with a different way of attempting the problem.
I don’t even think of stars and bars as a process of “filling gaps.” I think of it as we have two kinds of objects, $k-1$ of one kind and $n$ of another, and I want to put them all in a row from left to right. If I only care what type of object is in each place in the row, there are $binom{n+k-1}{k-1}$ ways to do this. Then I call the first kind of object a bar and the second kind a star and see what grouping of stars I get.
answered Jan 24 at 21:17
David KDavid K
55.1k344120
$endgroup$
add a comment |
$begingroup$
Putting $k-1$ bars into $n+1$ gaps, putting $k-1$ balls into $n+1$ bins, and making a list of $n+1$ non-negative integers that sum to $k-1$: these are all equivalent problems, and you can draw a direct link between the solution to one and the solution to another.
But just doing bars in gaps, $(n+1)^{k-1}$ is the number of ways you can put the bars into gaps if it matters which bars are in which gap. You can confirm this with some (very small) test cases, for example write down all the ways $3$ numbered bars go in $2$ numbered gaps and all the ways $2$ numbered bars go in $3$ numbered gaps.
With stars and bars, the bars are a fictitious device in the first place. Draw just one of the possible ways of distributing the bars (with a number on each bar), showing where the stars are too, and see what result (grouping of stars you get). Now renumber the bars and see what groups of stars you get. Do the numbers on the bars make any difference?
So $(n+1)^{k-1}$ is too large. Can you fix this by dividing it by something? There are $(k-1)!$ ways to distribute the numbers when each of the first $k-1$ gaps is occupied by a bar. But there is only one way to put all the bars in the first gap. So you don’t have a nice relationship where every outcome you want to count is represented by exactly $M$ of the outcomes you have.
Faced with a dilemma like that, the best choice is to throw out everything and start over, trying to come up with a different way of attempting the problem.
I don’t even think of stars and bars as a process of “filling gaps.” I think of it as we have two kinds of objects, $k-1$ of one kind and $n$ of another, and I want to put them all in a row from left to right. If I only care what type of object is in each place in the row, there are $binom{n+k-1}{k-1}$ ways to do this. Then I call the first kind of object a bar and the second kind a star and see what grouping of stars I get.
answered Jan 24 at 21:17
David KDavid K
55.1k344120
$endgroup$
add a comment |
$begingroup$
Putting $k-1$ bars into $n+1$ gaps, putting $k-1$ balls into $n+1$ bins, and making a list of $n+1$ non-negative integers that sum to $k-1$: these are all equivalent problems, and you can draw a direct link between the solution to one and the solution to another.
But just doing bars in gaps, $(n+1)^{k-1}$ is the number of ways you can put the bars into gaps if it matters which bars are in which gap. You can confirm this with some (very small) test cases, for example write down all the ways $3$ numbered bars go in $2$ numbered gaps and all the ways $2$ numbered bars go in $3$ numbered gaps.
With stars and bars, the bars are a fictitious device in the first place. Draw just one of the possible ways of distributing the bars (with a number on each bar), showing where the stars are too, and see what result (grouping of stars you get). Now renumber the bars and see what groups of stars you get. Do the numbers on the bars make any difference?
So $(n+1)^{k-1}$ is too large. Can you fix this by dividing it by something? There are $(k-1)!$ ways to distribute the numbers when each of the first $k-1$ gaps is occupied by a bar. But there is only one way to put all the bars in the first gap. So you don’t have a nice relationship where every outcome you want to count is represented by exactly $M$ of the outcomes you have.
Faced with a dilemma like that, the best choice is to throw out everything and start over, trying to come up with a different way of attempting the problem.
I don’t even think of stars and bars as a process of “filling gaps.” I think of it as we have two kinds of objects, $k-1$ of one kind and $n$ of another, and I want to put them all in a row from left to right. If I only care what type of object is in each place in the row, there are $binom{n+k-1}{k-1}$ ways to do this. Then I call the first kind of object a bar and the second kind a star and see what grouping of stars I get.
answered Jan 24 at 21:17
David KDavid K
55.1k344120
$endgroup$
Putting $k-1$ bars into $n+1$ gaps, putting $k-1$ balls into $n+1$ bins, and making a list of $n+1$ non-negative integers that sum to $k-1$: these are all equivalent problems, and you can draw a direct link between the solution to one and the solution to another.
But just doing bars in gaps, $(n+1)^{k-1}$ is the number of ways you can put the bars into gaps if it matters which bars are in which gap. You can confirm this with some (very small) test cases, for example write down all the ways $3$ numbered bars go in $2$ numbered gaps and all the ways $2$ numbered bars go in $3$ numbered gaps.
With stars and bars, the bars are a fictitious device in the first place. Draw just one of the possible ways of distributing the bars (with a number on each bar), showing where the stars are too, and see what result (grouping of stars you get). Now renumber the bars and see what groups of stars you get. Do the numbers on the bars make any difference?
So $(n+1)^{k-1}$ is too large. Can you fix this by dividing it by something? There are $(k-1)!$ ways to distribute the numbers when each of the first $k-1$ gaps is occupied by a bar. But there is only one way to put all the bars in the first gap. So you don’t have a nice relationship where every outcome you want to count is represented by exactly $M$ of the outcomes you have.
Faced with a dilemma like that, the best choice is to throw out everything and start over, trying to come up with a different way of attempting the problem.
I don’t even think of stars and bars as a process of “filling gaps.” I think of it as we have two kinds of objects, $k-1$ of one kind and $n$ of another, and I want to put them all in a row from left to right. If I only care what type of object is in each place in the row, there are $binom{n+k-1}{k-1}$ ways to do this. Then I call the first kind of object a bar and the second kind a star and see what grouping of stars I get.
answered Jan 24 at 21:17
David KDavid K
55.1k344120
answered Jan 24 at 21:17
David KDavid K
55.1k344120
answered Jan 24 at 21:17
David KDavid K
55.1k344120
answered Jan 24 at 21:17
David KDavid K
55.1k344120
55.1k344120
add a comment |
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%2f3086288%2fwhy-is-my-solution-to-stars-and-bars-wrong%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
$begingroup$
If $k=3,n=2$ you get $frac {3^2}2$ which isn't even an integer.
$endgroup$
– lulu
Jan 24 at 20:08
1
$begingroup$
The article you link to says the $textit {multinomial symbol} left(binom {n+1}{k-1}right)$ equals the $textit {binomial symbol} $ $binom {n+k-1}n$ The proof supplied in the article is hard to beat for elegance.
$endgroup$
– lulu
Jan 24 at 20:11
1
$begingroup$
I do not think Wikipedia is as clear as it should be on the stars and bars in theorem two. I would simply say you have $n$ stars and $k-1$ bars to put in any order (e.g. bars are allowed next to each other), so ${n+k-1 choose n}={n+k-1 choose k-1}$ ways of doing this depending on whether you choose the stars' positions first or the bars' positions first.
$endgroup$
– Henry
Jan 24 at 20:11
$begingroup$
@lulu You should not refer to $left(!binom {n}{k}!right)$ as the "multinomial symbol". The multinomial symbol is $binom{n}{n_1,n_2,dots,n_k} = frac{n!}{n_1!,n_2!dotsm n_k!}$. You sometimes hear $left(!binom {n}{k}!right)$ referred to as the multichoose number or the multiset number, of which I think the second is more clear.
$endgroup$
– Misha Lavrov
Jan 24 at 20:16
1
$begingroup$
No problem. At first glance, your formula looks sensible...these things are annoyingly unintuitive.
$endgroup$
– lulu
Jan 24 at 20:43