3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I agree with your work for the first part. I think what you need is that the words are ordered in lexicographic order, that is, dictionary order, so they are listed AB, ABA, ABAB, ABABA, ABABC, ABABD... Then their ranks are $1, 2, 3, 4, 5, 6\cdots$. $\endgroup$ – Kevin Long Oct 29 '18 at 17:50
  • $\begingroup$ True, that is what I meant by alphabetical order, (dictionary order). $\endgroup$ – Hussain-Alqatari Oct 29 '18 at 17:52
2
$\begingroup$

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"
$\endgroup$
  • $\begingroup$ I really appreciate you for this answer, it convinced me more than omega's answer. But I am confused that omega said the 13554th word is AWRD, I do not know really which one is correct, but I think your answer is the correct one. $\endgroup$ – Hussain-Alqatari Nov 3 '18 at 12:01
  • $\begingroup$ @Hussain-Alqatari: Thanks for the credit. I'll provide some reasoning to omegas answer soon. $\endgroup$ – Markus Scheuer Nov 3 '18 at 12:20
  • $\begingroup$ @Hussain-Alqatari: I've added comments to omegas answer indicating some discrepancies. $\endgroup$ – Markus Scheuer Nov 3 '18 at 14:24
  • $\begingroup$ @Hussain-Alqatari: I've added the code which might be useful. $\endgroup$ – Markus Scheuer Nov 4 '18 at 10:45
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ this counting ia a bit difficult at boundary values...hope i did not miss any... $\endgroup$ – idea Oct 29 '18 at 18:17
  • $\begingroup$ It seems difficult to understand. Can we find the rank of the word PAPER in other way? And how to solve the 3rd part of the question? $\endgroup$ – Hussain-Alqatari Oct 29 '18 at 18:18
  • $\begingroup$ actually...it wud have been much easier if they asked only letters of PAPER are arranged...in this case, counting may be an only solution $\endgroup$ – idea Oct 29 '18 at 18:20
  • $\begingroup$ for 3rd part, we need to count again for number of words with a given letter...here we are sure it starts with ABW, but need to count further $\endgroup$ – idea Oct 29 '18 at 18:21
  • $\begingroup$ Considering the words that start with "A" only; that have two letters = 1 x 25 = 25 that have three letters = 1 x 25 x 25 = 625 that have four letters = 1 x 25 x 25 x 25 = 15625 that have five letters = 1 x 25 x 25 x 25 x 25 = 390625 So, there are (25+625+15625+390625) or 406900 words start with "A" Therefore, the 13554th word must start with "A". $\endgroup$ – Hussain-Alqatari Oct 29 '18 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.