Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have given number of y string variables. Assignments to these y variables can be done in only following:

  1. Right hand side of the any yi variable is concatenation of y's and z's variables.
  2. Number of z variables is less than or equals to twice the number of y variables.
  3. Each yi and zi can occur at most once on the right hand side. That is y1 = z1.y1.z2.y2.z3 and y2 = y2 is illegal as y2 occurs twice.
  4. No two y or z variable can't occur consecutively that is y1 = z1.z2 is not possible. It can be y1 = z1 only.

So for two y variables, y1 and y2, these are the only 11 possibilities:

1. y1 = z1.y1.z2
   y2 = z3.y2.z4   (This is same as y1 = y1, y2 = y2 as you can consider z1=z2=z3=z4=epsilon(empty string), y1 = z1.y1 , y2 = z3.y2 and so on)

2. y1 = z1.y2.z2
    y2 = z3.y1.z4

3. y1 = z1.y1.z2.y2.z3
   y2 = z4

4. y1 = z1.y2.z2.y1.z3
   y2 = z4

5. y1 = z1
   y2 = z2.y1.z3.y2.z4

6. y1 = z1
   y2 = z2.y2.z3.y1.z4

7. y1 = z1.y1.z2
   y2 = z3

8. y1 = z1.y2.z2
   y2 = z3

9. y1 = z1
   y2 = z2.y1.z3

10. y1 = z1
     y2 = z2.y2.z3

11. y1 = z1
   y2 = z2 

I want to calculate number of possible assignments given the number of y variables.

share|cite|improve this question
It seems that where it says "consequently" you mean "consecutively"? – joriki Feb 16 '13 at 11:47
Are permutations among $z_i$ variables not allowed? For example, is $y_1=z_1$, $y_2=z_2$ different from $y_1=z_2$, $y_2=z_1$? Also, is $y_1=y_1 z_1 y_2$, $y_2=z_2$ not allowed? Does the consecutive requirement extend across LHS and RHS? – polkjh Feb 16 '13 at 12:57
y1=z1, y2=z2 is same as y1=z2, y2=z1. And y1=y1z1y2, y2=z2 is same as y1 = z1.y1.z2.y2.z3 ,y2 = z4. LHS can be only single y variable. – user1280282 Feb 16 '13 at 13:03
up vote 1 down vote accepted

Let the number of $y$ variables be $n$. Suppose exactly $r$ variables $y_i$ are used in the RHS (over all the assignments). These $r$ can be chosen in $\binom{n}{r}$ ways. Now these $r$ variables can be distributed among the $n$ assignments, with order, in $\frac{(n+r-1)!}{(n-1)!}$ ways. And we can see that once this is done, all the assignments are fixed. So the total number of assignments will be

$$ \sum_{r=0}^n \binom{n}{r} \frac{(n+r-1)!}{(n-1)!} $$

share|cite|improve this answer

Your Answer


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.