Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you want to make 500 draws, where you have 26 letters of the English alphabet in a bag. They come in equal quantities and their supply is unlimited, so that you could, for example, draw 500 "A's". How many different combinations are there for the number of these letters thus chosen?

It's hard for me to even formulate the question, and I realize the title is clumsy, so if someone can find better wording, please comment on it and I'll edit the post. But to give you an example, one combination would be 500 A's, another 498 A's, 2 B's, and yet another one, say, 467 A's, 23 C's and 10 D's.

This is not a homework question, but it was a related homework question I know how to solve that got me thinking about this. I tried to find a simple solution, but couldn't really find one, and to me the problem actually seems quite involved. Any thoughts on this?

share|improve this question
    
26 options for the first draw, 26 options for the second draw, ..., 26 options for the 500th draw. $26\times26\times\dots\times26=26^{500}$? Or am I missing something? –  crf Jan 12 '13 at 21:32
add comment

1 Answer

up vote 4 down vote accepted

This is a standard stars-and-bars problem. For $k=1,\dots,26$ let $x_k$ be the number of copies of the $k$-the letter of the alphabet that you draw. (This $x_1$ is the number of A’s, $x_2$ the number of B’s, and so on.) You’re looking for the number of solutions in non-negative integers to the equation

$$x_1+x_2+\ldots+x_{26}=500\;.$$

This is given by the binomial coefficient

$$\binom{500+26-1}{26-1}=\binom{525}{25}\approx3.641\times 10^{42}$$ or, equivalently,

$$\binom{500+26-1}{500}=\binom{525}{500}\;.$$

The reasoning is explained reasonably well in the linked article.

share|improve this answer
    
Ah, thanks! I got as far as that equation, but then I thought I'd need to go through all of those possibilities "manually", i.e. figure out how many ways there are of only one letter being represented, of one letter having 499 occurrences and another 1, of one letter having 498 occurrences and two other letters each 1 and so on... Which would, of course, be intractable :) –  Ryker Jan 13 '13 at 1:48
    
@Ryker: Yes, that would be pretty awful. You’re welcome! –  Brian M. Scott Jan 13 '13 at 1:54
    
I admire your responses in general by methodical aspect as a teacher you have been they are fully justified and understandable, especially I like combinatorics responses.I wanted to ask if you have written any book that has the Combinatorics as subject if you still have not written yet would be good to do because it will awaken great interest –  Adi Dani Jan 13 '13 at 11:53
    
@Adi: I have to apologize: I completely forgot about your question. No, I’m actually a late-comer to combinatorics: I think that I’m reasonably good at explaining the basics, but I’m also still learning. –  Brian M. Scott Jan 29 '13 at 21:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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