Modeling counting problems - Proof verification

Question

I'm trying to model the following problem in a meaningful way, and also I need help with part (b).

For part (a), I'm thinking that one way to see the problem is to group the players into $n$ pairs, represented by the sets $A_i$, for $i =1,2,...,n$. Now if the color is not an issue, then we simply need to enumerate the set $$\{\{A_1,A_2,...,A_n\}: \dot{\bigcup} A_i = [2n], |A_i|=2\}$$ which is $$\frac{{2n\choose 2}{2n-2\choose 2}...{2\choose 2}}{n!}$$

But for each pair, there are 2 ways to give the 2 players the color black or white. So we want to multiply each term in the numerator by 2, which gives the final answer: $$\frac{[{2n\choose 2}\times 2]\times[{2n-2\choose 2}\times 2]...[{2\choose 2}\times 2]}{n!} = \frac{{2n\choose 2}{2n-2\choose 2}...{2\choose 2}}{n!} \times 2^n$$

For part (b), I use the same $A_i$'s, but each one of them is also paired up with a $t_j$, for $j=1,2,...n$, denoting the table that the pair sit in. The set that need to be enumerated would be: $$\{\{(A_1,t_1),(A_2,t_2)...,(A_n,t_n)\}: \dot{\bigcup} A_i = [2n], |A_i|=2, \dot{\bigcup} t_j = [n], |t_j|=1\}$$ Here I get stuck since I don't know how to reason about the number of time a particular set $\{(A_1,t_1),(A_2,t_2)...,(A_n,t_n)\}$ is counted, i.e. what the denominator of the fraction would be.

So my questions are:

(1) Is the analysis above correct?

(2) If yes, how do I incorporate the information about the colors into the set representation in part (a)?

(3) What is the denominator in part (b)?

=======================================================

Edit: For part (c), following the same strategy, I think the set that needs to be enumerated would be:

$$\{\{(A_1,t_1,a_1),(A_2,t_2,a_1)...,(A_n,t_n,a_n)\}: \dot{\bigcup} A_i = [2n], |A_i|=2, t_j = \{0,1\}^1, a_i \in A_i\}$$

where $t_j$ is a binary variable denoting whether the pairs sit at the special table or not, and $a_i$ is the variable for color.

The count would be: $$\frac{{2n\choose 2}{2n-2\choose 2}...{2\choose 2}}{n!} \times 4^n$$

Please (4) verify this solution.

Answer 1

1. Yes.

2. For each pair $A_i$, you just need to specify the white player. For example, you could use $$ \{((A_1,a_1),(A_2,a_2),\dots,(A_n,a_n)):\bigsqcup A_i=[2n],|A_i|=2,a_i\in A_i\} $$

3. For (b), each seating arrangement can be represented in $n!$ ways by the notation $((A_1,t_1),(A_2,t_2),\dots,(A_n,t_n))$, corresponding to the $n!$ permutations of the list of the $n$ tuples $(A_i,t_i)$. Therefore, the denominator is $n!$.
   
   The set-builder description you are using obscures the simplicity of the answer. There are $\binom{2n}2$ choices for who sits at the first table, $\binom{2n-2}2$ for who sits at the second table, and so on. Thus, the count is $\binom{2n}2\binom{2n-2}2\cdots\binom{2}2$.

Answer 2

This problem looks like it was specially designed to be scholastically approached by species and e.g.f.'s.

1) We have a n-sets of 2-sets. The species is $E_n(E_2(X))$ and the e.g.f. is:

$\frac{1}{n!} \left(\frac {x^2}{2!}\right)^n = \frac{(2n)!}{n!(2^n)} \frac {x^{2n}}{(2n)!} $

the number required is the coefficient $ \frac{(2n)!}{n!(2^n)} $

2) We have a n-string of 2-sets. The species is $L_n(E_2(X))$ and the e.g.f. is:

$\left(\frac {x^2}{2!}\right)^n = \frac{(2n)!}{2^n} \frac {x^{2n}}{(2n)!} $

The number required is the coefficient $ \frac{(2n)!}{2^n} $

3) We have a pair and a (n-1)-set of pairs.

The species is $L_2(X).E_{n-1}(L_2(X))$ and the e.g.f. is:

$ x^2 \frac{\left(x^2\right)^{n-1}}{(n-1)!}= \frac{(2n)!}{(n-1)!} \frac {x^{2n}}{(2n)!} $

The number required is the coefficient $ \frac{(2n)!}{(n-1)!} $