Mixing
Counting assignments of elements of triples into bins
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
We have a family of $N$ triples $(x_i,y_i,z_i)$, ($1le i le N$) and $N$ bins. We want to distribute the elements of each triple into bins such that each bin has three elements and no bin gets the three elements of any triple ($(x_i,y_i,z_i)$).
Note that triples do not share any elements. The total number of all elements is $3N$.
In how many ways can we perform this?
combinatorics
asked Jul 23 at 21:22
Mohammad Al-Turkistany
388321
add a comment |Â
up vote
0
down vote
favorite
We have a family of $N$ triples $(x_i,y_i,z_i)$, ($1le i le N$) and $N$ bins. We want to distribute the elements of each triple into bins such that each bin has three elements and no bin gets the three elements of any triple ($(x_i,y_i,z_i)$).
Note that triples do not share any elements. The total number of all elements is $3N$.
In how many ways can we perform this?
combinatorics
asked Jul 23 at 21:22
Mohammad Al-Turkistany
388321
What have you tried? Also, for clarity: How can a bin be empty? you have $3N$ objects in total and each used bin "has three elements" so that's all the bins, yes?
– lulu
Jul 23 at 21:29
@lulu please see the edited post.
– Mohammad Al-Turkistany
Jul 23 at 21:38
Still unclear. Might help to work explicit examples. I guess (though I am not at all sure) that you meant to require that $N$ was a multiple of $3$? If so, then what are the answers for $N=3,6$?
– lulu
Jul 23 at 21:45
@lulu The problem is completely different after the revision.
– Mohammad Al-Turkistany
Jul 23 at 22:44
So, first permute the $x's$, now permute that list so that there are no fixed points, now permute that list so that there are no matches with either of the first two.
– lulu
Jul 23 at 23:40
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
We have a family of $N$ triples $(x_i,y_i,z_i)$, ($1le i le N$) and $N$ bins. We want to distribute the elements of each triple into bins such that each bin has three elements and no bin gets the three elements of any triple ($(x_i,y_i,z_i)$).
Note that triples do not share any elements. The total number of all elements is $3N$.
In how many ways can we perform this?
combinatorics
asked Jul 23 at 21:22
Mohammad Al-Turkistany
388321
We have a family of $N$ triples $(x_i,y_i,z_i)$, ($1le i le N$) and $N$ bins. We want to distribute the elements of each triple into bins such that each bin has three elements and no bin gets the three elements of any triple ($(x_i,y_i,z_i)$).
Note that triples do not share any elements. The total number of all elements is $3N$.
In how many ways can we perform this?
combinatorics
asked Jul 23 at 21:22
Mohammad Al-Turkistany
388321
edited Jul 23 at 22:50
asked Jul 23 at 21:22
Mohammad Al-Turkistany
388321
asked Jul 23 at 21:22
Mohammad Al-Turkistany
388321
asked Jul 23 at 21:22
Mohammad Al-Turkistany
388321
388321
What have you tried? Also, for clarity: How can a bin be empty? you have $3N$ objects in total and each used bin "has three elements" so that's all the bins, yes?
– lulu
Jul 23 at 21:29
@lulu please see the edited post.
– Mohammad Al-Turkistany
Jul 23 at 21:38
Still unclear. Might help to work explicit examples. I guess (though I am not at all sure) that you meant to require that $N$ was a multiple of $3$? If so, then what are the answers for $N=3,6$?
– lulu
Jul 23 at 21:45
@lulu The problem is completely different after the revision.
– Mohammad Al-Turkistany
Jul 23 at 22:44
So, first permute the $x's$, now permute that list so that there are no fixed points, now permute that list so that there are no matches with either of the first two.
– lulu
Jul 23 at 23:40
add a comment |Â
What have you tried? Also, for clarity: How can a bin be empty? you have $3N$ objects in total and each used bin "has three elements" so that's all the bins, yes?
– lulu
Jul 23 at 21:29
@lulu please see the edited post.
– Mohammad Al-Turkistany
Jul 23 at 21:38
Still unclear. Might help to work explicit examples. I guess (though I am not at all sure) that you meant to require that $N$ was a multiple of $3$? If so, then what are the answers for $N=3,6$?
– lulu
Jul 23 at 21:45
@lulu The problem is completely different after the revision.
– Mohammad Al-Turkistany
Jul 23 at 22:44
So, first permute the $x's$, now permute that list so that there are no fixed points, now permute that list so that there are no matches with either of the first two.
– lulu
Jul 23 at 23:40
What have you tried? Also, for clarity: How can a bin be empty? you have $3N$ objects in total and each used bin "has three elements" so that's all the bins, yes?
– lulu
Jul 23 at 21:29
What have you tried? Also, for clarity: How can a bin be empty? you have $3N$ objects in total and each used bin "has three elements" so that's all the bins, yes?
– lulu
Jul 23 at 21:29
@lulu please see the edited post.
– Mohammad Al-Turkistany
Jul 23 at 21:38
@lulu please see the edited post.
– Mohammad Al-Turkistany
Jul 23 at 21:38
Still unclear. Might help to work explicit examples. I guess (though I am not at all sure) that you meant to require that $N$ was a multiple of $3$? If so, then what are the answers for $N=3,6$?
– lulu
Jul 23 at 21:45
Still unclear. Might help to work explicit examples. I guess (though I am not at all sure) that you meant to require that $N$ was a multiple of $3$? If so, then what are the answers for $N=3,6$?
– lulu
Jul 23 at 21:45
@lulu The problem is completely different after the revision.
– Mohammad Al-Turkistany
Jul 23 at 22:44
@lulu The problem is completely different after the revision.
– Mohammad Al-Turkistany
Jul 23 at 22:44
So, first permute the $x's$, now permute that list so that there are no fixed points, now permute that list so that there are no matches with either of the first two.
– lulu
Jul 23 at 23:40
So, first permute the $x's$, now permute that list so that there are no fixed points, now permute that list so that there are no matches with either of the first two.
– lulu
Jul 23 at 23:40
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
You can do this using inclusion–exclusion.
There are $frac(3N)!3!^N$ ways to distribute the elements over the bins. If $k$ particular bins contain all the elements of a triple, there are $frac(3(N-k))!3!^N-k$ ways to distribute the remaining elements over the remaining triples. There are $binom Nk$ ways to choose the $k$ particular bins and $fracN!(N-k)!$ ways to choose triples for them. Thus the number of distributions in which no bin contains all elements of a triple is
$$
sum_k=0^N(-1)^kbinom NkfracN!(N-k)!frac(3(N-k))!3!^N-k;.
$$
answered Jul 24 at 4:17
joriki
164k10180328
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
You can do this using inclusion–exclusion.
There are $frac(3N)!3!^N$ ways to distribute the elements over the bins. If $k$ particular bins contain all the elements of a triple, there are $frac(3(N-k))!3!^N-k$ ways to distribute the remaining elements over the remaining triples. There are $binom Nk$ ways to choose the $k$ particular bins and $fracN!(N-k)!$ ways to choose triples for them. Thus the number of distributions in which no bin contains all elements of a triple is
$$
sum_k=0^N(-1)^kbinom NkfracN!(N-k)!frac(3(N-k))!3!^N-k;.
$$
answered Jul 24 at 4:17
joriki
164k10180328
add a comment |Â
up vote
1
down vote
accepted
You can do this using inclusion–exclusion.
There are $frac(3N)!3!^N$ ways to distribute the elements over the bins. If $k$ particular bins contain all the elements of a triple, there are $frac(3(N-k))!3!^N-k$ ways to distribute the remaining elements over the remaining triples. There are $binom Nk$ ways to choose the $k$ particular bins and $fracN!(N-k)!$ ways to choose triples for them. Thus the number of distributions in which no bin contains all elements of a triple is
$$
sum_k=0^N(-1)^kbinom NkfracN!(N-k)!frac(3(N-k))!3!^N-k;.
$$
answered Jul 24 at 4:17
joriki
164k10180328
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
You can do this using inclusion–exclusion.
There are $frac(3N)!3!^N$ ways to distribute the elements over the bins. If $k$ particular bins contain all the elements of a triple, there are $frac(3(N-k))!3!^N-k$ ways to distribute the remaining elements over the remaining triples. There are $binom Nk$ ways to choose the $k$ particular bins and $fracN!(N-k)!$ ways to choose triples for them. Thus the number of distributions in which no bin contains all elements of a triple is
$$
sum_k=0^N(-1)^kbinom NkfracN!(N-k)!frac(3(N-k))!3!^N-k;.
$$
answered Jul 24 at 4:17
joriki
164k10180328
You can do this using inclusion–exclusion.
There are $frac(3N)!3!^N$ ways to distribute the elements over the bins. If $k$ particular bins contain all the elements of a triple, there are $frac(3(N-k))!3!^N-k$ ways to distribute the remaining elements over the remaining triples. There are $binom Nk$ ways to choose the $k$ particular bins and $fracN!(N-k)!$ ways to choose triples for them. Thus the number of distributions in which no bin contains all elements of a triple is
$$
sum_k=0^N(-1)^kbinom NkfracN!(N-k)!frac(3(N-k))!3!^N-k;.
$$
answered Jul 24 at 4:17
joriki
164k10180328
answered Jul 24 at 4:17
joriki
164k10180328
answered Jul 24 at 4:17
joriki
164k10180328
answered Jul 24 at 4:17
joriki
164k10180328
164k10180328
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%2f2860791%2fcounting-assignments-of-elements-of-triples-into-bins%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
What have you tried? Also, for clarity: How can a bin be empty? you have $3N$ objects in total and each used bin "has three elements" so that's all the bins, yes?
– lulu
Jul 23 at 21:29
@lulu please see the edited post.
– Mohammad Al-Turkistany
Jul 23 at 21:38
Still unclear. Might help to work explicit examples. I guess (though I am not at all sure) that you meant to require that $N$ was a multiple of $3$? If so, then what are the answers for $N=3,6$?
– lulu
Jul 23 at 21:45
@lulu The problem is completely different after the revision.
– Mohammad Al-Turkistany
Jul 23 at 22:44
So, first permute the $x's$, now permute that list so that there are no fixed points, now permute that list so that there are no matches with either of the first two.
– lulu
Jul 23 at 23:40