Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$
share|improve this question
    
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 1

up vote 4 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.