# Counting the number of possibilities

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.

-
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

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