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.

The order of the letters does not matter, so:

ABALNKM

is the same as

ALMKNBA

bonus points

How would I determine the number of sets where any letter can only be repeated a maximum of 4 times?

share|improve this question
    
For the first question, you seem to be allowing "multisets" since there are two occurrences of A. Is that what you intend? For the bonus question (homework?) it is easiest to remove the cases of $5$ or more the same. To count this, break up into cases: (i) $5+2$; (ii) $5+1+1$; (iii) $6+1$; (iv) $7$. –  André Nicolas Apr 27 '12 at 18:48
    
Yes, A being in there twice was what I intended. This is not homework despite my phrasing. I would prefer 4 or 3 duplicates max but 5 wouldn't be the end of the world –  Abe Miessler Apr 27 '12 at 18:51
    
There is not much difference in the difficulty of counting. Assume we are using the $26$-letter English alphabet, adjustment is easy for other ones. To count the $5+2$, there are $26$ ways to choose what we have $5$ of, and for each there are $25$ ways to count what we have $2$ of, total $(26)(25)$. For $5+1+1$, there are $26$ ways to choose what we have $5$ of, and for each there are $\binom{25}{2}$ ways to count what we have $1$ each of (kind of tricky). I assume you know total number of choices with no restrictions. Work on it, I will be away for a while. –  André Nicolas Apr 27 '12 at 18:59

2 Answers 2

up vote 2 down vote accepted

Although you are undoubtedly familiar with some of what follows, we review things for completeness. In particular we will see that there is a simple way to count the number of choices if no restrictions are made. Then dealing with your restriction is relatively painless.

First we count the number of ways to choose $7$ letters, repetitions allowed. For definiteness, we assume that we are dealing with a $26$-letter alphabet. Modification to deal with an alphabet with other than letters, or multisets of size other than $7$, is straightforward.

Think of the $26$ letters of the alphabet as bins. We want to place $7$ identical marbles in these bins. The translation to choices of $7$ letters is immediate. For example, ABALNKM corresponds to putting $2$ marbles into bin A, and $1$ into each of B, L, N, K, M.

So we are distributing $7$ marbles between $26$ "people." It is easier to count the number of ways to distribute $26+7$ marbles between $26$ people, with everybody getting at least $1$ marble. There are just as many ways to do this as there are to distribute $7$ marbles among $26$ people. Just distribute the marbles, at least $1$ to each, and then take away a marble from everybody.

To count the ways to distribute $33$ marbles, at least $1$ to each of $26$ people, line up the marbles in a row. There are $32$ "gaps" between marbles. Choose $6$ of these gaps to put separators into. Then A will get everything up to the first separator, B gets everything from the first separator to the second, and so on. After that, everybody gives a marble back. This procedure generates every distribution of $7$ marbles in one and only one way. We conclude that the total number of choices is $$\dbinom{32}{6}.$$ We have used a standard "Stars and Bars" argument. For more detail, please see Wikipedia.

Suppose we do not want to allow a repetition of more than $4$ letters. Then from $\dbinom{32}{6}$ we subtract the number of forbidden choices. We now count these forbidden choices.

There are $26$ ways to choose $7$ identical letters. Next we count the choices where exactly $6$ letters are identical and $1$ is different. There are $26$ ways to choose the letter we will have $6$ of. For each of these ways, there are $25$ ways to choose the letter we will have $1$ of, for a total of $(26)(25)$.

Finally, we count the choices where exactly $5$ letters are identical. This can happen in two ways: (i) $5$ identical and $2$ identical. or (ii) $5$ identical and $1$ each of two different kinds. It is not hard to see there are $(26)(25)$ choices of type (i). For type (ii), the letter we have $5$ of can be chosen in $26$ ways, and for each of these ways, the other two letters can be chosen in $\binom{25}{2}$ ways, for a total of $(26)\binom{25}{2}$. This is the only place where it is easy to make a mistake, and think that the answer for type (ii) is $(26)(25)(24)$. It isn't, that would double-count. So the total number of forbidden choices is $$26+(26)(25)+(26)(25)+(26)\binom{25}{2}.$$

share|improve this answer

Let n the number of possible letters. We can form sets of the form 1111111, 211111, 22111, 2221, 31111,3211,322,331,4111,421,43, where 1111111 means a set with all letters dfferents, 211111 means a set wth 2 numbers equals and 5 numbers dfferents, 22111 means 2 groups of two letters dfferents and 3 letters diferents etc. Then, there are $\binom{n}{7}$ sets of the form 111111, $\binom{n}{6}$ of the form 211111, there are $\binom{n}{5}$ sets of the form 22111. Hence $$ 1111111 \longmapsto \ \ \binom{n}{7}, \ 211111 \longmapsto \ \ \binom{n}{6}, \ 22111 \longmapsto \ \ \binom{n}{5}, \ 2221 \longmapsto \ \ \binom{n}{4}$$ $$ 31111 \longmapsto \ \ \binom{n}{5}, \ 3211 \longmapsto \ \ \binom{n}{4}, \ I 322 \longmapsto \ \binom{n}{3}$$

Now is only add.

share|improve this answer
    
+1 for this answer. Also noticed when I scroll down quickly, it has interesting visual. –  Jeremy Carlos Apr 27 '12 at 22:38
    
@Marcelo: There are various issues. For example, the number of choices of type $1111111$ is $\binom{n}{7}$. The number of choices of type $211111$ is $n \binom{n-1}{5}$. The reason is that the OP was not asking for the number of words. Counting words can be done in the style of the post, but for example the number of words of type $211111$ is $\binom{7}{2}(n)(n-1)(n-2)(n-3)(n-4)(n-5)$. –  André Nicolas Apr 28 '12 at 0:22
    
To 211111, we can choose two places to have the same letter in $ \binom{7}{2}$ modes, we divide by 2! since The order of the letters does not matter, to not count more. We can chosse the letter to those 2 places in n modes. For the remaining places, chosing different letters, we have (n-1)(n-2)(n-3)(n-4)(n-5) modes. Excuse my bad English and if I'm wrong. –  user29999 Apr 28 '12 at 13:11
    
André Nícolas, in fact, I was wrong. I'm going to modify my answer. I hope now, it will be correct. –  user29999 Apr 29 '12 at 17:14

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.