Mixing
Set Partition of N elements into K groups. All equal elements.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I am trying to get the total number of possible set partitions of N elements into K groups, in a case where all the elements are the same. For example, in the case of $N=2$ and $K=3$ the possible partitions are 6 and would be:
(the numbers are the total of elements in each group)
2 0 0
1 1 0
1 0 1
0 1 1
0 2 0
0 0 2
The case for $N=3$ and $K=3$ seems to result in 10.
I know it is a sum that depends on how many elements were put in the
"first" group (it starts with $K+...$, which is the case where all the elements went into one group) , but I can't grasp what is the exact pattern here. This looks like a special case of the Bell number I think, but I wasn't able to use that either.
combinatorics combinations set-partition
asked Jul 24 at 8:59
mechanical_fan
776
add a comment |Â
up vote
1
down vote
favorite
I am trying to get the total number of possible set partitions of N elements into K groups, in a case where all the elements are the same. For example, in the case of $N=2$ and $K=3$ the possible partitions are 6 and would be:
(the numbers are the total of elements in each group)
2 0 0
1 1 0
1 0 1
0 1 1
0 2 0
0 0 2
The case for $N=3$ and $K=3$ seems to result in 10.
I know it is a sum that depends on how many elements were put in the
"first" group (it starts with $K+...$, which is the case where all the elements went into one group) , but I can't grasp what is the exact pattern here. This looks like a special case of the Bell number I think, but I wasn't able to use that either.
combinatorics combinations set-partition
asked Jul 24 at 8:59
mechanical_fan
776
1
$0,, 1,, 1$ looks like a possibility too. There will be a stars and bars calculation of these compositions and $6=4choose 2$ while $10=5choose 2$
– Henry
Jul 24 at 9:09
Oh, it definitely is a possibility I forgot (I'll edit). I had never heard of stars and bars, I'll look into it
– mechanical_fan
Jul 24 at 9:19
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am trying to get the total number of possible set partitions of N elements into K groups, in a case where all the elements are the same. For example, in the case of $N=2$ and $K=3$ the possible partitions are 6 and would be:
(the numbers are the total of elements in each group)
2 0 0
1 1 0
1 0 1
0 1 1
0 2 0
0 0 2
The case for $N=3$ and $K=3$ seems to result in 10.
I know it is a sum that depends on how many elements were put in the
"first" group (it starts with $K+...$, which is the case where all the elements went into one group) , but I can't grasp what is the exact pattern here. This looks like a special case of the Bell number I think, but I wasn't able to use that either.
combinatorics combinations set-partition
asked Jul 24 at 8:59
mechanical_fan
776
I am trying to get the total number of possible set partitions of N elements into K groups, in a case where all the elements are the same. For example, in the case of $N=2$ and $K=3$ the possible partitions are 6 and would be:
(the numbers are the total of elements in each group)
2 0 0
1 1 0
1 0 1
0 1 1
0 2 0
0 0 2
The case for $N=3$ and $K=3$ seems to result in 10.
I know it is a sum that depends on how many elements were put in the
"first" group (it starts with $K+...$, which is the case where all the elements went into one group) , but I can't grasp what is the exact pattern here. This looks like a special case of the Bell number I think, but I wasn't able to use that either.
combinatorics combinations set-partition
asked Jul 24 at 8:59
mechanical_fan
776
edited Jul 24 at 9:19
asked Jul 24 at 8:59
mechanical_fan
776
asked Jul 24 at 8:59
mechanical_fan
776
asked Jul 24 at 8:59
mechanical_fan
776
776
1
$0,, 1,, 1$ looks like a possibility too. There will be a stars and bars calculation of these compositions and $6=4choose 2$ while $10=5choose 2$
– Henry
Jul 24 at 9:09
Oh, it definitely is a possibility I forgot (I'll edit). I had never heard of stars and bars, I'll look into it
– mechanical_fan
Jul 24 at 9:19
add a comment |Â
1
$0,, 1,, 1$ looks like a possibility too. There will be a stars and bars calculation of these compositions and $6=4choose 2$ while $10=5choose 2$
– Henry
Jul 24 at 9:09
Oh, it definitely is a possibility I forgot (I'll edit). I had never heard of stars and bars, I'll look into it
– mechanical_fan
Jul 24 at 9:19
1
1
$0,, 1,, 1$ looks like a possibility too. There will be a stars and bars calculation of these compositions and $6=4choose 2$ while $10=5choose 2$
– Henry
Jul 24 at 9:09
$0,, 1,, 1$ looks like a possibility too. There will be a stars and bars calculation of these compositions and $6=4choose 2$ while $10=5choose 2$
– Henry
Jul 24 at 9:09
Oh, it definitely is a possibility I forgot (I'll edit). I had never heard of stars and bars, I'll look into it
– mechanical_fan
Jul 24 at 9:19
Oh, it definitely is a possibility I forgot (I'll edit). I had never heard of stars and bars, I'll look into it
– mechanical_fan
Jul 24 at 9:19
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
Think of your elements as of $n$ balls which are to be placed into $k$ urns. We can place the balls in a row, and then insert $k-1$ dividors, separating thge balls into $k$ groups. Each group containing the balls which are to be placed into the corresponding urn. We have $n+k-1$ places for dividors and balls, and k-1 dividors to choose from them. So there are:
$binomn+k-1k-1$
possibilities.
answered Jul 24 at 10:41
Eulerrr
1646
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Think of your elements as of $n$ balls which are to be placed into $k$ urns. We can place the balls in a row, and then insert $k-1$ dividors, separating thge balls into $k$ groups. Each group containing the balls which are to be placed into the corresponding urn. We have $n+k-1$ places for dividors and balls, and k-1 dividors to choose from them. So there are:
$binomn+k-1k-1$
possibilities.
answered Jul 24 at 10:41
Eulerrr
1646
add a comment |Â
up vote
0
down vote
Think of your elements as of $n$ balls which are to be placed into $k$ urns. We can place the balls in a row, and then insert $k-1$ dividors, separating thge balls into $k$ groups. Each group containing the balls which are to be placed into the corresponding urn. We have $n+k-1$ places for dividors and balls, and k-1 dividors to choose from them. So there are:
$binomn+k-1k-1$
possibilities.
answered Jul 24 at 10:41
Eulerrr
1646
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Think of your elements as of $n$ balls which are to be placed into $k$ urns. We can place the balls in a row, and then insert $k-1$ dividors, separating thge balls into $k$ groups. Each group containing the balls which are to be placed into the corresponding urn. We have $n+k-1$ places for dividors and balls, and k-1 dividors to choose from them. So there are:
$binomn+k-1k-1$
possibilities.
answered Jul 24 at 10:41
Eulerrr
1646
Think of your elements as of $n$ balls which are to be placed into $k$ urns. We can place the balls in a row, and then insert $k-1$ dividors, separating thge balls into $k$ groups. Each group containing the balls which are to be placed into the corresponding urn. We have $n+k-1$ places for dividors and balls, and k-1 dividors to choose from them. So there are:
$binomn+k-1k-1$
possibilities.
answered Jul 24 at 10:41
Eulerrr
1646
answered Jul 24 at 10:41
Eulerrr
1646
answered Jul 24 at 10:41
Eulerrr
1646
answered Jul 24 at 10:41
Eulerrr
1646
1646
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861137%2fset-partition-of-n-elements-into-k-groups-all-equal-elements%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
$0,, 1,, 1$ looks like a possibility too. There will be a stars and bars calculation of these compositions and $6=4choose 2$ while $10=5choose 2$
– Henry
Jul 24 at 9:09
Oh, it definitely is a possibility I forgot (I'll edit). I had never heard of stars and bars, I'll look into it
– mechanical_fan
Jul 24 at 9:19