Quadruples of Integers

YAHA

This should be a simple combinatorial problem. Suppose I have a number n which is a positive integer. Suppose, that there are four numbers a,b,c,d such that 0<=a<=b<=c<=d<=n.
The question is how many quadruples of the form (a,b,c,d) can be formed out such arrangement?

I realize that this is a homework-like question, but I am really interested in seeing which principles of combinatoris would apply here.

chiro

Hey YAHA.

Recall that if you get a number x on a particular draw, then the number of possibilities in the next draw will be n-x.

The rest is to apply the multiplication rule on these to get the number of possibilities for one particular set of observations.

Then sum over all possibilities and this will give you the total number of combinations.

So as an example, you look at the (n+1)*(n+1-x)*(n+1-y)*(n+1-z) for getting (*,x,y,z).

Now sum all of these over all consistent values of x, y, and z and that will give you the number of combinations.

awkward

The number of quadruples is the number of multisets of 4 numbers drawn from the integers 0, 1, 2, ..., n (n+1 integers), hence

[tex]\binom{n+1+4-1}{4} = \binom{n+4}{4}[/tex]

haruspex

Quite so, but I suspect that will need more detailed explanation. Here's my version, yours may be simpler.
We can map the problem into one where a< b < c < d, merely by adding 0, 1, 2, 3 respectively. Since we added 3 to d, we must also add 3 to n. So now it's a matter of the number of ways of choosing 4 distinct numbers from 0,..,n+3.