3
$\begingroup$

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?

  • 0
    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.2012-04-27

2 Answers 2

2

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}.$

2

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.

  • 0
    André Nícolas, in fact, I was wrong. I'm going to modify my answer. I hope now, it will be correct.2012-04-29