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.

How would I count the the number of ordered triples of different numbers $(X_1, X_2, X_3)$, where $X_i$ could be any positive integer from $1$ to $N_i$, inclusive $(i = 1, 2, 3)$.

If the input was $(3,3,3)$ the ordered triples formed from that would be $(1, 2, 3)$ $(1, 3, 2)$ $(2, 1, 3)$ $(2, 3, 1)$ $(3, 1, 2)$ $(3, 2, 1)$ and the answer would be $6$.

So, if someone could tell me how you would create those ordered triples out of the initial $(3,3,3)$ that would be great

I think one of the problems here for me is that I dont really understand what makes a number and ordered triple.

share|improve this question
    
Welcome to MSE! IS this homework? If so, please tag it as such. –  Amzoti Jan 6 '13 at 17:12
    
nope not homework. Its a sub problem to a computer science assignment. I need to figure out this before I can solve the problem. –  Will Jamieson Jan 6 '13 at 17:16
    
Don't you mean $6$ instead of $5$ for the case $(3,3,3)$? –  Hagen von Eitzen Jan 6 '13 at 17:18
    
@Will J: your question is confusing. First, you show six ordered pairs for your example, but say the number is $5$. Also, What would be the results if the inputs were $(1, 1, 1)$, $(1, 2, 3)$ and $(1, 1, 3)$? Regards. –  Amzoti Jan 6 '13 at 17:20
2  
Shouldn't the tag be combinatorics rather than number-theory? –  alancalvitti Jan 6 '13 at 17:32

3 Answers 3

up vote 1 down vote accepted

The following argument counts the number of ordered triples but also gives you an algorithm to generate the triples:

Let us assume $N_1\leq N_2 \leq N_3$. For the first element of the triple you can choose any number out of the $N_1$.

The second element, you are not allowed to choose the one that is already taken by the first, so these are $N_2 -1$ elements.

For the third element it goes equivalently: you can choose any but the one taken for the first or second element so $N_3-2$ elements.

In total you thus have $N_1(N_2 -1) (N_3-2)$ possibilities...

share|improve this answer
    
for test case 25 12 2012 answer should be 578880 but the result is wrong for this testcase. –  user55381 Jan 6 '13 at 18:35
    
@user55381: Can you be consistent with formatting? Can you clarify what you are saying here? Also, can you please explain why is it wrong? Regards –  Amzoti Jan 6 '13 at 18:55
    
@user55381: The answer by Fabian gives $(12)(24)(2010)=578880$. –  André Nicolas Jan 6 '13 at 19:02
    
Sorry for the inconvenience. I misinterpreted it –  user55381 Jan 6 '13 at 19:12

Wlog. $N_1\le N_2\le N_3$. The triples $(a,b,c)$ can be categorized as follows:

  • $b,c\le N_1$. There are $N_1(N_1-1)(N_1-2)$ possibilities
  • $b>N_1$, $c\le N_1$. There are $N_1(N_1-1)\cdot (N_2-N_1)$ possibilities
  • $b\le N_1$, $c>N_1$. There are $N_1(N_1-1)\cdot (N_3-N_1)$ possibilities
  • $b>N_1$, $N_1<c\le N_2$. There are $(N_2-N_1)(N_2-N_1-1)\cdot N_1$ possibilities
  • $b>N_1$, $c>N_2$. There are $N_1(N_2-N_1)(N_3-N_2)$ possibilities.

If you sum these up, you obtain $$ N_1^3-(N_2+1)N_1^2+(N_3-1)N_2N_1-(N_3-2)N_1,$$ I think.

share|improve this answer
    
I think this works but if you have the numbers $(1,1,4)$ the sum with your formula would be $6$ even though the actual answer is $0$ since the only choice for $N1, N2$ is $1$ –  Will Jamieson Jan 6 '13 at 17:50
    
If $N_1=N_2=1$, I obtain $1-2+(N_3-1)-(N_3-2)=0$, as expected. –  Hagen von Eitzen Jan 6 '13 at 18:08
    
@HagenvonEitzen: you result does not agree with my result. The simplest case where there is a difference is for $N_1=2$, $N_2=3$, $N_3=3$... You predict 2 possibilities whereas my formula gives 4. You can count $(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$... –  Fabian Jan 6 '13 at 18:20

Say the input has three numbers p, q, r. Sort the numbers in non-decreasing order and then you will have the number of such ordered triples as p*(q-1)*(r-2)

This problem is from a running contest at Codechef, but I am posting the answer as it will still require some effort to get the solution accepted there. ALthough the idea is correct, and hint is enough.

share|improve this answer

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.