# Counting the number of ordered triples

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.

-
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
Shouldn't the tag be combinatorics rather than number-theory? –  alancalvitti Jan 6 '13 at 17:32

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...

-
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.

-
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.

-