Find all variations of a given set of letters containing letters multiple times

Given a set of letters e.g. {a, a, a, a, a, b, b, b, c, c, c, c, c, c, c}, which contains 15 letters (5*a, 3*b, 7*c), how many different combinations can be made with a maximum length of 7.
Examples would be:

• a
• aa
• aaa
• aaab
• baaa
• aaaaabc

Not distinguishing between aa using the 2 first a's in the set or using the 2 last a's.
aaaaabbb would also be a combination but this is discarded because it is longer than 7 letters.
This question stems from project euler problem 480. I am, however, not asking for the solution and only inquiring about a single step of the process.

My current way of thinking when trying to find the position of a word would be to calculate all the strings that come before it. This can be done by taking the first letter of the word (let's take euler) and calculating how many strings would come before it with first letters that are in the given set and come before the first letter of the word in the alphabet.
After this you can move on to the second letter and do a similar process, only this time the first letter is fixed to be e in this case and then you calculate how many strings exist with the second letter being in the given set (minus the e that is already used) and coming before the second letter of the word (u in this case).
Repeating this process for all letters of the word would eventually give you the position of the word.

Solution 1:

(Exponential) generating functions may well be the best approach. Unfortunately, I don't know anything about generating functions. So, I can only offer the following alternative, extremely crude approach.

Unfortunately, the approach taken is so convoluted, that for someone relatively new to the topic, giving a helpful hint would be very problematic. So, I have given a full solution.

The first thing to do is to identify how many distinct satisfying combinations of letters that there are. Then, for each such combination, you would need to apply a scaling factor.

For example, one combination would be a $5$ letter word, consisting of $2$ a's and $3$ b's. This specific combination can be used to create $\binom{5}{2}$ words, since there are $\binom{5}{2}$ ways that the $2$ a's can be positioned.

In general, if you have an $n$ letters consisting of $r$ a's, $s$ b's and $t$ c's (i.e. where $r + s + t = n$), then the number of words that can be formed from this particular combination (i.e. the scaling factor) is

$$\frac{n!}{r! \times s! \times t!}.\tag1$$

To start, I suggest that you read the answer to this question. However, the approach discussed in that answer, which allows the number of satisfying combinations to be enumerated, provides nothing more than a preliminary step. You then have to collect the various combinations into groups, with the idea that each group of combinations would have the same scaling factor.

I emphasize that this entire approach is very crude. If you know generating functions, I suspect that is a far superior approach.

As another fine point:

Normally, when you are applying Stars and Bars theory to enumerate the number of non-negative integer solutions to

$$x_1 + x_2 + x_3 \leq n,$$

you would use the trick that

$$x_1 + x_2 + x_3 + c = n,$$

where the length of the word is $(n-c)$. Here, that approach is no good, because in (1) above, the numerator of the scaling factor represents the exact length of the word to be formed.

Therefore, I must take the (even more) crude approach of splitting the problem into $(7)$ cases, depending on the length of the word to be formed.

Further, for the smaller values of $n$, I won't even bother with the Stars and Bars analysis, since manual (brute force) enumeration will be easier.

In all of the analysis below, where I do employ Stars and Bars theory, the variables of $x_1, x_2, x_3$ will represent the number of a's, b's, and c's, respectively.

$\underline{\text{Case 1:} ~\text{Number of words with} ~1 ~\text{letter}}$

There are $3$ choices for the letter, so the number of possible words is

$$3.$$

$\underline{\text{Case 2:} ~\text{Number of words with} ~2 ~\text{letters}}$

There are $3$ possible double letter words, and $6$ possible words with two distinct letters.

The number of possible words is

$$3 + 6 = 9.$$

$\underline{\text{Case 3:} ~\text{Number of words with} ~3 ~\text{letters}}$

Since there are at least $3$ of each of the a's, b's, and c's, the number of possible combinations is the same as the number of non-zero integer solutions to

$$x_1 + x_2 + x_3 = 3.$$

In accordance with Stars and Bars, there are $\binom{3+2}{2} = \binom{5}{2} = 10$ such combinations. Grouping them by their scaling factors:

$(3)$ triplets: $~~\displaystyle 3 \times \frac{3!}{3! \times 0! \times 0!} = 3.$

$(6) = 3 \times 2$ - double + single: $~~\displaystyle 6 \times \frac{3!}{2! \times 1! \times 0!} = 18.$

$(1)$ - 3 singletons: $~~\displaystyle 1 \times \frac{3!}{1! \times 1! \times 1!} = 6.$

The number of possible words is

$$3 + 18 + 6 = 27.$$

$\underline{\text{Case 4:} ~\text{Number of words with} ~4 ~\text{letters}}$

Since the number of non-negative integer solutions to

$$x_1 + x_2 + x_3 = 4$$

is $\binom{4 + 2}{2} = \binom{6}{2} = 15$, I would ordinarily presume that $15$ satisfying combinations must be dealt with. Here, since there are only $3$ b's, the solution of

$$(x_1, x_2, x_3) = (0,4,0)$$

must be rejected. Therefore, there are $14$ satisfying combinations.

Grouping them by their scaling factors:

$(2)$ quadruplets: $~~\displaystyle 2 \times \frac{4!}{4! \times 0! \times 0!} = 2.$

$(6) = 3 \times 2$ - triple + single: $~~\displaystyle 6 \times \frac{4!}{3! \times 1! \times 0!} = 24.$

$(3)$ - 2 doubles: $~~\displaystyle 3 \times \frac{4!}{2! \times 2! \times 0!} = 18.$

$(3)$ - 1 double, 2 singles: $~~\displaystyle 3 \times \frac{4!}{2! \times 1! \times 1!} = 36.$

The number of possible words is

$$2 + 24 + 18 + 36 = 80.$$

$\underline{\text{Case 5:} ~\text{Number of words with} ~5 ~\text{letters}}$

The number of non-negative integer solutions to

$$x_1 + x_2 + x_3 = 5$$

is $\binom{5 + 2}{2} = \binom{7}{2} = 21$.

Following the strategy in the linked article, of those $21$ solutions, the number of them where the constraint that $x_2$ (i.e. the number of b's) is $\leq 3$ may be computed by computing the number of non-negative integer solutions to

$$x_1 + x_2 + x_3 = (5 - 4) = 1.$$

The number of such solutions is $\binom{1 + 2}{2} = \binom{3}{2} = 3.$ Therefore, the total number of satisfying combinations is $21 - 3 = 18.$

Grouping them by their scaling factors:

$(2)$ quintuplets: $~~\displaystyle 2 \times \frac{5!}{5! \times 0! \times 0!} = 2.$

$(4) = 2 \times 2$ quadruplet + singleton: $~~\displaystyle 4 \times \frac{5!}{4! \times 1! \times 0!} = 20.$

$(6) = 3 \times 2$ triplet + double: $~~\displaystyle 6 \times \frac{5!}{3! \times 2! \times 0!} = 60.$

$(3)$ triplet + 2 singles: $~~\displaystyle 3 \times \frac{5!}{3! \times 1! \times 1!} = 60.$

$(3)$ 2 doubles + 1 single: $~~\displaystyle 2 \times \frac{5!}{2! \times 2! \times 1!} = 90.$

The number of possible words is

$$2 + 20 + 60 + 60 + 90 = 232.$$

$\underline{\text{Case 6:} ~\text{Number of words with} ~6 ~\text{letters}}$

Here, you have two constraint violations to consider:

• $x_1 \leq 5.$
• $x_2 \leq 3.$

I will let $T_0$ represent the total number of non-negative integer solutions, without any regard to the above constraints.

I will let $A_1$ represent the set of solutions where the constraint of $x_1 \leq 5$ is violated.

I will let $A_2$ represent the set of solutions where the constraint of $x_2 \leq 3$ is violated.

I will let $T_1$ represent the number of elements in $A_1$ added to the number of elements in $A_2$.

I will let $T_2$ represent the number of elements in $A_1 \cap A_2$.

Then, in accordance with Stars and Bars Theory, the number of satisfying combinations will be

$$T_0 - T_1 + T_2.$$

Note that since $6 + 4 > 6$, it is actually impossible for the constraints on $x_1$ and $x_2$ to be simultaneously violated. Therefore, you know that $A_1 \cap A_2$ is the empty set, and therefore $T_2 = 0.$

$\displaystyle T_0 = \binom{8}{2} = 28.$

$\displaystyle T_1 = \binom{0 + 2}{2} + \binom{2 + 2}{2} = 7.$

Therefore, the total number of satisfying combinations is $28 - 7 = 21.$

Grouping them by their scaling factors:

$(1)$ group of 6: $~~\displaystyle 1 \times \frac{6!}{6! \times 0! \times 0!} = 1.$

$(4) = 2 \times 2$ groups of 5,1: $~~\displaystyle 4 \times \frac{6!}{5! \times 1! \times 0!} = 24.$

$(4) = 2 \times 2$ groups of 4,2: $~~\displaystyle 4 \times \frac{6!}{4! \times 2! \times 0!} = 60.$

$(2)$ groups of 4,1,1: $~~\displaystyle 4 \times \frac{6!}{4! \times 1! \times 1!} = 60.$

$(3)$ groups of 3,3: $~~\displaystyle 3 \times \frac{6!}{3! \times 3! \times 0!} = 60.$

$(6) = 3 \times 2$ groups of 3,2,1: $~~\displaystyle 6 \times \frac{6!}{3! \times 2! \times 1!} = 360.$

$(1)$ groups of 2,2,2: $~~\displaystyle 6 \times \frac{6!}{2! \times 2! \times 2!} = 90.$

The number of possible words is

$$1 + 24 + 60 + 60 + 60 + 360 + 90 = 655.$$

$\underline{\text{Case 7:} ~\text{Number of words with} ~7 ~\text{letters}}$

The analysis of the enumeration of the number of satisfying combinations is virtually identical with that of Case 6.

$\displaystyle T_0 = \binom{9}{2} = 36.$

$\displaystyle T_1 = \binom{3}{2} + \binom{5}{2} = 13.$

The number of satisfying combinations is
$\displaystyle T_0 - T_1 = 36 - 13 = 23.$

Grouping them by their scaling factors:

$(1)$ group of 7: $~~\displaystyle 1 \times \frac{7!}{7! \times 0! \times 0!} = 1.$

$(2) = 1 \times 2$ groups of 6,1: $~~\displaystyle 2 \times \frac{7!}{6! \times 1! \times 0!} = 14.$

$(4) = 2 \times 2$ groups of 5,2: $~~\displaystyle 4 \times \frac{7!}{5! \times 2! \times 0!} = 84.$

$(2)$ groups of 5,1,1: $~~\displaystyle 2 \times \frac{7!}{5! \times 1! \times 1!} = 84.$

$(4) = 2 \times 2$ groups of 4,3: $~~\displaystyle 4 \times \frac{7!}{4! \times 3! \times 0!} = 140.$

$(4) = 2 \times 2$ groups of 4,2,1: $~~\displaystyle 4 \times \frac{7!}{4! \times 2! \times 1!} = 420.$

$(3)$ groups of 3,3,1: $~~\displaystyle 3 \times \frac{7!}{3! \times 3! \times 1!} = 420.$

$(3)$ groups of 3,2,2: $~~\displaystyle 3 \times \frac{7!}{3! \times 2! \times 2!} = 630.$

The number of possible words is

$$1 + 14 + 84 + 84 + 140 + 420 + 420 + 630 = 1793.$$

Adding the total number of words possible, in each of the individual cases:

$$3 + 9 + 27 + 80 + 232 + 655 + 1793 = 2799.$$