1

I am trying to calculate the number of possible substrings with the maximum length n in the dictionary of size $r$. I would think that it should be the number of total subsets (of all sizes) in set of $3$: $2^3=8$ but in the dictionary $\{A,B,C\}$ for example, I've counted $19$:

AAA BBB CCC ABC CBA BCA BAC AA AB AC BB BA BC CC CA CB A B C

Where am I wrong?

vic
  • 11
  • Does the length of the alphabet dictates the maximum length of a word in the dictionary ? I mean why would "AAAA" not be a word ? – Furrane Mar 21 '18 at 20:33
  • Isn't it true that $AAA$, $AA$, and $A$ all represent the subset ${ A }$? – diligar Mar 21 '18 at 23:29
  • You are right - my question is incomplete. What I am trying to ask is number of permutations of the string with max size of k when the number of letters is r – vic Mar 22 '18 at 07:20

1 Answers1

1

Suppose your alphabet has $n$ letters. Then there will be $ n^k$ words of length $k$. Sum that from $1$ to $r$ if $r$ is the maximum length of a word.

In your question you missed many of the three letter words (for example, AAB). If you write them in alphabetical order you will see the pattern.

Your guess about $2^3$ is right when you are counting subsets, but in a dictionary the order in which the letters appear in a word matters.

Related: Finding total possible permutations of n elements, in strings of n length (Math-Challenged person!)

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199