We all know about the classic Ménage problem which for the number of different ways in which it is possible to seat a set of male-female couples at a dining table so that men and women alternate and nobody sits next to his or her partner.
Here again we consider a similar setup except each family consists four members, a father, mother, a son and a daughter. To be clear, we seek the number of different ways in which it possible to seat a set of families at a dining table so that men and women alternate and no family end up sitting together. Note that we consider a family to be sitting together only when all members of the same family sit next to each other.
The idea here is inspired by the Non-sexist solution of the menage problem. It is easy to see that there are $2(2n)!^2$ seatings in total such that the dinner table has a male-female arrangement. That is, $2$ ways to decide which seat is for men/women; $(2n)!$ ways each for men and women.
Consider $n>1$. Let $L_n$ be the answer we are trying to find for the case of $n$ families. Then, using inclusion-exclusion, we have
$L_n=\displaystyle\sum_{k=0}^n(-1)^k\binom{n}{k}w_k$
where $w_k$ denotes the number of seatings such that a given set of $k$ families are seated together (There maybe other families sitting together as well but we don't care about them). To compute $w_k$, let's define $d_k$ which is the number of ways of covering a circle containing $4n$ equally spaced points with a curved domino that spans $4$ points.
Calculation of $d_k$'s are very easy. It is just the stars and bars problem on a circular setup. For the problem at hand, we have,
$d_k=\displaystyle\frac{4n}{4n-3k}\binom{4n-3k}{k}$
The idea for the above formulae is exactly like that of this Stack Exchange question.
Now, we compute $w_k$. Note that there are $8$ ways in which a family can be seated together with men and women alternating
If we are done choosing $k$ families, we have $2$ ways to decide on which are men's seats and which are women's. We have $d_k$ ways to seat these $k$ families in the circular table. The families can be permuted in $k!$ ways. As we have selected men's (and women's) seats, each of the $k$ families that are supposed to sit together, can have $4$ ways of being seated. The remaining $2n-2k$ men and $2n-2k$ women can be permuted in the remaining seats. In short, we have,
$w_k=2\cdot d_k \cdot 4 ^k \cdot k! \cdot (2n-2k)!^2$
Therefore,
$L_n=\displaystyle\sum_{k=0}^n(-1)^k\binom{n}{k}\cdot 2\cdot 4^k\cdot k!\cdot (2n-2k)!^2\cdot d_k$
Substituting $d_k$, and simplifying we finally end up with,
$L_n=2\cdot n!\displaystyle\sum_{k=0}^n(-4)^k\frac{4n}{4n-3k}\binom{4n-3k}{k}\frac{(2n-2k)!^2}{(n-k)!}$
And there we have our final answer.
Another interesting variation in our 'generalized menage problem' is asking for the number of ways such that no two members of the same family sit together. This seems rather complicated in that it doesn't seem to admit any closed form. Of course, this is just my opinion.
Trying to find an answer to this variation, I started thinking about arranging balls of $n$ different colors with $c[i]$ balls of color $i$. Seems DP is the best approach as discussed in AMBALLS - Editorial. But let's postpone that for a later post.
Hope you enjoyed this post. I'll write again with a nice post.
UPDATE: In the spirit of ménage numbers, if we define
$A_n=\displaystyle\sum_{k=0}^n(-4)^k\frac{4n}{4n-3k}\binom{4n-3k}{k}\frac{(2n-2k)!^2}{(n-k)!}$
then we have this monstrous recurrence for $A_n$'s.
$\begin{align}
(2 n - 3) (2 n - 5) (2 n - 7) (n - 2) (n - 3) (n - 4) (n - 5)A_n&=4 (n - 5) (n - 4) (n - 3) n (2 n - 7) (2 n - 5) (8 n^4 - 36 n^3 + 54 n^2 - 17 n - 13) A_{n - 1} + \\&
16 (n - 5) (n - 4) (n - 3) n (2 n - 7) (16 n^5 - 144 n^4 + 472 n^3 -
736 n^2 + 505 n - 95) A_{n - 2} - \\&
384 (n - 5) (n - 4) n (2 n - 1) (12 n^3 - 84 n^2 + 197 n - 145) A_{
n - 3} + \\&
2304 (n - 5) (n - 3) n (2 n - 3) (2 n - 1) (6 n^2 - 21 n + 10) A_{
n - 4} + \\&
27648 (n - 4) (n - 3) (n - 1) n (2 n - 5) (2 n - 3) (2 n - 1) A_{
n - 5}+ \\&
96 \cdot (-4)^n \cdot (2 n - 7) (2 n - 5) (2 n - 3) (2 n - 1) (4 n - 5)
\end{align}$
Obviously, I didn't find this recurrence manually. I used the amazing RISCergosum package which has a Mathematica implementation of Zeilberger's algorithm for finding holonomic recurrences. And it did the job in a matter of seconds. Amazing!!
Here again we consider a similar setup except each family consists four members, a father, mother, a son and a daughter. To be clear, we seek the number of different ways in which it possible to seat a set of families at a dining table so that men and women alternate and no family end up sitting together. Note that we consider a family to be sitting together only when all members of the same family sit next to each other.
The idea here is inspired by the Non-sexist solution of the menage problem. It is easy to see that there are $2(2n)!^2$ seatings in total such that the dinner table has a male-female arrangement. That is, $2$ ways to decide which seat is for men/women; $(2n)!$ ways each for men and women.
Consider $n>1$. Let $L_n$ be the answer we are trying to find for the case of $n$ families. Then, using inclusion-exclusion, we have
$L_n=\displaystyle\sum_{k=0}^n(-1)^k\binom{n}{k}w_k$
where $w_k$ denotes the number of seatings such that a given set of $k$ families are seated together (There maybe other families sitting together as well but we don't care about them). To compute $w_k$, let's define $d_k$ which is the number of ways of covering a circle containing $4n$ equally spaced points with a curved domino that spans $4$ points.
Calculation of $d_k$'s are very easy. It is just the stars and bars problem on a circular setup. For the problem at hand, we have,
$d_k=\displaystyle\frac{4n}{4n-3k}\binom{4n-3k}{k}$
The idea for the above formulae is exactly like that of this Stack Exchange question.
Now, we compute $w_k$. Note that there are $8$ ways in which a family can be seated together with men and women alternating
If we are done choosing $k$ families, we have $2$ ways to decide on which are men's seats and which are women's. We have $d_k$ ways to seat these $k$ families in the circular table. The families can be permuted in $k!$ ways. As we have selected men's (and women's) seats, each of the $k$ families that are supposed to sit together, can have $4$ ways of being seated. The remaining $2n-2k$ men and $2n-2k$ women can be permuted in the remaining seats. In short, we have,
$w_k=2\cdot d_k \cdot 4 ^k \cdot k! \cdot (2n-2k)!^2$
Therefore,
$L_n=\displaystyle\sum_{k=0}^n(-1)^k\binom{n}{k}\cdot 2\cdot 4^k\cdot k!\cdot (2n-2k)!^2\cdot d_k$
Substituting $d_k$, and simplifying we finally end up with,
$L_n=2\cdot n!\displaystyle\sum_{k=0}^n(-4)^k\frac{4n}{4n-3k}\binom{4n-3k}{k}\frac{(2n-2k)!^2}{(n-k)!}$
And there we have our final answer.
Another interesting variation in our 'generalized menage problem' is asking for the number of ways such that no two members of the same family sit together. This seems rather complicated in that it doesn't seem to admit any closed form. Of course, this is just my opinion.
Trying to find an answer to this variation, I started thinking about arranging balls of $n$ different colors with $c[i]$ balls of color $i$. Seems DP is the best approach as discussed in AMBALLS - Editorial. But let's postpone that for a later post.
Hope you enjoyed this post. I'll write again with a nice post.
UPDATE: In the spirit of ménage numbers, if we define
$A_n=\displaystyle\sum_{k=0}^n(-4)^k\frac{4n}{4n-3k}\binom{4n-3k}{k}\frac{(2n-2k)!^2}{(n-k)!}$
then we have this monstrous recurrence for $A_n$'s.
$\begin{align}
(2 n - 3) (2 n - 5) (2 n - 7) (n - 2) (n - 3) (n - 4) (n - 5)A_n&=4 (n - 5) (n - 4) (n - 3) n (2 n - 7) (2 n - 5) (8 n^4 - 36 n^3 + 54 n^2 - 17 n - 13) A_{n - 1} + \\&
16 (n - 5) (n - 4) (n - 3) n (2 n - 7) (16 n^5 - 144 n^4 + 472 n^3 -
736 n^2 + 505 n - 95) A_{n - 2} - \\&
384 (n - 5) (n - 4) n (2 n - 1) (12 n^3 - 84 n^2 + 197 n - 145) A_{
n - 3} + \\&
2304 (n - 5) (n - 3) n (2 n - 3) (2 n - 1) (6 n^2 - 21 n + 10) A_{
n - 4} + \\&
27648 (n - 4) (n - 3) (n - 1) n (2 n - 5) (2 n - 3) (2 n - 1) A_{
n - 5}+ \\&
96 \cdot (-4)^n \cdot (2 n - 7) (2 n - 5) (2 n - 3) (2 n - 1) (4 n - 5)
\end{align}$
Obviously, I didn't find this recurrence manually. I used the amazing RISCergosum package which has a Mathematica implementation of Zeilberger's algorithm for finding holonomic recurrences. And it did the job in a matter of seconds. Amazing!!
Mathematica code:
Clear["Global`*"];
<< RISC`HolonomicFunctions`
ann = Annihilator[
Power[-4, k] (4 n)/(4 n - 3 k)
Binomial[4 n - 3 k, k] Factorial[2 n - 2 k]^2/
Factorial[n - k], {S[k], S[n]}];
Takayama[ann, {k}]
Until then
Yours Aye
Me
No comments:
Post a Comment