# Number of Modifications to a String

Suppose Elmo starts with the string "SesameStreet" and then applies one modification to it, where a modification consists of inserting a number at some position. This process can produce a string like "Sesa5meStreet".

What if Elmo applies two modifications? This process can produce a string like "9Sesa5meStreet". How many different strings can Elmo create?

-
Can Elmo apply two modifications next to each other, such as Sesame99Street? – Austin Mohr Nov 4 '12 at 4:15
yes,I thinks so – user1667315 Nov 4 '12 at 4:20
Seems identical to a homework question (www.cs.uwm.edu/classes/cs317/HW/hw7-ver2.pdf), due in a few days. – Douglas S. Stones Nov 4 '12 at 5:35
I take it here that a modification involves just inserting a single digit? The question says "number", which could mean any number of digits, or even a non-integer. – user22805 Nov 4 '12 at 9:05
rolled back the edit to give the answers context. – robjohn Nov 13 '12 at 21:54

There are $13$ "interletter gaps" in SesameStreet, of which $11$ are genuinely between letters, and the other $2$ are at the two ends. We can either (i) choose $1$ of these gaps, and put in it any string of two digits or (ii) choose $2$ of these gaps, and insert a digit into the leftmost chosen gap, and then a digit into the other gap.

For type (i), there are $\binom{13}{1}$ ways to choose the gap, and for each such way we can enter any of the $(10)(10)$ sequences of two not necessarily distinct digits.

For type (ii), there are $\binom{13}{2}$ ways to choose the two gaps, and for each way there are $(10)(10)$ ways to fill the two gaps with digits.

So we get a total of $$\binom{13}{1}(100)+\binom{13}{2}(100)$$ ways to do the job. Calculate. We have $\binom{13}{1}=13$ and $\binom{13}{2}=78$. This gives a total of $9100$.

-

There are thirteen places to insert a number and we need two of them (possibly choosing the same place twice). This known as a combination with repetition. In our case, there are $$\binom{13 + 2 - 1}{2} = \binom{14}{2} = 91$$ ways to choose the locations for the modifications.

For each such choice of positions, there are $10$ choices for the first modification and $10$ choices for the second, giving $10 \cdot 10 = 100$ modifications total.

Finally, we have $$91 \cdot 100 = 9,100$$ total possible modifications.

-
 You have double counted the cases where the two numbers are the same. – Ross Millikan Nov 4 '12 at 4:30 why not there be 14 places to insert a number ?! – user1667315 Nov 4 '12 at 4:35 @RossMillikan I think there is no issue with overcount. By using combination with repetition, I count each selection of positions exactly once and count each of the 100 possible two-digit modifications exactly once. – Austin Mohr Nov 4 '12 at 4:43 I see why allowing the repetition doesn't double count-in a sense the two places are already different. – Ross Millikan Nov 4 '12 at 4:47 WOW , Thanks man very help full – user1667315 Nov 4 '12 at 4:47
show 2 more comments