I have a string 1111 and I know that 1 can be converted to 1, 10 or 100 but the string will be still 4 symbols length, so actually each 0 sign replaces next symbol.
So it could be
1111
1110
1101
1011
1010
1001
1100
How to count all possible convertions to limited string size?
I counted that:
first symbol `1` could be converted to `1`, `10` or `100`.
second symbol `1` could be converted to `1`, `10`or `100`.
third symbol `1` could be converted to `1`, `10`.
fourth symbol `1` could be converted to `1`.
So I have some map of size of convertions for each position:
1 -> 3
2 -> 3
3 -> 2
4 -> 1
And with that map I know that there are 3 permutations with 10 , 2 permutations with 100 and 1 permutation with 1, but I can't catch mix of permutations.
Like if there were 5 initial symbols 11111 and the same convertions, so I didn't catch mixes like
10100
10010
10101
10110
11010
How to catch them?
But I can't solve it in this direction.
Can you help me with that?
Firstly, how to do it using my map of convertions.
And if it is a dead end, then how to do it with other solutions?
UPD Trying to rephrase it.
I have an alphabet {1, 10, 100} and I need to count all possible permutations that are limited to the total symbol length of 4.
How to do it with knowing amount of permutations for each symbol ? Like
first symbol `1` could be converted to `1`, `10` or `100`.
second symbol `1` could be converted to `1`, `10`or `100`.
third symbol `1` could be converted to `1`, `10`.
fourth symbol `1` could be converted to `1`.
Assuming you mean, how many strings of length $n$ can be formed by freely concatenating 1, 10, and 100, the answer is, the coefficient of $t^n$ in the power series for $$\begin{align*}Z(t)&=\frac1 {1-(t+t^2+t^3)}\\&=1+t+2t^2+4t^3+7t^4+13t^5\cdots.\end{align*}$$ This can be seen by noting that any legal concatenation is either the empty string, the string 1 followed any legal concatenation, the string 10 followed by any legal concatenation, or the string 100 followed by any legal concatenation, leading to the equation $$\begin{align*}Z(t)&=1+tZ(t)+t^2Z(t)+t^3Z(t)\\&=1+(t+t^2+t^3)Z(t)\end{align*},$$ whose solution is above.
Note also that in this case each legal concatenation is uniquely parseable: the language $\{1,10,100\}^*$ is uniquely decodable, this means that to count legal concatenations is to count distinct parsings. Unlike what happens with $\{1,11\}^*$, say, where strings such as 111 have multiple parsings. See discussions of the Chomsky–Schützenberger theorem for further theory, or pp. 36-38 of Shannon and Weaver, The mathematical theory of communication for a similar example.
Similarly, the number of strings of length $n$ which can be formed by freely concatenating 1 and 10, the answer is the coefficient of $t^n$ in the power series expansion of $$\begin{align*}Z(t)&=\frac{1}{1-(t+t^2)}\\&= 1+t+2t^2+3t^3+5t^4+8t^5+\cdots\end{align*}$$ and so on.