This is an alternative approach to compute this numbers using a computer.
The set of all words we are trying to count is of course finite, to it is a regular language. Luckily, it is easy to construct an automaton which recognizes it, so we can look at the adjacency matrix of the machine and compute its powers. The obvious automaton has $(2+n)n!$ vertices, which is pretty huge.
The actual computation of the matrix powers takes time similar to
$$\log\binom{n+1}{2}(n+2)^3n!^3$$ if one uses repeated squaring.
Can someone get an asymtotics idea of the actual result we are computing to compare this algorithm with something like Jiri's (which obviously taes time linear in the result) ?
In mathematica, we can code this with
vertices[n_] :=
Join[
{start, bottom},
Flatten[
Table[st[a, is], {a, 1, n}, {is,
Tuples[Table[Range[0, i], {i, 1, n}]]}
], 1]
]
rules[n_] :=
Join[
Table[{start, i} -> st[i, MapAt[# - 1 &, Range[n], i]], {i,
1, n}],
Table[{bottom, i} -> bottom, {i, 1, n}],
Flatten[Table[
{st[a, is], b} ->
If[a == b || is[[b]] == 0,
bottom, st[b, MapAt[# - 1 &, is, b]]],
{a, 1, n}, {b, 1, n}, {is, Tuples[Table[Range[0, i], {i, 1, n}]]}
], 2]
]
toMatrix[rs_, n_, vs_] :=
SparseArray[
Flatten@Table[
With[{src = Position[vs, v][[1, 1]],
dest = Position[vs, {v, i} /. rs][[1, 1]]},
{src, dest} -> If[src === bottom || dest === bottom, 0, 1]
], {v, vs}, {i, n}] ,
{Length[vs], Length[vs]}
]
go[n_] := Module[{vs = vertices[n], a, m},
a = Position[vs, start][[1, 1]];
Print[n, ": Matrix size : ", Length[vs]];
m = MatrixPower[
Transpose@toMatrix[rules[n], n, vs],
Binomial[n + 1, 2],
SparseArray[{a -> 1}, {Length[vs]}]
];
Total[m[[Position[vs, st[_, {0 ..}]][[All, 1]]]]]
]
Using this code, I can evaluate
go /@ Range[1..5]
to get
1, 1, 10, 1074, 1637124
in 57 seconds.
Your answer is off by a factor of $2$, seems that you forgot the double letter L.
The word GOOGOLPLEX consists of the letters O (3x), G (2x), L (2x), P (1x), E (1x) and X (1x).
So the number of possible words consisting of these letters is the multinomial coefficient
$$
\binom{10}{3,2,2,1,1,1} = \frac{10!}{3!\cdot 2!\cdot 2!\cdot 1!\cdot 1!\cdot 1!} = 151200.
$$
Best Answer
think of it as having six slots. You need to find all the ways you can stick P's A's and a Y into those slots.
Youve got 3 A's. So there are $\binom{6}{3}$ ways you can put the A's in. After that, youve got 3 slots left, and two P's. So youve got $\binom{3}{2}$ ways to put the P's in. And then finally you have $\binom{1}{1}$ way to arrange the final Y. It doesnt matter the order you do these in, you could have started with the Y, and then the P and then the A's and instead of $\binom{6}{3}\binom{3}{2}\binom{1}{1}$ youd have $\binom{6}{1}\binom{5}{2}\binom{3}{3}$ and it ends up being the same answer, which is 60.
So of those 60 possible arrangements, have many have AAA? Well if we think of "AAA" as a single letter, now we have 4 slots to put the letters "AAA", "P", "P", and "Y" into, and no matter how we arrange them "AAA" will be together. So $\binom{4}{1} \binom{3}{2} \binom{1}{1}$