# Prove that an $n$-length string has $2^n$ i18n-style abbreviations

An i18n-style abbreviation is one in which multiple letters are shortened to that number of letters. E.g., "internationalization" -> "i18n" ("nternationalizatio" is substituted with its length 18). Other abbreviations include "in17n", "i17on", "in16on", etc. I see a pattern in which words with at least 3 characters have $2^{n-2}-1$ different abbreviations. E.g.,

• hat - h1t (1 possible abbreviation)
• code - co1e, c1de, c2e (3 abbreviations)
• words - wor1s, wo1ds, wo2s, w1rds, w1r1s, w2ds, w3s (7 abbreviations)
• active - acti1e, act1ve, act2e, ac1ive, ac1i1e, ac2ve, ac3e, a1tive, a1ti1e, a1t1ve, a1t2e, a2ive, a2i1e, a3ve, a4e (15 abbreviations)

The pattern is apparent, but how do I prove that this is the case?

• Check out this link. It might be helpful. Jul 12, 2014 at 17:30

The proof should be easy once you've modeled the problem sufficiently precisely. Your examples demonstrate some assumptions about possible abbreviations that you don't describe in the accompanying text.

• The first and last letter are always kept unchanged. For example, hat can only be abbreviated h1t (or left unabbreviated).
• If successive letters are abbreviated, then they must all be included in the same number. An equivalent way to state this is that you cannot have consecutive numbers in an abbreviation. For example, code cannot be abbreviated as c11e: if both the o and the d are abbreviated then the number 2 must be used to replace them both together.
• You seem to waver as to whether the original word counts as a (trivial) abbreviation. I'll include it as an abbreviation in my answer.

Under these rules, an abbreviation is uniquely determined by the set of letters to abbreviate. A letter that can be abbreviated is determined by its position, which is an index between $2$ and $n-1$ where $n$ is the number of letters in the word. Therefore, for a word of length $n \ge 2$, the set of possible abbreviations is uniquely determined by the set of indices in the range $[2,n-1]$ to abbreviate. In mathematical terms, there is a bijection between abbreviations of a given word of length $n$ and the set of all subsets of $[2,n-1]$.

The set of integers $[2,n-1]$ has $n-2$ elements. The set of its subsets $\mathscr{P}([2,n-1])$ has $2^{n-2}$ elements. Given the bijection above, the number of abbreviations is also $2^{n-2}$.

Follow-up exercise (significantly harder): some of these abbreviations are useless, in that they are no shorter than the original. There is one trivial abbreviation where all the letters are kept, but there are also abbreviations which involve the replacement of a single letter by 1, such as h1t (no shorter than hat) or a2i1e (no shorter than a2ive). How many abbreviations actually shorten the word?

• I deleted my answer (proof by induction) after realising that you just need to look at the subset of deleted characters and then finding you'd already written it up. Jul 12, 2014 at 17:56