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.

I am thinking about following problem, but am not able to find answer.
In how many ways can a number be formed only using 3 digits (0, 1, 2) given following constraints with K and D:-
1) Each digit appears exactly K times. The total length of the number is 3*K.
2) At any given position (staring from left), the number of 0's must be at most D more than the number of 1's and number of 1's must be at most D more than number of 2's.
i.e. for K =3 and D =1 followings are some valid numbers.
012012012 010212012
The number 001201212 will be invalid as there are 2 two's before the first 1. Similarly 010122012 is invalid as there are two 1's are there before first 2.

The number 001201212 will be valid if D=2.

So far I have only found out the total number of numbers which can be formed is $\binom{3K}{K}\binom{2K}{K}$

share|improve this question
    
$\binom{3K}{K}\binom{2K}{K}$ is correct if D is so large you can ignore it –  Ross Millikan Jan 13 '11 at 13:49
    
Your examples all start with 0 and end with 2. Do you also require (as in 2) that scanning from the left there must be at least as many 0's as 1's and at least as many 1's as 2's? I think that will make counting for D=1 fairly easy. –  Ross Millikan Jan 13 '11 at 14:14
    
The case of two digits and $D=0$ is the Catalan numbers. Maybe you should review how to get that, and then try to attack your more general problem. –  Yuval Filmus Jan 13 '11 at 15:00
    
@Ross - For your second comment. Anything that start with other than zero does not fit as valid number. Similar goes for the end digit and 2. –  Manoj R Jan 13 '11 at 15:08
    
@Manjor R: But what about the middle? For example, is 012102 valid with two 1's preceding the second 0? –  Ross Millikan Jan 13 '11 at 15:48
show 2 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.