# How many combinations of $A,B,C,D,\ldots$ and $1,2,3,4,\ldots$ such that there are at least $n$ letters before the $n^\text{th}$ number

So, given $A,B,C,D,E,\ldots$ etc (up to $n$ letters) and $1,2,3,4,5,\ldots$ (up to $n$ numbers) where $n$ is the same for both (same number of letters as numbers)

How many unique sequences of letters and numbers can be formed such that for the $i^\text{th}$ number in the sequence, there are at least $i$ preceding letters.

So for example

• $A1B2C3$
• $AB12C3$
• $ABC123$

But not

• $1ABC23$
• $AB123C$
-
The examples are rather confusing... The 'i-th' number means the position of the number in the sequence or to the number value? A2B1 is valid? –  leonbloy May 5 '12 at 21:24

## 1 Answer

I'm going to take a wild guess here and assume that of the two properties of your examples that aren't mentioned in the question, that they all contain all the letters and numbers exactly once and that they contain them all in order, the first one is meant to hold for all the sequences you're interested in and the second one is incidental.

In that case, all the letters and all the numbers can be permuted arbitrarily, which gives a factor of $n!^2$, and this has to be multiplied by the number of ways of arranging $n$ X's and $n$ Y's such that no initial segment of the sequence has more Y's than X's. This latter number is the $n$-th Catalan number $C_n$, so the total number of sequences is

$$n!^2C_n=n!^2\frac1{n+1}\binom{2n}n=\frac{(2n)!}{n+1}\;.$$

-