3
$\begingroup$

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}$?

$\endgroup$
4
  • 1
    $\begingroup$ Your work suggests that you meant letter $A$ occurs at most $2n$ times and that letter $B$ occurs at most $2n$ times. It is not possible for letters $A$ and $B$ to occur at least $2n$ times since $2n + 2n = 4n > 3n$. $\endgroup$ Mar 30, 2019 at 19:22
  • $\begingroup$ @N.F.Taussig yes, english is not my native language and I missed words $\endgroup$
    – user617243
    Mar 30, 2019 at 19:32
  • $\begingroup$ Shouldn't the term $\left(\frac{1 - x^{2n + 1}}{1 - x}\right)$ be squared since there are two factors of $(1 + x + x^2 + \cdots + x^{2n})$? $\endgroup$ Mar 31, 2019 at 0:45
  • $\begingroup$ Right, fixed but still I don't know how to use there enumerators. I know that I can do this in other combinatorics approaches but I am especially interested in use there enumerators. Enumerators were created for computers but we should be able to solve that too :| $\endgroup$
    – user617243
    Mar 31, 2019 at 9:01

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Your work has been invaluable to me! Thanks for great explanation. As you see, it is really interesting method but also hard. I think that it is better for computer than for us, but we should understand it too. Thanks again! $\endgroup$
    – user617243
    Apr 1, 2019 at 15:50
  • 1
    $\begingroup$ There were some calculation mistakes which I have now corrected! $\endgroup$
    – Explorer
    Apr 2, 2019 at 7:55
0
$\begingroup$

Premises

We'll use this notation:

$$\alpha=\text{number of repetitions of letter } A$$ $$\beta=\text{number of repetitions of letter } B$$ $$\gamma=\text{number of repetitions of letter } C$$

Clearly a generic permutation with repetition is:

$$P_{3n,(\alpha,\beta,\gamma)}=\frac{3n!}{\alpha!\beta!\gamma!}$$

We can distinguish 4 cases

1° case: $n$ is odd and $\alpha$ and $\beta$ are even

So: $$\alpha=2a$$ $$\beta=2b$$ $$\alpha=2c+1$$

In this case the number of $3n$-subsets is clearly:

$$\sum_{a=0}^{n}\sum_{b=0}^{n} \frac{3n!}{2a!2b!(3n-2a-2b)!}$$

2° case: $n$ is odd and $\alpha$ and $\beta$ are odd

So: $$\alpha=2a+1$$ $$\beta=2b+1$$ $$\alpha=2c+1$$

In this case the number of $3n$-subsets is clearly:

$$\sum_{a=0}^{n}\sum_{b=0}^{n} \frac{3n!}{(2a-1)!(2b-1)!(3n-2a-2b+2)!}$$

So if $n$ is odd the answer is:

$$\sum_{a=0}^{n}\sum_{b=0}^{n} \left[\frac{3n!}{(2a-1)!(2b-1)!(3n-2a-2b+2)!}+ \frac{3n!}{2a!2b!(3n-2a-2b)!}\right]$$

If $n$ is even the reasoning is the same but I can't find any further simplification :( .

$\endgroup$
2
  • $\begingroup$ it is interesting apporach but as I said, I really want to solve that with enumerators $\endgroup$
    – user617243
    Mar 30, 2019 at 23:20
  • $\begingroup$ Since all 'A's and 'B's are identical, you do not have to consider a permutation of 'A's and 'B's, once their number repetition is fixed. $\endgroup$
    – Explorer
    Apr 2, 2019 at 7:59
0
$\begingroup$

We obtain for $n\geq 1$:

\begin{align*} [x^{3n}]&\left(\frac{1-x^{2n+1}}{1-x}\right)^2\frac{x}{1-x^2}\tag{1}\\ &=[x^{3n-1}]\frac{1-2x^{2n+1}}{(1-x)^2\left(1-x^2\right)}\tag{2}\\ &=\left([x^{3n-1}]-2[x^{n-2}]\right)\sum_{k=0}^\infty\binom{-2}{k}(-x)^k\sum_{j=0}^\infty x^{2j}\tag{3}\\ \end{align*}

Comment:

  • In (2) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and we expand the numerator skipping the term $x^{4n+2}$ which does not contribute to $[x^{3n-1}]$.

  • In (3) we apply the rule from (2) again and do a geometric and a binomial series expansion.

Next we calculate the coefficient of $x^n$. We obtain from (3) \begin{align*} [x^n]&\sum_{j=0}^\infty x^{2j}\sum_{k=0}^\infty\binom{k+1}{1}x^k\tag{4}\\ &=\sum_{j=0}^{\left\lfloor n/2\right\rfloor}[x^{n-2j}]\sum_{k=0}^\infty (k+1)x^k\tag{5}\\ &=\sum_{j=0}^{\left\lfloor n/2\right\rfloor}(n-2j+1)\tag{6}\\ &=(n+1)\sum_{j=0}^{\left\lfloor n/2\right\rfloor}1-2\sum_{j=0}^{\left\lfloor n/2\right\rfloor}j\\ &=(n+1)\left(\left\lfloor\frac{n}{2}+1\right\rfloor\right)-\frac{n}{2}\left(\left\lfloor\frac{n}{2}+1\right\rfloor\right)\\ &=\begin{cases} (n+1)\left(\frac{n}{2}+1\right)-\frac{n}{2}\left(\frac{n}{2}+1\right)&\qquad\qquad\qquad n\text{ even}\\ (n+1)\left(\frac{n-1}{2}+1\right)-\frac{n-1}{2}\left(\frac{n-1}{2}+1\right)&\qquad\qquad\qquad n\text{ odd}\\ \end{cases}\\ &=\begin{cases} \frac{1}{4}(n+2)^2&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ n\text{ even}\\ \frac{1}{4}(n+2)^2-\frac{1}{4}&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ n\text{ odd}\tag{7}\\ \end{cases} \end{align*}

Comment:

  • In (4) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

  • In (5) we apply again $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and we set the upper limit of the outer sum to $\left\lfloor\frac{n}{2}\right\rfloor$ since the coefficient is non-negative.

  • In (6) we select the coefficient of $x^{n-2j}$.

We can now evaluate (3) with the help of (7) and note that if $n$ is even we have odd $3n-1$ and even $n-2$. On the other hand if $n$ is odd we have even $3n-1$ and odd $n-2$.

We obtain from (3) and (7) \begin{align*} \color{blue}{[x^{3n}]}&\color{blue}{\left(\frac{1-x^{2n+1}}{1-x}\right)^2\frac{x}{1-x^2}}\\ &=\left([x^{3n-1}]-2[x^{n-2}]\right)\sum_{k=0}^\infty\binom{-2}{k}(-x)^k\sum_{j=0}^\infty x^{2j}\\ &=\begin{cases} \frac{1}{4}(3n+1)^2-\frac{1}{4}-2\cdot\frac{1}{4}n^2&\qquad\qquad\qquad n\text{ even}\\ \frac{1}{4}(3n+1)^2-2\left(\frac{1}{4}n^2+\frac{1}{4}\right)&\qquad\qquad\qquad n\text{ odd}\\ \end{cases}\\ &\,\,\color{blue}{=\frac{1}{4}\left(7n^2+6n+3[[n\text{ odd}]]\right)}\tag{8} \end{align*}

In (8) we use Iverson brackets as compact notation for even and odd cases.

$\endgroup$

You must log in to answer this question.