Formula for how many ways you can fit a string of length x into a string of length n For example, if the string we want to insert is "11" and the length of the word is 5, there are 7 ways to fit it.

*

*"11000"

*"01100"

*"00110"

*"00011"

*"11110"

*"01111"

*"11011"
To clarify you can't put a string on top of another or have part of it outside of the bounds. That would make "11001" not work because part of it is outside the bounds of the string.

I have no combinatorics experience and want to know what concepts I need to learn to be able to derive a correct formula. I saw a couple of questions that seem to be similar to this one but the explanation has too much advanced math.
 A: My first thought is to calculate for each count of inserted string ("inlay"), then sum.
So in your example, 1 copy of the inlay means there are 3 characters left over which are divided into two groups (before and after), giving $\binom {3{+}1} 1 = 4$ options, and 2 copies of the inlay means only one spare character giving $\binom {1{+}2} 2 = 3$ options.
Obviously the length of the inlay $\ell$ is required along with the total string length $s$, to give the general summation
$$\sum_{i=1}^{\lfloor s/\ell \rfloor} \binom {s-i\ell+i} i$$
In you example you didn't have zero inlays as an option, so that is reflected above, but there would only be one such.
A: Unclear whether this response will help.
Assume that the string to be fitted is of length $k$, and the overall length of the string is $n$, with $~k,n \in \Bbb{Z^+} ~: ~k < n.$
Assume (for great simplicity), that each fitted string is all $1$'s, and that any portion of the overall string (of length $n$) that is not part of a fitted string, must be all $0$'s.
So, if the fitted string is $11$, and $n = 5$, then the overall string of $11001$ is not permitted.  This is because the $5$th character, not being part of any fitted string, must be $0$.
Also assume that fitted strings are not allowed to overlap.
So, in the above example, $11110$ is okay, but $11100$ is not.  $11100$ is not permitted because here, the fitted string that begins in position 1 overlaps the fitted string that begins in position 2.
The above assumptions greatly simplify the computations.

Let $~\displaystyle c = \left\lfloor \frac{n}{k} \right\rfloor~$ (i.e. the floor function). 
That is, $c$ is the largest positive integer such that 
$\displaystyle c \leq \frac{n}{k}.$
Then, assuming that there must be at least one fitted string, you have $c$ mutually exclusive cases to examine.  That is, the number of fitted strings must be some element in $\{ ~1, ~2, ~\cdots, ~c ~\}.$
For $~r \in \{ ~1, ~2, ~\cdots, ~c ~\}, ~$ 
let $f(r)$ denote the number of different ways of placing  exactly $~r~$ fitted (non-overlapping) strings in the $n$ positions.
Then, the desired enumeration is
$$\sum_{r=1}^c f(r) = \sum_{r=1}^{\left\lfloor \frac{n}{k}\right\rfloor} f(r).$$
So, the entire problem has been reduced to enumerating $~f(r).$

If you have $r$ fitted strings, each of length $k$, then there are $A = n - rk$ additional positions that need to be zero filled.
This means that (in effect) you must select $r$ positions, from the $A + r$ available positions, sampling without replacement, where order of selection is deemed unimportant.
This can be done in $\displaystyle ~f(r) = \binom{A+r}{r} = \binom{[n-rk] + r}{r}~$ ways.

Putting this all together:

*

*$\displaystyle c = \left\lfloor \frac{n}{k} \right\rfloor~$


*$~r \in \{ ~1, ~2, ~\cdots, ~c ~\}.$


*$A = n - rk.$


*$\displaystyle f(r) = \binom{A+r}{r}.$


*The desired computation is $~\displaystyle \sum_{r=1}^c f(r).$
A: We want to fit a string of length $x$ into a string of length $n$ so $x\leq n$ or else it wouldn't make any sense. Now we consider how many possible strings we can have of the length $n-x$. If our alphabet $\mathcal X$, possible characters of our string, has size $q = |\mathcal X|$ then those are $q^{n-x}$ possibilities. Those are the possibilities for the bits other than the string we want to fit in. Now we still can "move" our string in the other one, so we have to multiply the possibilities of the other bits with the possibility of the position of the string, as the difference in length is $n-x$ those are $n-x+1$ possibilities. Therefor we have $(n-x+1)*q^{n-x}$ possibilities. However this way some of the strings you get may not be unique, take your example from above, with this method you would count "11111" four times as a string you can fit "11" in. (1. "11 111", 2. "1 11 11", 3. "11 11 1",4."111 11")
If you want to get unique strings there is no general formula as the number of strings you can have depends on the string you want to fit into the other one. For one take the string "11" to fit into a string of length 3. There you get 3 distinct strings:

*

*"110"

*"011"

*"111"

But if you want to fit the string "10" into a sting of length 3 you get 4 distinct strings, namely:

*

*"100"

*"101"

*"010"

*"110"

So you can see that it depends on the string and you just have to try it out.
Concerning your example in either case you get more than 7 possibilities as "11001" would also be a possible string.
