Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

migrated from stats.stackexchange.com 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 cases.eg. 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
add comment

2 Answers 2

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|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
add comment

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|improve this answer
    
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. –  xupv5 Feb 28 '13 at 21:34
add comment

Your Answer

 
discard

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.