How many possible strings exist given base string S and character C?

Question

We're given a base string "abcdefghijklmnopqrstuvwxyz0123" of length 30, and a new character "_" of length 1.

How many possible ways can our character be placed (or excluded) in the string without exceeding a total string length of 40?

Valid strings, length:

• "abcdefghijklmnopqrstuvwxyz0123", 30
• "a_b_c_d_e_f_ghijklmnopqrstuvwxyz0123", 36
• "a_b_c_d_e_f_g_h_i_j_klmnopqrstuvwxyz0123", 40
• "a_b_cd_e_fghijklmno_pq__rs_t_uvwx_yz0123", 40
• "abcdefghijklm__________nopqrstuvwxyz0123", 40

Invalid strings, length:

• "_____abcdefghijklmnopqrstuvwxyz0123_____", 40 (external characters)
• "a_b_c_d_e_f_g_h_i_j_k_lmnopqrstuvwxyz0123", 41 (exceeds given length)

To solve this problem, I began by imagining each possible space between characters in the string as possible homes for the character. 29 of these spaces exist.

• a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3

Because of the length limit of 40 and 30 existing characters, we can place at most, a total of 10 new characters. There are then 29 ways to place our first character, 28 ways to place the second, 27 ways to place the third, and so on until we've placed all 10 characters.

For this, I believe the number of possible strings to be $\frac{29!}{19!}$ when we exhaust the limit of 10 characters. Because we don't have to exhaust that limit, we can theoretically use only 9, 8, 7, and so on. To account for those strings, I sum the combinations for each with

$$\sum_{i=0}^{10}\frac{29!}{(29-i)!}$$

I believe my reasoning to be correct up until this point, where I get a little confused with possibilities where one new character is immediately next to another new character, such as with the following

• "a_b_cd_e_fghijklmno_pq__rs_t_uvwx_yz0123", 40
• "abcdefghijklm__________nopqrstuvwxyz0123", 40

I've considered treating consecutive new characters as a sort of super character, but the total number of possible strings quickly increases at a rate that seems a lot bigger than I first imagined the final result being.

If someone could point me in the right direction or provide a complete solution, I'd be very thankful!

Cheers, Taylor

Answer 1

This is a stars-and-bars problem in disguise. Consider an empty space with "a" at one end and "3" at the other. If you use ten underscores, then you have to place those ten underscores, plus the remaining 28 letters/numbers, into the space between "a" and "3"; there are clearly $\binom{28+10}{10}$ ways to do this. So all you need to do is to add up $$\binom{28+i}{i}$$ for $i$ from $1$ to $10$.

Alternatively, as JMoravitz suggested in a comment above, mark the ends of the region by "a" and some unused symbol, say "!". Then you must place 29 letters/numbers, plus all ten underscores, into this space, in $\binom{29+10}{10}$ ways. Any underscores that end up to the right of the "3" are unused in the final string, which then extends from "a" to "3".