2
$\begingroup$

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}$

  • 0
    $\binom{3K}{K}\binom{2K}{K}$ is correct if D is so large you can ignore it2011-01-13
  • 0
    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.2011-01-13
  • 0
    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.2011-01-13
  • 0
    @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.2011-01-13
  • 0
    @Manjor R: But what about the middle? For example, is 012102 valid with two 1's preceding the second 0?2011-01-13
  • 0
    @Manoj R: Why is the following number invalid: 001201212? There are two zeros before the first 1.2011-01-13
  • 0
    @Trevor: It has three zeros before the second 1, so is only valid if D=2, not if D=1.2011-01-14

0 Answers 0