# Counting permutations of distinct items with repetition allowed and compulsory inclusion of some items

I have following problem:

I have five elements $\{a,b,c,d,e\}$. I have to form ordered group of three elements out of these five elements. at least one or both of $a$ and $b$ should appear in the group formed. Also elements can be repeated. What will be the nicer / neat / systematic way, possibly made-up but neat formula to get the desired count?

How can I come up with final count? I can guess all the possibilities that I have to consider, but I am not able to come up with nice formula to put all these possibilities together. These are the possibilities I am able to come up with:

1. With $a$ included in the group, there will be $5\times 5$ groups.
2. With $b$ included in the group, there will be $5\times 5$ groups.
3. However out of these $5\times 5 + 5\times 5$, I need to subtract count of groups including both $a$ and $b$.
4. Again I have to subtract count of groups where we have permuted among same group due to repetition of some specific element. For example {a,a,c} will be counted twice. But I should count once only.

How I do deal with last two points? Do I have to resort to manual counting?

• If the groups are ordered, you're miscounting in bullet points 1 and 2. – Wildcard Oct 5 '17 at 21:02

Hint: How many sequences are there in total ?

How many sequences are there that do not contains both $a$ and $b$ ?

So ...

Alternatively :

The sure fire bet to get the answer is to list the $10$ possibilities and calculate their multiplicities. ($S$ = sequence upto permutation, $M$= Multiplicity , $*= c,d \text{ or } e$)

\begin{array}{l|l} S & M \\ \hline aaa & \color{blue}{1} \\ aab & \color{blue}{3} \\ abb & \color{blue}{3} \\ bbb & \color{blue}{1} \\ aa* & \color{blue}{9} \\ ab* & \color{blue}{18} \\ bb* & \color{blue}{9} \\ a** & \color{blue}{27} \\ b** & \color{blue}{27} \\ *** & 27 \\ \hline & 125 \end{array}

• Do you mean to say the final answer is 125? – anir Oct 5 '17 at 20:56
• No. Add the blue values together. (Altenatively just subtact the only black value from $125$) ... The $125$ is there in order to check that we have counted every possibility. – Donald Splutterwit Oct 5 '17 at 21:03

Ignoring the restriction, there are five choices for each of three positions.

The restriction excludes ordered sequences drawn from the space wherein there are only three choices for each of three positions.

$$5^3-3^3=98$$