Question

Let x be a string of length n, and let y be a string of length n − k, for

1 ≤ k < n.

We wish to line up the symbols in x with the symbols in y by adding k blanks to y.

Suppose that we add two separate blocks of blanks, one of size i and one of size

k − i,

for

1 ≤ i < k.

How many ways are there to do this?

Every solution I have found on Chegg Study says the answer is n-k+1 ways; but this answer is incorrect.

Answer 1

We first determine the number of ways of creating the blocks of spaces. That only depends on the number of ways of choosing which is .

Now, we determine the number of ways of putting the two blocks of spaces in the string . The length of string is , hence the possible number of gaps is . Thus, the total number of ways of selecting gaps is and hence the total number of ways to do this is .