Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quadruples of Integers

  1. Oct 10, 2012 #1
    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.
     
  2. jcsd
  3. Oct 10, 2012 #2

    chiro

    User Avatar
    Science Advisor

    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.
     
  4. Oct 11, 2012 #3
    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]
     
  5. Oct 12, 2012 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook