Applying Burnside's lemma to show there are $k+n-1 choose k-1$ ways to store n stars in k bins?











up vote
1
down vote

favorite
3












Usually it is proven using multisets I think, but I wondered how Burnside's lemma could be applied. Everytime I tried to wrap it around my head the indices didn't seem to fit. So I TeXed it and eventually I found out.










share|cite|improve this question




















  • 1




    Stars and Bars is the usual way that I see this shown.
    – robjohn
    Nov 17 at 16:59










  • The wikipedia-proof is taking advantage of Multisets if it were to be formalised, isn't it?
    – Martin Erhardt
    Nov 17 at 19:56










  • It is counting the number of ways to arrange $n$ stars and $k-1$ bars among each other.
    – robjohn
    Nov 17 at 20:08















up vote
1
down vote

favorite
3












Usually it is proven using multisets I think, but I wondered how Burnside's lemma could be applied. Everytime I tried to wrap it around my head the indices didn't seem to fit. So I TeXed it and eventually I found out.










share|cite|improve this question




















  • 1




    Stars and Bars is the usual way that I see this shown.
    – robjohn
    Nov 17 at 16:59










  • The wikipedia-proof is taking advantage of Multisets if it were to be formalised, isn't it?
    – Martin Erhardt
    Nov 17 at 19:56










  • It is counting the number of ways to arrange $n$ stars and $k-1$ bars among each other.
    – robjohn
    Nov 17 at 20:08













up vote
1
down vote

favorite
3









up vote
1
down vote

favorite
3






3





Usually it is proven using multisets I think, but I wondered how Burnside's lemma could be applied. Everytime I tried to wrap it around my head the indices didn't seem to fit. So I TeXed it and eventually I found out.










share|cite|improve this question















Usually it is proven using multisets I think, but I wondered how Burnside's lemma could be applied. Everytime I tried to wrap it around my head the indices didn't seem to fit. So I TeXed it and eventually I found out.







combinatorics group-actions algebraic-combinatorics






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 17 at 18:11

























asked Nov 17 at 16:23









Martin Erhardt

1859




1859








  • 1




    Stars and Bars is the usual way that I see this shown.
    – robjohn
    Nov 17 at 16:59










  • The wikipedia-proof is taking advantage of Multisets if it were to be formalised, isn't it?
    – Martin Erhardt
    Nov 17 at 19:56










  • It is counting the number of ways to arrange $n$ stars and $k-1$ bars among each other.
    – robjohn
    Nov 17 at 20:08














  • 1




    Stars and Bars is the usual way that I see this shown.
    – robjohn
    Nov 17 at 16:59










  • The wikipedia-proof is taking advantage of Multisets if it were to be formalised, isn't it?
    – Martin Erhardt
    Nov 17 at 19:56










  • It is counting the number of ways to arrange $n$ stars and $k-1$ bars among each other.
    – robjohn
    Nov 17 at 20:08








1




1




Stars and Bars is the usual way that I see this shown.
– robjohn
Nov 17 at 16:59




Stars and Bars is the usual way that I see this shown.
– robjohn
Nov 17 at 16:59












The wikipedia-proof is taking advantage of Multisets if it were to be formalised, isn't it?
– Martin Erhardt
Nov 17 at 19:56




The wikipedia-proof is taking advantage of Multisets if it were to be formalised, isn't it?
– Martin Erhardt
Nov 17 at 19:56












It is counting the number of ways to arrange $n$ stars and $k-1$ bars among each other.
– robjohn
Nov 17 at 20:08




It is counting the number of ways to arrange $n$ stars and $k-1$ bars among each other.
– robjohn
Nov 17 at 20:08










2 Answers
2






active

oldest

votes

















up vote
1
down vote













The $k$ bins can all be distinguished, so we're dealing with the trivial group whose one element is the identity permutation over $k$ elements.



Thus the cycle index is $Z = t_1^k$. There's one way of putting one star in a bin, one way of putting two stars, etc. so the final generating function is $f(z) = left(frac{1}{1-z}right)^k = (1-z)^{-k}$. Then the term with $z^n$ is $frac{(-k)^{underline n}}{n!}(-z)^n$ with coefficient $$frac{(-k)^{underline n}}{n!}(-1)^n = frac{(k+n-1)^{underline n}}{n!} = binom{k+n-1}{n}$$





Note that this is also $binom{k+n-1}{k-1}$, so maybe the reason the indexes always came out wrong for you is that you were trying to prove a statement with an out-by-one error.






share|cite|improve this answer





















  • Could you please elaborate on the set you are operating on and how? Operating with a cyclic group is obviously way more elegant, than with the Symmetric group -even though you do not seem to use burnside's lemma.
    – Martin Erhardt
    Nov 17 at 18:30








  • 1




    Strictly I'm using Pólya's enumeration theorem, which is a generalisation of not-Burnside's lemma. $G$ contains only the identity element of $S_k$, so the sum is trivial.
    – Peter Taylor
    Nov 17 at 18:55










  • I'am reliefed to see, that I could not have come up with that with my limited knowledge :). I wonder: Would it be possible to stay that short, without this strong theorem?
    – Martin Erhardt
    Nov 17 at 19:11








  • 1




    qchu.wordpress.com/2009/06/16/… might achieve that, although I personally could use an extra step or two of explanation. (The next two posts in the series may also interest you).
    – Peter Taylor
    Nov 18 at 8:48


















up vote
1
down vote













EDIT: Substitute n=k, k=n. This proof follows the urn model -intuition.



Let $|N|=n$, $M=N^{k}/sim$ and:
$$x,yin N^k, x sim yLeftrightarrowexists sigma in S^k: (x_1,...,x_k)=(y_{sigma(1)},...,y_{sigma(k)})$$
Obviously M is the orbital space of a group action: $sigma.(x_1,...,x_k)=(x_{sigma(1)},...,x_{sigma(k)})$.



To proof: $|N^k/sim|={k+n -1choose k}$



Induction by k:



Trivially: $$|N^1/sim|overset{Burnside}=frac{sum_{sigmain S^1}|N|^1}{1!}=|N|=n={1+n-1choose 1}$$



$k-1 rightarrow k:$



Each $sigma$ in $S^{k-1}$ can be naturally identified by $sigma'in S^k$ $$sigma'(h)=left{begin{array}{cl} sigma(h), & hleq k-1\ k, & h=k end{array}right.$$
$$ forall h in {1,...,k}:omega_h:S^{k-1}rightarrow { sigma'' in S^k:sigma''(h)=k},sigmamapsto (sigma'(h), k) circ sigma' $$
$(sigma(h) k)$ is the transposition, that swaps $sigma(h)$ with k. $omega_h$
is bijective(trivially injective, surjective with inverse $sigma mapsto ((sigma(h),sigma(k))sigma)|_{{1,...,k-1}}$, which is well defined, because $sigma(h)=k$ and $sigma(k) in {1,..k-1}$ for $hneq k$)



Let $F_k$ be: $S^k rightarrow N^k, F_k(sigma)={x in N^k: sigma(x)=x}$



$$|N^k/sim|=frac{sum_{sigmain S^k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|+sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}$$



Moreover:
$$F_k(omega_k(sigma))=F_{k-1}(sigma)times N Rightarrow |F_{k}(omega_k(sigma))|=|F_{k-1}(sigma)|n$$



Bijectivity of transposition leads to: $x in F_k(omega_h(sigma)) Rightarrow (x_1,...,x_{k-1})in F_{k-1}(sigma)$.
For each $hin {1,...,k-1}$ and $xin F_{k-1}(sigma)$ the k-th compononent is uniquely determined, by $x_{omega_h(sigma(k))}$.Since $omega_h(sigma(k))=sigma(h)$ and $x_{(omega_h circ sigma)^{-1}(k)}=x_h=x_{sigma(h)}=x_{omega_h(sigma(k))}=x_k$, $(x,x_{omega_h(sigma(k))})$ is actually in $F_k(omega_h(sigma))$. It follows, that:
$$F_k(omega_h(sigma))={(x,x_{omega_h(sigma(k))}) : x in F_{k-1}(sigma)} Rightarrow |F_{k}(omega_h(sigma(k)))|=|F_{k-1}(sigma)|$$



This yields: $$frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k-1}}|F_{k-1}(omega_k(sigma))|n}{k!}$$
$$overset{IH}{=}frac{n(k-1)!{k+n-2 choose k-1}}{k!}=frac{n-1}{k}{k+n-2 choose k-1}+frac{1}{k}{k+n-2 choose k-1}$$$$={k+n-2 choose k}+frac{1}{k}{k+n-2 choose k-1}$$
Now we are taking a closer look at the latter guys $forall h in{1,..k-1}:$
$$frac{sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)= i, i=1}^{k-1}|F_k(sigma)|}{k!}=frac{sum_{i=1}^{k-1}sum_{sigmain S^{k-1}}|F_{k-1}(omega_i(sigma))|}{k!}$$



$$overset{IH}{=}frac{sum_{i=1}^{k-1}(k-1)!{k+n-2 choose k-1}}{k!}=frac{k-1}{k}{k+n-2 choose k-1 }$$
We conclude:
$$|N^k/sim|=frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}+frac{sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}$$
$$={k+n-2 choose k}+frac{1}{k}{k+n-2 choose k-1}+
frac{k-1}{k}{k+n-2 choose k-1 }$$

$$={k+n-2 choose k}+{k+n-2 choose k-1 }={k+n-1 choose k}$$






share|cite|improve this answer



















  • 1




    The base case of the induction is wrong. Trivially, if you only have one bin there's only one way to store the stars.
    – Peter Taylor
    Nov 17 at 17:45










  • Oh I thought about pulling n balls out of an urn k - times neglecting sequence with replacement. This is dual in a way to the stars-bins-approach.
    – Martin Erhardt
    Nov 17 at 18:09










  • So the proof is actually correct, but I confused two different models of the same problem.
    – Martin Erhardt
    Nov 17 at 18:13











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',
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%2f3002539%2fapplying-burnsides-lemma-to-show-there-are-kn-1-choose-k-1-ways-to-store-n%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
1
down vote













The $k$ bins can all be distinguished, so we're dealing with the trivial group whose one element is the identity permutation over $k$ elements.



Thus the cycle index is $Z = t_1^k$. There's one way of putting one star in a bin, one way of putting two stars, etc. so the final generating function is $f(z) = left(frac{1}{1-z}right)^k = (1-z)^{-k}$. Then the term with $z^n$ is $frac{(-k)^{underline n}}{n!}(-z)^n$ with coefficient $$frac{(-k)^{underline n}}{n!}(-1)^n = frac{(k+n-1)^{underline n}}{n!} = binom{k+n-1}{n}$$





Note that this is also $binom{k+n-1}{k-1}$, so maybe the reason the indexes always came out wrong for you is that you were trying to prove a statement with an out-by-one error.






share|cite|improve this answer





















  • Could you please elaborate on the set you are operating on and how? Operating with a cyclic group is obviously way more elegant, than with the Symmetric group -even though you do not seem to use burnside's lemma.
    – Martin Erhardt
    Nov 17 at 18:30








  • 1




    Strictly I'm using Pólya's enumeration theorem, which is a generalisation of not-Burnside's lemma. $G$ contains only the identity element of $S_k$, so the sum is trivial.
    – Peter Taylor
    Nov 17 at 18:55










  • I'am reliefed to see, that I could not have come up with that with my limited knowledge :). I wonder: Would it be possible to stay that short, without this strong theorem?
    – Martin Erhardt
    Nov 17 at 19:11








  • 1




    qchu.wordpress.com/2009/06/16/… might achieve that, although I personally could use an extra step or two of explanation. (The next two posts in the series may also interest you).
    – Peter Taylor
    Nov 18 at 8:48















up vote
1
down vote













The $k$ bins can all be distinguished, so we're dealing with the trivial group whose one element is the identity permutation over $k$ elements.



Thus the cycle index is $Z = t_1^k$. There's one way of putting one star in a bin, one way of putting two stars, etc. so the final generating function is $f(z) = left(frac{1}{1-z}right)^k = (1-z)^{-k}$. Then the term with $z^n$ is $frac{(-k)^{underline n}}{n!}(-z)^n$ with coefficient $$frac{(-k)^{underline n}}{n!}(-1)^n = frac{(k+n-1)^{underline n}}{n!} = binom{k+n-1}{n}$$





Note that this is also $binom{k+n-1}{k-1}$, so maybe the reason the indexes always came out wrong for you is that you were trying to prove a statement with an out-by-one error.






share|cite|improve this answer





















  • Could you please elaborate on the set you are operating on and how? Operating with a cyclic group is obviously way more elegant, than with the Symmetric group -even though you do not seem to use burnside's lemma.
    – Martin Erhardt
    Nov 17 at 18:30








  • 1




    Strictly I'm using Pólya's enumeration theorem, which is a generalisation of not-Burnside's lemma. $G$ contains only the identity element of $S_k$, so the sum is trivial.
    – Peter Taylor
    Nov 17 at 18:55










  • I'am reliefed to see, that I could not have come up with that with my limited knowledge :). I wonder: Would it be possible to stay that short, without this strong theorem?
    – Martin Erhardt
    Nov 17 at 19:11








  • 1




    qchu.wordpress.com/2009/06/16/… might achieve that, although I personally could use an extra step or two of explanation. (The next two posts in the series may also interest you).
    – Peter Taylor
    Nov 18 at 8:48













up vote
1
down vote










up vote
1
down vote









The $k$ bins can all be distinguished, so we're dealing with the trivial group whose one element is the identity permutation over $k$ elements.



Thus the cycle index is $Z = t_1^k$. There's one way of putting one star in a bin, one way of putting two stars, etc. so the final generating function is $f(z) = left(frac{1}{1-z}right)^k = (1-z)^{-k}$. Then the term with $z^n$ is $frac{(-k)^{underline n}}{n!}(-z)^n$ with coefficient $$frac{(-k)^{underline n}}{n!}(-1)^n = frac{(k+n-1)^{underline n}}{n!} = binom{k+n-1}{n}$$





Note that this is also $binom{k+n-1}{k-1}$, so maybe the reason the indexes always came out wrong for you is that you were trying to prove a statement with an out-by-one error.






share|cite|improve this answer












The $k$ bins can all be distinguished, so we're dealing with the trivial group whose one element is the identity permutation over $k$ elements.



Thus the cycle index is $Z = t_1^k$. There's one way of putting one star in a bin, one way of putting two stars, etc. so the final generating function is $f(z) = left(frac{1}{1-z}right)^k = (1-z)^{-k}$. Then the term with $z^n$ is $frac{(-k)^{underline n}}{n!}(-z)^n$ with coefficient $$frac{(-k)^{underline n}}{n!}(-1)^n = frac{(k+n-1)^{underline n}}{n!} = binom{k+n-1}{n}$$





Note that this is also $binom{k+n-1}{k-1}$, so maybe the reason the indexes always came out wrong for you is that you were trying to prove a statement with an out-by-one error.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Nov 17 at 17:43









Peter Taylor

8,35212240




8,35212240












  • Could you please elaborate on the set you are operating on and how? Operating with a cyclic group is obviously way more elegant, than with the Symmetric group -even though you do not seem to use burnside's lemma.
    – Martin Erhardt
    Nov 17 at 18:30








  • 1




    Strictly I'm using Pólya's enumeration theorem, which is a generalisation of not-Burnside's lemma. $G$ contains only the identity element of $S_k$, so the sum is trivial.
    – Peter Taylor
    Nov 17 at 18:55










  • I'am reliefed to see, that I could not have come up with that with my limited knowledge :). I wonder: Would it be possible to stay that short, without this strong theorem?
    – Martin Erhardt
    Nov 17 at 19:11








  • 1




    qchu.wordpress.com/2009/06/16/… might achieve that, although I personally could use an extra step or two of explanation. (The next two posts in the series may also interest you).
    – Peter Taylor
    Nov 18 at 8:48


















  • Could you please elaborate on the set you are operating on and how? Operating with a cyclic group is obviously way more elegant, than with the Symmetric group -even though you do not seem to use burnside's lemma.
    – Martin Erhardt
    Nov 17 at 18:30








  • 1




    Strictly I'm using Pólya's enumeration theorem, which is a generalisation of not-Burnside's lemma. $G$ contains only the identity element of $S_k$, so the sum is trivial.
    – Peter Taylor
    Nov 17 at 18:55










  • I'am reliefed to see, that I could not have come up with that with my limited knowledge :). I wonder: Would it be possible to stay that short, without this strong theorem?
    – Martin Erhardt
    Nov 17 at 19:11








  • 1




    qchu.wordpress.com/2009/06/16/… might achieve that, although I personally could use an extra step or two of explanation. (The next two posts in the series may also interest you).
    – Peter Taylor
    Nov 18 at 8:48
















Could you please elaborate on the set you are operating on and how? Operating with a cyclic group is obviously way more elegant, than with the Symmetric group -even though you do not seem to use burnside's lemma.
– Martin Erhardt
Nov 17 at 18:30






Could you please elaborate on the set you are operating on and how? Operating with a cyclic group is obviously way more elegant, than with the Symmetric group -even though you do not seem to use burnside's lemma.
– Martin Erhardt
Nov 17 at 18:30






1




1




Strictly I'm using Pólya's enumeration theorem, which is a generalisation of not-Burnside's lemma. $G$ contains only the identity element of $S_k$, so the sum is trivial.
– Peter Taylor
Nov 17 at 18:55




Strictly I'm using Pólya's enumeration theorem, which is a generalisation of not-Burnside's lemma. $G$ contains only the identity element of $S_k$, so the sum is trivial.
– Peter Taylor
Nov 17 at 18:55












I'am reliefed to see, that I could not have come up with that with my limited knowledge :). I wonder: Would it be possible to stay that short, without this strong theorem?
– Martin Erhardt
Nov 17 at 19:11






I'am reliefed to see, that I could not have come up with that with my limited knowledge :). I wonder: Would it be possible to stay that short, without this strong theorem?
– Martin Erhardt
Nov 17 at 19:11






1




1




qchu.wordpress.com/2009/06/16/… might achieve that, although I personally could use an extra step or two of explanation. (The next two posts in the series may also interest you).
– Peter Taylor
Nov 18 at 8:48




qchu.wordpress.com/2009/06/16/… might achieve that, although I personally could use an extra step or two of explanation. (The next two posts in the series may also interest you).
– Peter Taylor
Nov 18 at 8:48










up vote
1
down vote













EDIT: Substitute n=k, k=n. This proof follows the urn model -intuition.



Let $|N|=n$, $M=N^{k}/sim$ and:
$$x,yin N^k, x sim yLeftrightarrowexists sigma in S^k: (x_1,...,x_k)=(y_{sigma(1)},...,y_{sigma(k)})$$
Obviously M is the orbital space of a group action: $sigma.(x_1,...,x_k)=(x_{sigma(1)},...,x_{sigma(k)})$.



To proof: $|N^k/sim|={k+n -1choose k}$



Induction by k:



Trivially: $$|N^1/sim|overset{Burnside}=frac{sum_{sigmain S^1}|N|^1}{1!}=|N|=n={1+n-1choose 1}$$



$k-1 rightarrow k:$



Each $sigma$ in $S^{k-1}$ can be naturally identified by $sigma'in S^k$ $$sigma'(h)=left{begin{array}{cl} sigma(h), & hleq k-1\ k, & h=k end{array}right.$$
$$ forall h in {1,...,k}:omega_h:S^{k-1}rightarrow { sigma'' in S^k:sigma''(h)=k},sigmamapsto (sigma'(h), k) circ sigma' $$
$(sigma(h) k)$ is the transposition, that swaps $sigma(h)$ with k. $omega_h$
is bijective(trivially injective, surjective with inverse $sigma mapsto ((sigma(h),sigma(k))sigma)|_{{1,...,k-1}}$, which is well defined, because $sigma(h)=k$ and $sigma(k) in {1,..k-1}$ for $hneq k$)



Let $F_k$ be: $S^k rightarrow N^k, F_k(sigma)={x in N^k: sigma(x)=x}$



$$|N^k/sim|=frac{sum_{sigmain S^k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|+sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}$$



Moreover:
$$F_k(omega_k(sigma))=F_{k-1}(sigma)times N Rightarrow |F_{k}(omega_k(sigma))|=|F_{k-1}(sigma)|n$$



Bijectivity of transposition leads to: $x in F_k(omega_h(sigma)) Rightarrow (x_1,...,x_{k-1})in F_{k-1}(sigma)$.
For each $hin {1,...,k-1}$ and $xin F_{k-1}(sigma)$ the k-th compononent is uniquely determined, by $x_{omega_h(sigma(k))}$.Since $omega_h(sigma(k))=sigma(h)$ and $x_{(omega_h circ sigma)^{-1}(k)}=x_h=x_{sigma(h)}=x_{omega_h(sigma(k))}=x_k$, $(x,x_{omega_h(sigma(k))})$ is actually in $F_k(omega_h(sigma))$. It follows, that:
$$F_k(omega_h(sigma))={(x,x_{omega_h(sigma(k))}) : x in F_{k-1}(sigma)} Rightarrow |F_{k}(omega_h(sigma(k)))|=|F_{k-1}(sigma)|$$



This yields: $$frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k-1}}|F_{k-1}(omega_k(sigma))|n}{k!}$$
$$overset{IH}{=}frac{n(k-1)!{k+n-2 choose k-1}}{k!}=frac{n-1}{k}{k+n-2 choose k-1}+frac{1}{k}{k+n-2 choose k-1}$$$$={k+n-2 choose k}+frac{1}{k}{k+n-2 choose k-1}$$
Now we are taking a closer look at the latter guys $forall h in{1,..k-1}:$
$$frac{sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)= i, i=1}^{k-1}|F_k(sigma)|}{k!}=frac{sum_{i=1}^{k-1}sum_{sigmain S^{k-1}}|F_{k-1}(omega_i(sigma))|}{k!}$$



$$overset{IH}{=}frac{sum_{i=1}^{k-1}(k-1)!{k+n-2 choose k-1}}{k!}=frac{k-1}{k}{k+n-2 choose k-1 }$$
We conclude:
$$|N^k/sim|=frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}+frac{sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}$$
$$={k+n-2 choose k}+frac{1}{k}{k+n-2 choose k-1}+
frac{k-1}{k}{k+n-2 choose k-1 }$$

$$={k+n-2 choose k}+{k+n-2 choose k-1 }={k+n-1 choose k}$$






share|cite|improve this answer



















  • 1




    The base case of the induction is wrong. Trivially, if you only have one bin there's only one way to store the stars.
    – Peter Taylor
    Nov 17 at 17:45










  • Oh I thought about pulling n balls out of an urn k - times neglecting sequence with replacement. This is dual in a way to the stars-bins-approach.
    – Martin Erhardt
    Nov 17 at 18:09










  • So the proof is actually correct, but I confused two different models of the same problem.
    – Martin Erhardt
    Nov 17 at 18:13















up vote
1
down vote













EDIT: Substitute n=k, k=n. This proof follows the urn model -intuition.



Let $|N|=n$, $M=N^{k}/sim$ and:
$$x,yin N^k, x sim yLeftrightarrowexists sigma in S^k: (x_1,...,x_k)=(y_{sigma(1)},...,y_{sigma(k)})$$
Obviously M is the orbital space of a group action: $sigma.(x_1,...,x_k)=(x_{sigma(1)},...,x_{sigma(k)})$.



To proof: $|N^k/sim|={k+n -1choose k}$



Induction by k:



Trivially: $$|N^1/sim|overset{Burnside}=frac{sum_{sigmain S^1}|N|^1}{1!}=|N|=n={1+n-1choose 1}$$



$k-1 rightarrow k:$



Each $sigma$ in $S^{k-1}$ can be naturally identified by $sigma'in S^k$ $$sigma'(h)=left{begin{array}{cl} sigma(h), & hleq k-1\ k, & h=k end{array}right.$$
$$ forall h in {1,...,k}:omega_h:S^{k-1}rightarrow { sigma'' in S^k:sigma''(h)=k},sigmamapsto (sigma'(h), k) circ sigma' $$
$(sigma(h) k)$ is the transposition, that swaps $sigma(h)$ with k. $omega_h$
is bijective(trivially injective, surjective with inverse $sigma mapsto ((sigma(h),sigma(k))sigma)|_{{1,...,k-1}}$, which is well defined, because $sigma(h)=k$ and $sigma(k) in {1,..k-1}$ for $hneq k$)



Let $F_k$ be: $S^k rightarrow N^k, F_k(sigma)={x in N^k: sigma(x)=x}$



$$|N^k/sim|=frac{sum_{sigmain S^k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|+sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}$$



Moreover:
$$F_k(omega_k(sigma))=F_{k-1}(sigma)times N Rightarrow |F_{k}(omega_k(sigma))|=|F_{k-1}(sigma)|n$$



Bijectivity of transposition leads to: $x in F_k(omega_h(sigma)) Rightarrow (x_1,...,x_{k-1})in F_{k-1}(sigma)$.
For each $hin {1,...,k-1}$ and $xin F_{k-1}(sigma)$ the k-th compononent is uniquely determined, by $x_{omega_h(sigma(k))}$.Since $omega_h(sigma(k))=sigma(h)$ and $x_{(omega_h circ sigma)^{-1}(k)}=x_h=x_{sigma(h)}=x_{omega_h(sigma(k))}=x_k$, $(x,x_{omega_h(sigma(k))})$ is actually in $F_k(omega_h(sigma))$. It follows, that:
$$F_k(omega_h(sigma))={(x,x_{omega_h(sigma(k))}) : x in F_{k-1}(sigma)} Rightarrow |F_{k}(omega_h(sigma(k)))|=|F_{k-1}(sigma)|$$



This yields: $$frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k-1}}|F_{k-1}(omega_k(sigma))|n}{k!}$$
$$overset{IH}{=}frac{n(k-1)!{k+n-2 choose k-1}}{k!}=frac{n-1}{k}{k+n-2 choose k-1}+frac{1}{k}{k+n-2 choose k-1}$$$$={k+n-2 choose k}+frac{1}{k}{k+n-2 choose k-1}$$
Now we are taking a closer look at the latter guys $forall h in{1,..k-1}:$
$$frac{sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)= i, i=1}^{k-1}|F_k(sigma)|}{k!}=frac{sum_{i=1}^{k-1}sum_{sigmain S^{k-1}}|F_{k-1}(omega_i(sigma))|}{k!}$$



$$overset{IH}{=}frac{sum_{i=1}^{k-1}(k-1)!{k+n-2 choose k-1}}{k!}=frac{k-1}{k}{k+n-2 choose k-1 }$$
We conclude:
$$|N^k/sim|=frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}+frac{sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}$$
$$={k+n-2 choose k}+frac{1}{k}{k+n-2 choose k-1}+
frac{k-1}{k}{k+n-2 choose k-1 }$$

$$={k+n-2 choose k}+{k+n-2 choose k-1 }={k+n-1 choose k}$$






share|cite|improve this answer



















  • 1




    The base case of the induction is wrong. Trivially, if you only have one bin there's only one way to store the stars.
    – Peter Taylor
    Nov 17 at 17:45










  • Oh I thought about pulling n balls out of an urn k - times neglecting sequence with replacement. This is dual in a way to the stars-bins-approach.
    – Martin Erhardt
    Nov 17 at 18:09










  • So the proof is actually correct, but I confused two different models of the same problem.
    – Martin Erhardt
    Nov 17 at 18:13













up vote
1
down vote










up vote
1
down vote









EDIT: Substitute n=k, k=n. This proof follows the urn model -intuition.



Let $|N|=n$, $M=N^{k}/sim$ and:
$$x,yin N^k, x sim yLeftrightarrowexists sigma in S^k: (x_1,...,x_k)=(y_{sigma(1)},...,y_{sigma(k)})$$
Obviously M is the orbital space of a group action: $sigma.(x_1,...,x_k)=(x_{sigma(1)},...,x_{sigma(k)})$.



To proof: $|N^k/sim|={k+n -1choose k}$



Induction by k:



Trivially: $$|N^1/sim|overset{Burnside}=frac{sum_{sigmain S^1}|N|^1}{1!}=|N|=n={1+n-1choose 1}$$



$k-1 rightarrow k:$



Each $sigma$ in $S^{k-1}$ can be naturally identified by $sigma'in S^k$ $$sigma'(h)=left{begin{array}{cl} sigma(h), & hleq k-1\ k, & h=k end{array}right.$$
$$ forall h in {1,...,k}:omega_h:S^{k-1}rightarrow { sigma'' in S^k:sigma''(h)=k},sigmamapsto (sigma'(h), k) circ sigma' $$
$(sigma(h) k)$ is the transposition, that swaps $sigma(h)$ with k. $omega_h$
is bijective(trivially injective, surjective with inverse $sigma mapsto ((sigma(h),sigma(k))sigma)|_{{1,...,k-1}}$, which is well defined, because $sigma(h)=k$ and $sigma(k) in {1,..k-1}$ for $hneq k$)



Let $F_k$ be: $S^k rightarrow N^k, F_k(sigma)={x in N^k: sigma(x)=x}$



$$|N^k/sim|=frac{sum_{sigmain S^k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|+sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}$$



Moreover:
$$F_k(omega_k(sigma))=F_{k-1}(sigma)times N Rightarrow |F_{k}(omega_k(sigma))|=|F_{k-1}(sigma)|n$$



Bijectivity of transposition leads to: $x in F_k(omega_h(sigma)) Rightarrow (x_1,...,x_{k-1})in F_{k-1}(sigma)$.
For each $hin {1,...,k-1}$ and $xin F_{k-1}(sigma)$ the k-th compononent is uniquely determined, by $x_{omega_h(sigma(k))}$.Since $omega_h(sigma(k))=sigma(h)$ and $x_{(omega_h circ sigma)^{-1}(k)}=x_h=x_{sigma(h)}=x_{omega_h(sigma(k))}=x_k$, $(x,x_{omega_h(sigma(k))})$ is actually in $F_k(omega_h(sigma))$. It follows, that:
$$F_k(omega_h(sigma))={(x,x_{omega_h(sigma(k))}) : x in F_{k-1}(sigma)} Rightarrow |F_{k}(omega_h(sigma(k)))|=|F_{k-1}(sigma)|$$



This yields: $$frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k-1}}|F_{k-1}(omega_k(sigma))|n}{k!}$$
$$overset{IH}{=}frac{n(k-1)!{k+n-2 choose k-1}}{k!}=frac{n-1}{k}{k+n-2 choose k-1}+frac{1}{k}{k+n-2 choose k-1}$$$$={k+n-2 choose k}+frac{1}{k}{k+n-2 choose k-1}$$
Now we are taking a closer look at the latter guys $forall h in{1,..k-1}:$
$$frac{sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)= i, i=1}^{k-1}|F_k(sigma)|}{k!}=frac{sum_{i=1}^{k-1}sum_{sigmain S^{k-1}}|F_{k-1}(omega_i(sigma))|}{k!}$$



$$overset{IH}{=}frac{sum_{i=1}^{k-1}(k-1)!{k+n-2 choose k-1}}{k!}=frac{k-1}{k}{k+n-2 choose k-1 }$$
We conclude:
$$|N^k/sim|=frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}+frac{sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}$$
$$={k+n-2 choose k}+frac{1}{k}{k+n-2 choose k-1}+
frac{k-1}{k}{k+n-2 choose k-1 }$$

$$={k+n-2 choose k}+{k+n-2 choose k-1 }={k+n-1 choose k}$$






share|cite|improve this answer














EDIT: Substitute n=k, k=n. This proof follows the urn model -intuition.



Let $|N|=n$, $M=N^{k}/sim$ and:
$$x,yin N^k, x sim yLeftrightarrowexists sigma in S^k: (x_1,...,x_k)=(y_{sigma(1)},...,y_{sigma(k)})$$
Obviously M is the orbital space of a group action: $sigma.(x_1,...,x_k)=(x_{sigma(1)},...,x_{sigma(k)})$.



To proof: $|N^k/sim|={k+n -1choose k}$



Induction by k:



Trivially: $$|N^1/sim|overset{Burnside}=frac{sum_{sigmain S^1}|N|^1}{1!}=|N|=n={1+n-1choose 1}$$



$k-1 rightarrow k:$



Each $sigma$ in $S^{k-1}$ can be naturally identified by $sigma'in S^k$ $$sigma'(h)=left{begin{array}{cl} sigma(h), & hleq k-1\ k, & h=k end{array}right.$$
$$ forall h in {1,...,k}:omega_h:S^{k-1}rightarrow { sigma'' in S^k:sigma''(h)=k},sigmamapsto (sigma'(h), k) circ sigma' $$
$(sigma(h) k)$ is the transposition, that swaps $sigma(h)$ with k. $omega_h$
is bijective(trivially injective, surjective with inverse $sigma mapsto ((sigma(h),sigma(k))sigma)|_{{1,...,k-1}}$, which is well defined, because $sigma(h)=k$ and $sigma(k) in {1,..k-1}$ for $hneq k$)



Let $F_k$ be: $S^k rightarrow N^k, F_k(sigma)={x in N^k: sigma(x)=x}$



$$|N^k/sim|=frac{sum_{sigmain S^k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|+sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}$$



Moreover:
$$F_k(omega_k(sigma))=F_{k-1}(sigma)times N Rightarrow |F_{k}(omega_k(sigma))|=|F_{k-1}(sigma)|n$$



Bijectivity of transposition leads to: $x in F_k(omega_h(sigma)) Rightarrow (x_1,...,x_{k-1})in F_{k-1}(sigma)$.
For each $hin {1,...,k-1}$ and $xin F_{k-1}(sigma)$ the k-th compononent is uniquely determined, by $x_{omega_h(sigma(k))}$.Since $omega_h(sigma(k))=sigma(h)$ and $x_{(omega_h circ sigma)^{-1}(k)}=x_h=x_{sigma(h)}=x_{omega_h(sigma(k))}=x_k$, $(x,x_{omega_h(sigma(k))})$ is actually in $F_k(omega_h(sigma))$. It follows, that:
$$F_k(omega_h(sigma))={(x,x_{omega_h(sigma(k))}) : x in F_{k-1}(sigma)} Rightarrow |F_{k}(omega_h(sigma(k)))|=|F_{k-1}(sigma)|$$



This yields: $$frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k-1}}|F_{k-1}(omega_k(sigma))|n}{k!}$$
$$overset{IH}{=}frac{n(k-1)!{k+n-2 choose k-1}}{k!}=frac{n-1}{k}{k+n-2 choose k-1}+frac{1}{k}{k+n-2 choose k-1}$$$$={k+n-2 choose k}+frac{1}{k}{k+n-2 choose k-1}$$
Now we are taking a closer look at the latter guys $forall h in{1,..k-1}:$
$$frac{sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)= i, i=1}^{k-1}|F_k(sigma)|}{k!}=frac{sum_{i=1}^{k-1}sum_{sigmain S^{k-1}}|F_{k-1}(omega_i(sigma))|}{k!}$$



$$overset{IH}{=}frac{sum_{i=1}^{k-1}(k-1)!{k+n-2 choose k-1}}{k!}=frac{k-1}{k}{k+n-2 choose k-1 }$$
We conclude:
$$|N^k/sim|=frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}+frac{sum_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}$$
$$={k+n-2 choose k}+frac{1}{k}{k+n-2 choose k-1}+
frac{k-1}{k}{k+n-2 choose k-1 }$$

$$={k+n-2 choose k}+{k+n-2 choose k-1 }={k+n-1 choose k}$$







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Nov 17 at 18:21

























answered Nov 17 at 16:23









Martin Erhardt

1859




1859








  • 1




    The base case of the induction is wrong. Trivially, if you only have one bin there's only one way to store the stars.
    – Peter Taylor
    Nov 17 at 17:45










  • Oh I thought about pulling n balls out of an urn k - times neglecting sequence with replacement. This is dual in a way to the stars-bins-approach.
    – Martin Erhardt
    Nov 17 at 18:09










  • So the proof is actually correct, but I confused two different models of the same problem.
    – Martin Erhardt
    Nov 17 at 18:13














  • 1




    The base case of the induction is wrong. Trivially, if you only have one bin there's only one way to store the stars.
    – Peter Taylor
    Nov 17 at 17:45










  • Oh I thought about pulling n balls out of an urn k - times neglecting sequence with replacement. This is dual in a way to the stars-bins-approach.
    – Martin Erhardt
    Nov 17 at 18:09










  • So the proof is actually correct, but I confused two different models of the same problem.
    – Martin Erhardt
    Nov 17 at 18:13








1




1




The base case of the induction is wrong. Trivially, if you only have one bin there's only one way to store the stars.
– Peter Taylor
Nov 17 at 17:45




The base case of the induction is wrong. Trivially, if you only have one bin there's only one way to store the stars.
– Peter Taylor
Nov 17 at 17:45












Oh I thought about pulling n balls out of an urn k - times neglecting sequence with replacement. This is dual in a way to the stars-bins-approach.
– Martin Erhardt
Nov 17 at 18:09




Oh I thought about pulling n balls out of an urn k - times neglecting sequence with replacement. This is dual in a way to the stars-bins-approach.
– Martin Erhardt
Nov 17 at 18:09












So the proof is actually correct, but I confused two different models of the same problem.
– Martin Erhardt
Nov 17 at 18:13




So the proof is actually correct, but I confused two different models of the same problem.
– Martin Erhardt
Nov 17 at 18:13


















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%2f3002539%2fapplying-burnsides-lemma-to-show-there-are-kn-1-choose-k-1-ways-to-store-n%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

AnyDesk - Fatal Program Failure

How to calibrate 16:9 built-in touch-screen to a 4:3 resolution?

QoS: MAC-Priority for clients behind a repeater