0
$\begingroup$

first let me add a disclaimer, my question is not a duplicate of Find the number of 3-letter words that can be made with letters in alphabetical order. I am learning combinatorics from "Emunerative Counting by George Martin".
I am listing down my solution vs solution given in book, I fail to see how it is a case of combination with repetition. Any help in helping me understand is greatly appreciated.
My Approach
We pick four distinct letters and then for each of them there is only one out of twenty-four which is in alphabetical order, so the solution should be:
$${26 \choose 4}.1$$ Author's solution (copied verbatim)

$${{26 + 4 -1} \choose 4} *1$$
since there is only 1 way to put 4 given letters in alphabetical order.


Please help me understand how is this a case of combination with repetition? Or why is my approach wrong. Thanks

P.S The question given in the book is (clarifying as per Ross's answer)

How many 4-letter words are there with the letters in alphabetical order?

$\endgroup$
  • 1
    $\begingroup$ Can you repeat letters in a word? Is "AAAA" an accettable word? $\endgroup$ – zar Jun 29 '18 at 20:48
  • $\begingroup$ @zar I don't know how to figure out whether the assumption we are making is true or not. I have posted the exact question from Book now, could you help me in figuring out how to determine that repetition is allowed? Thanks! $\endgroup$ – humblecoder Jun 29 '18 at 20:58
1
$\begingroup$

I assume repeated letters are acceptable.

There are:

  • One distinct letter: $26$ words made from a single letter (AAAA, BBBB, ..., ZZZZ), and each is of course in alphabetical order: total = 26
  • Two distinct letters: There are two classes of words with two distinct letters, having 2 As and 2 Bs, or having 1A and 3Bs, etc. Consider the 2-and-2 case. There are $(26 \times 25)/2$ candidate words made from the two-and-two distinct letters, where the possible words that can be selected to be in alphabetical order are of the form $(AABB, AACC, ..., AAZZ, BBAA, ....)$. Then there are the 3-and-1 cases: $(AAAB, AAAC, BBBA, ...)$. The total number of the first type and then we must divide this number by $2$ to get the word in alphabetical order: $(AABB, BBAA) \to AABB$. Then for the three-and-one cases there are analogously $26 \times 25 \times 2/2$. total = 975
  • Three distinct letters: $26 \times 25 \times 24$ choices of three distinct letters $(ABC, ABD, ...)$ and for each of these we multiply by $3$ to choose which letter is duplicated $(ABC \to AABC, ABBC, ABCC)$. For each of these three letters we must divide by $3!$ to find the single word that is in alphabetical order, so $(26 \times 25 \times 24) 3/6$ total = 7800
  • Four distinct letters: $(26 \times 25 \times 24 \times 23)/4!$ made from four distinct letters. 26 choices for the first letter, 25 for the second, etc. (ABCD, ACBD, ...). There are 4! words made from the exact set of 4 distinct letters, so we must divide the total by 4! to get the single word that is in alphabetical order. Thus: $(26 \times 25 \times 24 \times 23)/4!$ total = 14950

Grand total: 23,751

This answer agrees with the textbook, i.e., ${29 \choose 4} = 23,751$. (Alas, I don't quite see the author's logic in his formula, though.)

$\endgroup$
  • $\begingroup$ Are you missing words like $AAAB$ and $ABBB$? $\endgroup$ – Daniel Schepler Jun 29 '18 at 22:11
  • $\begingroup$ I'm fixing this... $\endgroup$ – David G. Stork Jun 29 '18 at 22:14
  • $\begingroup$ Thanks for such detailed reply. $\endgroup$ – humblecoder Jun 30 '18 at 17:01
  • $\begingroup$ David, the author uses the formula for combinations with repetitions $\endgroup$ – zar Jul 2 '18 at 0:04
3
$\begingroup$

You are picking four distinct letters to form the word. The author is allowing repeated letters, so you do not count AAAA or AABC but the author does. You did not quote the question so it is not clear whether repeated letters are allowed.

$\endgroup$
  • $\begingroup$ Thanks for replying. The text of my question is exactly same as the one mentioned in book, Apologies for not clarifying it in the first place. $\endgroup$ – humblecoder Jun 29 '18 at 20:54
  • $\begingroup$ I have also added the exact question from the book. My question now is how does one determine whether or not to assume if repetition of letters is allowed. $\endgroup$ – humblecoder Jun 29 '18 at 20:56
  • 2
    $\begingroup$ @humblecoder In my view aaaa is in this context a 4 letter word. The term "distinct" lacks. $\endgroup$ – drhab Jun 29 '18 at 21:04
  • $\begingroup$ A word can have repeated letters, so I agree with @drhab $\endgroup$ – zar Jun 29 '18 at 21:38
  • $\begingroup$ @drhab thanks for reply, what you said makes sense to me, I want to ask if in general if the word distinct is missing, could we safely assume repetition is allowed? sorry if it sounds dumb but I am trying to learn combinatorics in depth, and as such is often confused between the assumptions to be made. $\endgroup$ – humblecoder Jun 29 '18 at 21:42
2
$\begingroup$

Most probably you are expected to find the number of sums:$$n_A+\cdots+n_Z=4$$For this you can use stars and bars. There are $4$ stars and $25$ bars, so...

$\endgroup$

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.