# 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

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}\;.$$