Given a set A containing {x, y, z}, how many permutations can we obtain that contain B elements, all drawn from the set A(with repetition)?

eg. given A = {x, y, z} and a target number of elements B=5 then we might have {x,y,z,x,x}, {x,y,z,x,y}, {x,y,z,x,z}, {x,y,z,y,x}, {x,y,z,z,x}, {y,x,z,x,x}, ...

How many of these permutations can be obtained given the size of set A and a fixed size B?(where B > A)

  • $\begingroup$ If the size of B is less than A would be a special case to ponder. $\endgroup$ – JB King Feb 28 '13 at 21:22
  • $\begingroup$ Can there be non-appearing elements (e.g. {x, x, x, x, x} doesn't include y and z)? $\endgroup$ – Joe Z. Feb 28 '13 at 21:24
  • $\begingroup$ Yes. All combinations are wanted. Then subsequently a way of finding out the number of special cases.eg. all subsets with the same first 2 leading elements, sets with x as first two leading elements, etc. $\endgroup$ – xupv5 Feb 28 '13 at 21:27
  • $\begingroup$ You write "permutations", but then you write "subsets" and "combinations". These are different. Figure out which one you mean, and please edit accordingly. $\endgroup$ – Gerry Myerson Feb 28 '13 at 21:38
  • $\begingroup$ I'm looking for the permutations. $\endgroup$ – xupv5 Feb 28 '13 at 21:44

Just consider how many eg. 5-digits number can we have, here is the same situation. $$_ _ _ _ _ ...._ _ _$$ Above are the blanks for the elements say if |A|=x, |B|=y, so there are y blanks each blanks can have x choice so its just $x^y$. please check it if i am right.

  • $\begingroup$ Partially right. However this doesn't account for the ordering of the elements. $\endgroup$ – xupv5 Feb 28 '13 at 21:39
  • $\begingroup$ yeah, its a bit tricky, think of when you do the digits question you dont consider the order of the digits, because you dont have to consider the difference of elements in different place, eg. for B=5, considr the situation x_ _ _ x , now if you wanna consider the ordering then it has 2 cases, x_ _ x and x _ _x , but its the same. $\endgroup$ – Dylan Zhu Feb 28 '13 at 21:52
  • $\begingroup$ Are you asking for where order doesn't matter? $\endgroup$ – Joe Z. Mar 1 '13 at 0:05

You seem to be asking for the number of strings of length $b$ where all characters in the set $A$ (of size $a$) appear at least once.

The way we do this is to take all the strings of length $b$ with any characters in the set $A$ (of which there are $a^b$) and subtract the number of strings of length $b$ with all characters of any strict subset of $A$ appearing at least once, and no others.

This is equal to $\displaystyle a^b - \binom{a}{a-1} (a-1)^b - \binom{a}{a-2} (a-2)^b - \ldots - \binom{a}{1} 1^b$ or $\displaystyle a^b - \sum_{k = 1}^{a} \binom{a}{a-k} (a-k)^b$.

  • $\begingroup$ No, it needs to include the cases where some elements don't appear at all.eg. {x,x,x,y,y} should be a valid subset. $\endgroup$ – xupv5 Feb 28 '13 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.