Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question

migrated from Feb 28 '13 at 21:20

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

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

share|cite|improve this answer
Partially right. However this doesn't account for the ordering of the elements. – xupv5 Feb 28 '13 at 21:39
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. – Dylan Zhu Feb 28 '13 at 21:52
Are you asking for where order doesn't matter? – 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$.

share|cite|improve this answer
No, it needs to include the cases where some elements don't appear at {x,x,x,y,y} should be a valid subset. – xupv5 Feb 28 '13 at 21:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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