Words Counting and Ranking

Question

All words which contain $2, 3, 4$ or $5$ English letters (A to Z) are listed alphabetically. In each word, the letters can be repeated, but any two adjacent letters must be distinct. So, the first word is "AB", and the last one is "ZYZYZ".

• What is the total number of words in the list?
• What is the rank of the word "PAPER"?
• What is the $13554$th word?

I have answered the first part as follows;

Total number of words $=26(25^1+25^2+25^3+25^4)$

$=26(25+625+15625+390625)=26(406900)=10579400$ words.

Am I right for this part?

How to solve the second and the third part?

Answer 1

The first part is correct. Denoting the rank of a word $w$ with $\mathrm{rk}(w)$ we know according to OP's result: \begin{align*} \mathrm{rk}(AB)=1,\qquad \mathrm{rk}(ABA)=2, \qquad\ldots,\qquad\mathrm{rk}(ZYZYZ)=10\,579\,400 \end{align*}

We will also use the lexicographic order of the letters $A-Z$ and list them for convenience.

\begin{array}{ccccccccccccc} A&B&C&D&E&F&G&H&I&J&K&L&M\\ 1&2&3&4&5&6&7&8&9&10&11&12&13\\ \\ N&O&P&Q&R&S&T&U&V&W&X&Y&Z\\ 14&15&16&17&18&19&20&21&22&23&24&25&26\\ \end{array}

Rank of the word "PAPER":

We get the rank of the word $PAPER$ by successively calculating the rank of words which are at the end or the beginning of blocks since this can be determined easily. Nevertheless this approach needs somewhat careful bookkeeping.

We obtain \begin{align*} \mathrm{rk}(OZYZY)&=15(25+25^2+25^3+25^4) =6\,103\,500\tag{1}\\ \mathrm{rk}(\color{blue}{PA})&=6\,103\,501\tag{2}\\ \mathrm{rk}(PAOZY)&=\mathrm{rk}(PA)+14(1+25+25^2)\\ &=6\,103\,501+9\,114 =6\,112\,615\tag{3}\\ \mathrm{rk}(\color{blue}{PAP})&=6\,112\,616\\ \mathrm{rk}(PAPDZ)&=\mathrm{rk}(PAP)+4(1+25)\\ &=6\,112\,616+104 =6\,112\,720\tag{4}\\ \mathrm{rk}(\color{blue}{PAPE})&=6\,112\,721\\ \mathrm{rk}(\color{blue}{PAPER})&=\mathrm{rk}(PAPE)+17=6\,112\,738\tag{5} \end{align*} We conclude the rank of the word "$\color{blue}{PAPER}$" is $\color{blue}{6\,112\,738}$.

Comment:

• In (1) we calculate the number of valid words which have first letter $A-O$. The last word in this block is $OZYZY$. Note that the letter $O$ is the '$15$'-th letter in the alphabet. So, we take the factor $15$ and the rest is calculated as in OP's first part.

• In (2) we note that $PA$ is the word immediately following $OZYZY$.

• In (3) we start from $PA$ and count all words which are before $PAP$.

• In (4) we start from $PAP$ and count all words which are before $PAPE$.

• In (5) we finally come to $PAPER$ by noting that $R$ is the $18$-th letter in the alphabet. Since the letter $E$ in $PAPER$ is immediately left to $R$ it is to exclude and we have to add $17$ to $\mathrm{rk}(PAPE)$ to obtain $\mathrm{rk}(PAPER)$.

The $13\,554$-th word:

Note, the rank function is a bijection from the valid words to the corresponding rank. So, here we have to do some kind of inverse steps in order to determine the valid words.

We start by calculating the number of words when fixing the leftmost two, three and four letters. Wlog we take $A,B$ as letters which are fixed.

We obtain \begin{align*} \mathrm{rk}(\color{blue}{A}ZYZY)-\mathrm{rk}(\color{blue}{A}B)+1 &=25+25^2+25^3+25^4=406\,900\\ \mathrm{rk}(\color{blue}{AB}ZYZ)-\mathrm{rk}(\color{blue}{AB})+1 &=1+25+25^2+25^3=16\,276\\ \mathrm{rk}(\color{blue}{ABA}ZY)-\mathrm{rk}(\color{blue}{ABA})+1 &=1+25+25^2=651\\ \mathrm{rk}(\color{blue}{ABAB}Z)-\mathrm{rk}(\color{blue}{ABAB})+1 &=1+25=26\\ \end{align*}

We can now represent the rank $13\,554$ as \begin{align*} 13\,554=\color{blue}{0}\cdot406\,900+\color{blue}{0}\cdot161\,276 +\color{blue}{20}\cdot651+\color{blue}{20}\cdot26+\color{blue}{14} \end{align*} and from the coefficient tupel $(0,0,20,20,14)$ we can now derive the wanted word. But we have to be careful, since we have to respect the rules for the valid words.

We derive \begin{align*} \mathrm{rk}(\color{blue}{AB})&=1&(\color{blue}{0},\color{blue}{0},20,20,14)\tag{6}\\ \mathrm{rk}(ABUZY)&=\mathrm{rk}(AB)+20\cdot651\\ &=1+13\,020\\ &=13\,021&(0,0,\color{blue}{20},20,14)\tag{7}\\ \mathrm{rk}(\color{blue}{ABV})&=13\,022\tag{8}\\ \mathrm{rk}(ABVTZ)&=\mathrm{rk}(ABV)+20\cdot26\\ &=13\,022+520\\ &=13\,542&(0,0,20,\color{blue}{20},14)\tag{9}\\ \mathrm{rk}(\color{blue}{ABVU})&=13\,543\\ \mathrm{rk}(\color{blue}{ABVUK})&=13\,554&(0,0,20,20,\color{blue}{14})\tag{10} \end{align*} We conclude the $\color{blue}{13\,554}$-th word is "$\color{blue}{ABVUK}$".

Comment:

• In (6) the first coefficient $0$ addresses the left-most letter of the wanted word. The value $0$ tells us to take the first letter $A$.

  The second coefficient addresses the second letter when starting from left. The value $0$ tells us to take the first valid letter. Since the wanted word starts with $A$, the first valid letter is $B$.

  The wanted word starts therefore with $AB$.

• In (7) the coefficient $20$ tells to take all words with the $20$-th valid letter at the third position. Since the $20$-th letter is $T$ and we have to ignore the letter $B$ at the left next position, we have to take the $21$-st letter $U$. The highest-ranked valid word with $U$ at the third position is $ABUZY$.

• In (8) we take the next word $ABV$ from which we now know it has rank $13\,022$.

• In (9) the coefficient $20$ tells to take all words with the $20$-th valid letter at the fourth position. This time there is no obstacle to take the $20$-th letter $T$ of the alphabet. The highest-ranked valid word with $T$ at the fourth position is $ABVTZ$.

• In (10) we see from the line before that we have to take $11$ to go from $13\,543$ to $13\,554$. So, we finally find $ABVUK$ as the wanted word. Note that we added $11$ instead of $14$ since there was an increment by one at each step of $AB$, $ABV$ and $ABVU$.

Note: I've written some lines of code in R in order to check the results and some intermediate steps.

############################################################################
#
#  MSE 2976421
#
############################################################################
#
#  generate all combinations of length "len"
#  of elements given in "v"
#
combinations <- function(v,len) {
  cur_v <- v
  if (len > 1) {
    for (i in 1:(len-1)) {
      next_v <- as.vector(outer(cur_v, v, paste, sep=""))
      cur_v <- next_v
    }
  }
  return(cur_v)
}

############################################################################
#
# print rank 
#
print_rank <- function(w, rank) {
  print(paste("rank(",w,") = ",rank,sep="", collapse=NULL))
}

###########################################################################
#
# main part
#

v <- c(toupper(letters))

w <- NULL
w_all <- NULL
rk <- NULL

for (len in c(2:5)) {

  print(paste("generating words of length",len, "..."))

  # generate all combinations of length "len"
  w <- combinations(v,len)

  # filter out invalid words
  for (c in c(toupper(letters))){
    c2 <- paste(c,c,sep="", collapse=NULL)
    w <- w[!grepl(c2,w)]
  }

  # collect valid words in "w_all"
  w_all <- c(w_all,w)
}

print("sorting valid words ...")
w_all <- sort(w_all)

#######################################################################
#
# checks
#

print("checks ...")

print(paste("number of valid words:",length(w_all)))
w <- "ZYZYZ"
rk <- match(w,w_all)
print_rank(w,rk)

#
# OP's second part
#

for (w in c("ZYZYZ",
            "OZYZY",
            "PA",
            "PAOZY",
            "PAP",
            "PAPE",
            "PAPER")) {
              rk <- match(w,w_all)
              print_rank(w,rk)
}

#
# OP's third part
#

for (w in c("AB",
            "ABA",
            "ABAB",
            "AZYZY",
            "ABZYZ",
            "ABAZY",
            "ABABZ")) {
  rk <- match(w,w_all)
  print_rank(w,rk)
}

for (w in c("AB",
            "ABUZY",
            "ABV",
            "ABVTZ",
            "ABVU",
            "ABVUK")) {
  rk <- match(w,w_all)
  print_rank(w,rk)
}

Output:

[1] "checks ..."
[1] "number of valid words: 10579400"
[1] "rank(ZYZYZ) = 10579400"

[1] "rank(OZYZY) = 6103500"
[1] "rank(PA) = 6103501"
[1] "rank(PAOZY) = 6112615"
[1] "rank(PAP) = 6112616"
[1] "rank(PAPDZ) = 6112720"
[1] "rank(PAPE) = 6112721"
[1] "rank(PAPER) = 6112738"

[1] "rank(AB) = 1"
[1] "rank(ABA) = 2"
[1] "rank(ABAB) = 3"
[1] "rank(AZYZY) = 406900"
[1] "rank(ABZYZ) = 16276"
[1] "rank(ABAZY) = 652"
[1] "rank(ABABZ) = 28"

[1] "rank(AB) = 1"
[1] "rank(ABUZY) = 13021"
[1] "rank(ABV) = 13022"
[1] "rank(ABVTZ) = 13542"
[1] "rank(ABVU) = 13543"
[1] "rank(ABVUK) = 13554"

Answer 2

P is$16^{th}$ alphabet.
So, take all words beginning with A to O, i.e. $15\cdot(25+25^2+25^3+25^4)$

Now, for words beginning with P:
take all 2,3 and 4 letter words, i.e. $(25+25^2+25^3)$

For 5 letter words:
$1^{st}$ will be PABAB.
So, fix A at $2^{nd}$ position and count for last 3.

We want P at $3^{rd}$, so, take all alphabets from B to P, i.e. 15 letters

We got PAP_ _. Now, for $4^{th}$ position, we have A,B,C,D and then E; so, 5 letters.

Now its PAPE_. Count from B to R for last one, i.e. 17 letters.

Add all: $$15\cdot(25+25^2+25^3+25^4)+(25+26^2+25^3)+15+5+17$$

For C:
we see that number of words starting with A upto the form A_ _ _ _ are $25+625+20\cdot625=15625$
So, definitely, it will be a 4 letter word starting with A.

If we fix 2nd place with W, we get AWAB as $13150^{th}$ word.
Then trying for Q at 3rd place, we ge AWQZ at $13150+16\cdot25=13550^{th}$ place.

Only 4 more words to count...
AWRA, AWRB, AWRC and AWRD