0

If I have a set of $n$ items $\{ A, B, C, D, ... \}$ from which I need to choose $r$ items and I am aware the formula for the number of combinations is:

$$\frac{n!}{ r!(n - r)!}$$

(Note, in my use-case, $r$ is always 3).

However, in my case each item may (but need not) have a variation (indicated here by a prime), so the set could be, for example, $\{ A, A', B, B', C, D \}$.

I want to choose 3 items from the set such that you may not choose a primed and non-primed item of the same letter and you may choose at most one primed item. If there are no primed items in the set then you may choose only non-primed items.

So from the above set $\{ A, B', C, D\}$ is legal but $\{ A, A', B, C \}$ and $\{ A', B', C, D \}$ are not.

I have noted that adding the first primed item to the set doesn't change the number of combinations (due to the rule that if there are none, then none need be used) so this may require an exception. After that, the number of combinations appears to be proportional to the number of primed items, however I am unable to derive the complete formula. Any help would be appreciated.

Alain Remillard
  • 3,625
rghome
  • 227

1 Answers1

1

If you have a set of $n$ éléments, where $k$ are prime. You want to choose $r$ elements such that

  • There is at most one primed element ( we'll consider two cases, no prime and one prime)

  • if a prime element is chosen, the corresponding non-prine is not.

If there is no primed element. Then you choose $r$ elements from a set of $n-k$ elements. $${n-k\choose r}=\frac{(n-k)!}{r!(n-k-r)!}$$ If there is one primed element, you first choose which one it is, then you choose the remainder from the set of non prime minus the corresponding one. $${k\choose 1}{n-k-1\choose r-1}=k\frac{(n-k-1)!}{(r-1)!(n-k-r)!}$$ Total number of sets is $$\frac{(n-k)!}{r!(n-k-r)!}+k\frac{(n-k-1)!}{(r-1)!(n-k-r)!}$$ In your example, with the set $\{ A, A', B, B', C, D \}$, $n=6$, $k=2$. If you want the number of subsets with three elements, $$\frac{(6-2)!}{3!(1)!}+2\frac{(6-2-1)!}{(3-1)!(6-2-3)!}=10$$

Alain Remillard
  • 3,625