Permutations with repetition beginning and/or ending with members of a subset For the sake of this example, take the random letters OOOAEESTMLHHXX. How would I go about finding all of the permutations, accounting for repetition, that start and end with members of a subset, in this case any of the vowels?
I'm aware of the formula for permutations with repetition n!/(n1!n2!...) where n1/n2... are the counts of each item, but I can't figure out how to split up the cases to not include unique permutations multiple times.
I originally wanted to do cases for each vowel where it started at the beginning (O___) or end (___O), add them, then subtract away the cases where the string begins AND ends with the particular vowel (since O___O would be included in each of the added cases, we take one of them out). The problem I see here is that for future vowels, I'm repeating cases like A___O, which I could be counting again but already included when calculating for O.
I also thought about calculating every case that begins and ends with consonants (which I still think is probably the way to go), but I can't see any way other than manually pairing every case of consonants for the front and back of the word, then using the repetition formula, which seems like SO MANY calculations.
Is there something easier that I'm missing?
Appreciated highly.
 A: The key to this problem is to combine elegance and brute force.
The string is "OOOAEESTMLHHXX".
There is one constraint: the first and last letters must each be
either "O", "A", or "E".  Although the string could (for example)
begin and end with "O", since there is only 1 "A", "A" can not
appear at both ends of the string.
This means that there are the letter groups "OOO", "EE", "HH", and "XX". 
There are also the single letters "A", "S", "T", "M", and "L".
Therefore, the string can vary in length from 2 through 14, inclusive.
As I see it, you are going to need 6 variables. 
Let $L_O \equiv ~$ the number of "O" letters used.  
Let $L_E\equiv ~$ the number of "E" letters used.  
Let $L_H \equiv ~$ the number of "H" letters used.  
Let $L_X \equiv ~$ the number of "X" letters used.  
Let $L_Z \equiv ~$ the number of letters used from the group "A", "S", "T", "M", and "L" 
Let $T \equiv ~$ the total number of letters used in the string.
The preliminary portion of this analysis will resemble
the following problem.
When you study this problem you will notice a few points.

*

*There are two ways to attack the # of solutions -
[Stars and Bars + Inclusion - Exclusion] or generating functions.


*The # of solutions that you generate will actually be a function of $T$, which
represents the variable length of the string (i.e. from 2 through 14 inclusive).


*All this analysis is doing is identifying all of the possible non-negative
integer solutions for each of the variables $L_O, L_E, L_H, L_X, L_Z.$


*At each possible value for $T$, you must focus on each of the individual
solutions separately.


*You then have to compute a formula that represents the number of possible
strings, as a function of the 6 variables.


*Note that you have to be very careful to prune away any of the solutions
that do not have at least two vowels.  Since the # of vowels are actually
reflected in the interaction between $L_O, L_E,~$ and whether $a$ makes an
appearance, you have a couple of options here.
You could split "a" off from the other group and make it its own variable.
Or you could decline to split "a" off, and simply ignore any strings that
don't begin and end with a vowel.

Believe it or not, unless someone has a more elegant approach, this is where
the fun starts.  For a given set of values for the variables,
you have to enumerate the # of possible distinct strings that can be formed.
I am going to give you a starter enumeration.  However, you will have to
polish the formula re the first and last letters need to begin with a vowel.
You can think of the # of strings as a fraction which equals
$$\frac{T!}{D\text{(enominaor)}}.$$
Here,
$$D = (L_O!) \times (L_E!) \times (L_H!) \times (L_X!).$$
The reason for this is because (for example) if the "O" appears in a specific
group of $L_O$ slots, you have to compensate for it being counted $(L_O!)$ times.
This approach is the easiest way to adjust for the over-counting.
I emphasize: I am leaving the constraint that both ends of the string
are vowels to you.
Obviously, you are going to have to program your computer very carefully.

There is an obvious alternative.  Since it would be ridiculous to try to
count the number of solutions (without using a computer) using a whole group of
elegant formulas, you have two alternatives.

*

*Come up with a more elegant approach than I have suggested.


*Abandon all elegance and simply use brute force to have the computer
spin through all of the various possible strings, seeing which ones satisfy
the constraints.  Here, the # of possible strings would be strictly less than
or equal to the following:
$$\sum_{k=2}^{14} ~\binom{14}{k} \times k!$$.
Addendum 
Keep in mind that I am totally ignorant of both generating functions and exponential generating functions.  I suspect that a more elegant approach is available through exponential generating functions.  However, I could be mistaken.
You would have to first study generating functions and then
study exponential generating functions to make this work.  Further, you would somehow have to include the constraint that the string begins and ends with a vowel.
