Count permutations of [1, 1, 1, 2, 2, 3, 3, 4, 5] with length 6 How can I count number of permutations such as:
[1, 1, 1, 2, 2, 3]
[1, 2, 1, 3, 2, 4]
[1, 1, 1, 2, 2, 5]
...
So I have:
'1' x 3
'2' x 2
'3' x 2
'4' x 1
'5' x 1
So permutation valid if it contains $\le3$ of '1' and $\le2$ of '2' and and $\le2$ of '3' and $\le1$ of '4' and $\le1$ of '5' and it's length is 6.
I've counted them on Python with filtering and the answer is 3630. But how it works?
Thanks!
 A: The exponential generating function for the number of permutations of length $r$ is
$$f(x) = (1+x)^2 \left( 1 + x + \frac{1}{2!} x^2 \right)^2 \left(1 + x + \frac{1}{2!} x^2 + \frac{1}{3!}x^3 \right)$$
On expansion (I used a computer algebra system), the coefficient of $x^6$ is $121/24$, so the number of permutations of length 6 is

$$\frac{121}{24} \cdot 6! = 3630$$

A: You have five mutually-exclusive kinds of collections here:


*

*Exactly one pair, no three of a kind (like $[1,1,2,3,4,5]$)

*Exactly two pair, no three of a kind (like $[1,1,2,2,3,4]$)

*Exactly three pair (like $[1,1,2,2,3,3]$)

*Three of a kind, no pair (like $[1,1,1,2,3,4]$)

*Three of a kind, one pair (like $[1,1,1,2,2,3]$)


Case 1: Pick the number for the pair, and the places you put them $(3 \cdot 15)$. Then order the other four numbers in the remaining spaces $(4!)$.
Case 2: Pick the two numbers for the pair ($3$) and place the smaller number in two places $(15)$ then the larger in two of the remaining places $(6)$. Then, choose the remaining two numbers and place them $(6)$.
Case 3: Place the $1$s in two of the spaces $(15)$ and then the $2$s in two of the remaining four $(6)$. (The $3$s go in the spaces that remain.)
Case 4: Place the $1$s $(6 \cdot 5 \cdot 4 / (3 \cdot 2 \cdot 1) = 20)$. Choose three numbers out of $2,3,4,5$ and place them ($4 \cdot 6$).
Case 5: Place the $1$s $(20)$. Choose whether the pair is $2$s or $3$s, and place them $(2 \cdot 3)$. Choose the last number and put it in the spot that remains $(3)$.
Adding these up: $1080 + 1620 + 90 + 480 + 360 = 3630$.
(Hat tip to N.F. Taussig for helping me work through the errors!)
A: I believe you are forced to sum mutually exclusive and exhaustive possibilities.
I suggest defining $N(a,b)$ as the number of permutations having $a$ "1"'s and $b$ other doubles. Then ...
$$N(a,b) = \binom 2 b \cdot \frac{6!}{a!(2!)^b}$$
and
$$ N_{tot} = N(0,2)+N(1,2)+N(1,1)+N(2,2)+N(2,1)+N(2,0)+N(3,1)+N(3,0) $$
* EDIT *
I my expression gave the number of permutations given a specific combination of "single" extra numbers (extra means not including 1 or any doubles )
there will be $4-b$ "single" numbers from which we must choose $6-a-2b$
So my formula above should be amended to read
$$N(a,b) =\binom{4-b}{6-a-2b}\binom 2 b \cdot \frac{6!}{a!(2!)^b}$$
Evaluating the formula ...
$$ \begin{eqnarray*} 
N_{tot} =&  \binom 2 2 \binom 2 2 \frac{6!}{(2!)^2} 
+ \binom 2 1 \binom 2 2 \frac{6!}{(2!)^2} 
+ \binom 3 3 \binom 2 1 \frac{6!}{ 2!}
\\+ &\binom 2 0 \binom 2 2 \frac{6!}{2! (2!)^2}  
+ \binom 3 2 \binom 2 1 \frac{6!}{ 2! (2!)} 
+ \binom 4 4 \binom 2 0 \frac{6!}{ 2! } 
\\+ & \binom 3 1 \binom 2 1 \frac{6!}{ 3! (2!)} 
+ \binom 4 3 \binom 2 0 \frac{6!}{ 3! } 
\end{eqnarray*}$$
$$ =(1)(1)(180)+(2)(1)(180)+(1)(2)(360)+ (1)(1)(90) \\+ (3)(2)(180) + (1)(1)(360) + (3)(2)(60) +(4)(1)(120)   $$
$$ =180+360+720+90+1080+360+360+480   = 3630$$
