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.

I have a question, probably relatively simple one. Once you want to find all the unique combinations of number 5 you count 5! = 120. Once you want to find all the combinations including repetition of value of number 5 you count 5 power of 5 = 3125.

In my case I have the following situation. I have 9 characters you need to use to perform unique permutations on 4 columns/variables, meaning, for example, having 'a, b, c, d, e, f, g, h, i' I perform all the possible unique 4 combinations by using the 9 characters: 'a b c d'; 'a b e f'; 'd e f g' etc. In each column of each string of 4 characters (e.g. 'a, a, b, c' not allowed) the value of character can't get repeated. Now, how to count the number of such unique combinations obeying the constrains? Cheers

share|improve this question
    
Hmmm...you said "using all the $9$ characters". By that, do you mean that each character must be used at least once? If so, I'll need to change my answer.... –  Cameron Buie Sep 5 '12 at 14:41
1  
-1: It's difficult to tell what's being asked here. –  Austin Mohr Sep 5 '12 at 14:43
    
You have 9 characters and you need to perform all the possible permutations in 4 columns (e.g. 'a, b, d, e') such that you never get repetition of the same character in a single string of the 4 column characters. –  ucas Sep 5 '12 at 14:48
    
With 4 characters a, b, c, d and 2 "columns", would you expect to obtain a count of 6 (because there are ab, ac, ad, bc, bd, cd)? I just wonder - you seem to disallow repetition, but seem to implicitly order. If this is what you want to count, the answer is $n\choose k$, so e.g. ${9\choose 4} = 126$. –  Hagen von Eitzen Sep 5 '12 at 14:56
add comment

1 Answer

This post is incorrect at present, as Ross points out below. I'll think about it some more to try to fix it. Please don't upvote, downvote, or accept this answer, yet.

If I understand you correctly, you basically want to know how many $4$-row, $4$-column arrays there are with $9$ distinct possible entries, such that no row or column contains any repetition.

Well, there are $9\cdot 8\cdot 7\cdot 6$ possibilities for the first row. For the second (once the first is chosen), there are $8\cdot 7\cdot 6\cdot 5$. Then $7\cdot 6\cdot 5\cdot 4$ for the third and $6\cdot 5\cdot 4\cdot 3$ for the fourth. Multiply those $4$ products together for the answer.

Put in matrix form, assuming we work from the top-left in a down/right fashion, the number of possibilities, entrywise, will be $$\left(\begin{array}{cccc}9&8&7&6\\8&7&6&5\\7&6&5&4\\6&5&4&3\end{array}\right).$$ We're simply multiplying all the entries in the above matrix together.

share|improve this answer
    
Try to use \cdot instead.. –  Rijul Saini Sep 5 '12 at 14:37
    
This is not correct. The first row is fine, but the first element of the second row could match the second element of the first. In that case there will be $8$ choices for the second element of the second row. The other entries also need to take account of possible duplications in the entries above and to the left. –  Ross Millikan Sep 5 '12 at 14:39
    
Ah! Good catch. /facepalm/ –  Cameron Buie Sep 5 '12 at 14:43
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.