Find number of ways to choose $3n$-subset with repetitions from set $\left\{A,B,C\right\}$ such that:
1. Letter $A$ occur at most $2n$
2. Letter $B$ occur at most $2n$
3. Letter $C$ occur odd times
Approach
I want to use there enumerators. Ok, so a factor responsible for $A$ will be
$$(1+x+x^2+ \cdots + x^{2n}) $$
(We can choose $A$ $0$ times, $1$ time, … $2n$ times). The same will be for $B$.
Enumerator for $C$ will be
$$(x+x^3+x^5 + \cdots) $$
(We can choose $C$ 1 time, 3 times, etc)
Ok, so I want to find
$$[x^{3n}](1+x+x^2+ \cdots + x^{2n})(1+x+x^2+ \cdots + x^{2n})(x+x^3+x^5 + \cdots) = $$
$$ [x^{3n}] \left(\frac{1-x^{2n+1}}{1-x}\right)^2 \cdot\frac{x}{1-x^2} $$
but… how I can get from there factor at $x^{3n}$?
Best Answer
Note that \begin{align} (1+x+\ldots+x^{2n})^2 &= \sum_{i=0}^{n}x^{2i}+2\sum_{i=1}^{2n}x^i+2x\sum_{i=2}^{2n}x^i+\ldots2x^{2n-1}x^{2n}\\ &=\sum_{i=0}^{n}x^{2i}+2\sum_{j=0}^{2n-1}\left(x^j\sum_{i=j+1}^{2n}x^i\right). \end{align} So, we have \begin{multline} (1+x+\ldots+x^{2n})^2 (x+x^3+\ldots) \\=\left[ \sum_{i=0}^{n}x^{2i} \right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]+2\sum_{j=0}^{2n-1}\left[\sum_{i=j+1}^{2n}x^{i+j}\right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right] \end{multline} We find the coefficient of $x^{3n}$ in the above expression for two separate cases:
Case 1: $n$ is odd
$x^{3n}$ in $\left[ \sum_{i=0}^{n}x^{2i} \right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$ is due to the terms corresponding to \begin{equation} (2i,2k-1)=(0,3n), (2,3n-2), \ldots, (3n-1,1). \end{equation} Thus, the coefficient of $x^{3n}$ = $\frac{3n+1}{2}$.
For $j$ odd, $x^{3n}$ in $2\left[\sum_{i=j+1}^{2n}x^{i+j}\right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$ is due to the terms corresponding to \begin{equation} (i+j,2k-1)=(2j+2,3n-2j-2), (2j+4,3n-2j-4), \ldots, (2n+j-1,n-j+1), \end{equation} for $i+j\leq 3n-1$ and $j\leq\frac{3n-1}{2}-1$. Thus, the coefficient of $x^{3n}$ is given by \begin{equation} \min\{3n-2j-1,2n-j-1\} = \begin{cases} 2n-j-1&\text{ for } 1\leq j\leq n\\ 3n-2j-1&\text{ for } n< j\leq \frac{3n-1}{2}-1 \end{cases} \end{equation}
For $j$ even, $x^{3n}$ in $2\left[\sum_{i=j+1}^{2n}x^{i+j}\right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$ is due to the terms corresponding to \begin{equation} (i+j,2k-1)=(2j+2,3n-2j-2), (2j+4,3n-2j-4), \ldots, (2n+j,n-j), \end{equation} for $i+j\leq 3n-1$ and $j\leq\frac{3n-1}{2}-1$. Thus, the coefficient of $x^{3n}$ is given by \begin{equation} \min\{3n-2j-1,2n-j\} = \begin{cases} 2n-j&\text{ for } 1\leq j\leq n-1\\ 3n-2j-1&\text{ for } n-1< j\leq \frac{3n-1}{2}-1 \end{cases} \end{equation}
Thus, the required coefficient is given by \begin{equation} \frac{3n+1}{2}+\sum_{j=0}^{\frac{3n-1}{2}-1}(2n-j)+\sum_{j=n}^{\frac{3n-1}{2}-1}(n-j-1) - \frac{n-1}{2} = \frac{7n^2+6n+3}{4}. \end{equation}
Case 2: $n$ is even
$x^{3n}$ does not appear in $\left[ \sum_{i=0}^{n}x^{2i} \right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$. Thus, the coefficient of $x^{3n}=0$.
For $j$ odd, $x^{3n}$ in $2\left[\sum_{i=j+1}^{2n}x^{i+j}\right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$ is due to the terms corresponding to \begin{equation} (i+j,2k-1)=(2j+1,3n-2j-1), (2j+3,3n-2j-3), \ldots, (2n+j,n-j), \end{equation} for $j+i\leq 3n-1$ and $j\leq \frac{3n}{2}-1$. Thus, the coefficient of $x^{3n}$ is given by \begin{equation} \min\{3n-2j,2n-j+1\} = \begin{cases} 2n-j+1&\text{ for } 1\leq j\leq n-1\\ 3n-2j&\text{ for } n-1<j\leq \frac{3n}{2}-1 \end{cases} \end{equation}
For $j$ even, $x^{3n}$ in $2\left[\sum_{i=j+1}^{2n}x^{i+j}\right]\left[\sum_{k=1}^{\infty}x^{2k-1}\right]$ is due to the terms corresponding to \begin{equation} (i+j,2k-1)=(2j+1,3n-2j-1), (2j+3,3n-2j-3), \ldots, (2n+j-1,n-j+1), \end{equation} for $j+i\leq 3n-1$ and $j\leq \frac{3n}{2}-1$. Thus, the coefficient of $x^{3n}$ is given by \begin{equation} \min\{3n-2j,2n-j\} = \begin{cases} 2n-j&\text{ for } 1\leq j\leq n\\ 3n-2j&\text{ for } n<j\leq \frac{3n}{2}-1 \end{cases} \end{equation}
Thus, the required coefficient is given by \begin{equation} \sum_{j=0}^{\frac{3n}{2}-1}(2n-j)+\sum_{j=n+1}^{\frac{3n}{2}-1}(n-j) + n/2 = \frac{7n^2+6n}{4}. \end{equation}
Overall, the number of possibilities is $\frac{7n^2+6 n+3\alpha}{4}$, where \begin{equation} \alpha = \begin{cases} 1, & \text{if } n \text{ is odd}\\ 0, & \text{if } n \text{ is even} \end{cases} \end{equation}
P.S.: Thanks for introducing the technique of solving using enumerators to me.