12-letter words with four X's, four Y's, and four Z's
Okay, per the title, we're constructing 12-letter words with four X's, four Y's, and four Z's. How many such words have no X's in the first 4 letters and no Y's in the next 4 letters?
Let me show my work with what I got. Let's do casework based on the number of X's in the last 4 letters.
YYYY ZZZZ XXXX: 1 possibility
YYYZ ZZZX XXXY: 4(4)(4) = 64 possibilities
YYYY ZZZX XXXZ: 4(4) = 16 possibilities
YYYZ XXZZ XXYZ: 4(6)(12) = 288 possibilities
YYZZ XXZZ XXYY: 6(6)(6) = 216 possibilities
YYYY XXZZ XXZZ: 6(6) = 216 possibilities
YYYY XXXZ XZZZ: 4(4) = 16 possibilities
ZZZY XXXZ XYYY: 4(4)(4) = 64 possibilities
YYZZ XXXZ XZYY: 6(4)(12) = 288 possibilities
YYYZ XXXZ XYZZ: 4(4)(12) = 192 possibilities
ZZZZ XXXX YYYY: 1 possibility
YYYY XXXX ZZZZ: 1 possibility
Adding up, we have 1363 possibilities.
(1) Is this correct?
(2) That was a pain to do all the casework. Is there a cleaner way to solve this problem?
$\endgroup$ 32 Answers
$\begingroup$The inclusion/exclusion argument is to let $A$ be all words, no restrictions. $|A|=\frac{12!}{4!4!4!}.$ Let $A_i$ be the words with an $X$ at position $i,$ with $i=1,2,3,4.$ Let $B_j$ be the words with $Y$ in position $j$ for $j=5,6,7,8.$ Then inclusion-exclusion gives:
$$\sum_{m=0}^{4}\sum_{n=0}^4 (-1)^{m+n}\binom 4m\binom 4n\frac{(12-m-n)!}{(4-m)!(4-n)!4!}$$
That’s not going to be any easier than your approach, I guess, unless we can find some closed formula here, or quick calculation technique.
A computer program to falculate this returned $1251,$ which disagrees with your value. I will check my program.
A way to do your technique cleaner
Let $m$ be the number of letter X in the middle segment, and $n$ the number of Y in the first segment.
Then there are:
$$C_{m,n}=\binom4m\binom4n\binom{4}{4-m,4-n,m+n-4}$$
You need $m+n\geq 4.$
So this is:
$$\sum_{m=0}^4\sum_{n=4-m}^4\binom4m\binom4n\binom{4}{4-m,4-n,m+n-4}$$
Not trivial to calculate, but easier to avoid mistakes.
$$\begin{align}C_{0,4}&=1\\ C_{1,3}&=4\cdot4\cdot4=64\\ C_{1,4}&=4\cdot1\cdot 4 =16\\ C_{2,2}&=6\cdot 6\cdot 6=216\\ C_{2,3}&=6\cdot4\cdot 12 =288\\ C_{2,4}&=6\cdot 1\cdot 6=36\\ C_{3,1}&=C_{1,3} =64\\ C_{3,2}&=C_{2,3}=288\\ C_{3,3}&=4\cdot 4\cdot 12=192\\ C_{3,4}&=4\cdot 1\cdot 4=16\\ C_{4,0}&=C_{0,4}=1\\ C_{4,1}&=C_{1,4}=16\\ C_{4,2}&=C_{2,4}=36\\ C_{4,3}&=C_{3,4}=16\\ C_{4,4}&=1. \end{align} $$
This gives $1251$ also.
One of your $216$ values should be $36.$
I have four rows of value $16,$ while you only have two.
You are also missing another $36.$
The rows you are missing are:
YZZZ XXXX YYYZ $16$
YYYZ XXXX YZZZ $16$
YYZZ XXXX YYZZ $36$
This is why figuring case-by-case can still benefit from notation. It would be much more obvious if I had missed a few cases than it is when you missed a few. Also, this let me see the symmetry, $C_{m,n}=C_{n,m}.$
Appendix
$\binom k{a,b,c}$ is the multinominal, defined for $a+b+c=k,$ with value $0$ if any of $a,b,c$ is less than $0,$ and otherwise equal to:$$\frac{k!}{a!b!c!}$$
$\endgroup$ $\begingroup$When there are $k$ X's in the last $4$ positions (and therefore $4-k$ X's in the middle $4$ positions) there are $\binom 4k \binom 4{4-k} = \binom 4k^2$ ways to choose the position of the X's. After that, the Y's have $8-k$ places to go which are not in the middle and not occupied by X's; there are $\binom{8-k}{4}$ ways to choose their positions. Finally, the Z's go in the last $4$ spaces.
This gives us a sum of$$ \binom 40^2 \binom 84 + \binom 41^2 \binom 74 + \binom 42^2 \binom 64 + \binom 43^2 \binom 54 + \binom 44^2 \binom 44 $$which simplifies to$$ 1^2 \cdot 70 + 4^2 \cdot 35 + 6^2 \cdot 15 + 4^2 \cdot 5 + 1^2 \cdot 1 $$or $70 + 560 + 540 + 80 + 1 = 1251$.
In general (when there are $n$ X's, $n$ Y's, and $n$ Z's, with no X's in the first $n$ letters and no Y's in the middle $n$ letters) the number of words is given by the $n^{\text{th}}$ Apéry number: sequence A005258 in the OEIS. There is no better closed form known than a generalization of the sum above, unless you allow hypergeometric functions.
$\endgroup$ 1
