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

I have 2d numbers X

  1. Aug 4, 2010 #1
    ok this seems like a predominantly maths problem but i need it for a little project of mine related to classical dynamics.

    So i have 2d numbers Xk, which are constrained by the relation that their sum is n.

    what i need to find out is the number of possible permutations of the 2d numbers (Xk) that satisfy this condition.

    the numbers Xk belong to the set of whole numbers, and n belongs to the set of natural numbers.
  2. jcsd
  3. Aug 4, 2010 #2


    Staff: Mentor

    Re: permutations

    If you have a set of numbers for which x1 + x2 + ... + x2d = n, then any permutation of the xk's will have the same sum, so that isn't much of a constraint.

    If you had 4 numbers x1, x2, x3, and x4, whose sum was N, how many permutation of the four numbers are there? Any of the four numbers could go into the first position, then any of the remaining three numbers could go into the second position, then any of the remaining two numbers could go into the third position, leaving only one number to go into the fourth position.
  4. Aug 4, 2010 #3
    Re: permutations

    Assuming that the numbers are non-negative integers (without this restriction, the number of possibilities is infinite), the number of solutions is given by combinatations with repetition of n objects of k = 2d different types; you may think of this as "filling" each variable Xi, one unit at a time, until you a total of n.

    You may find a more complete explanation for these combinations here:

    http://www.csee.umbc.edu/~stephens/203/PDF/6-5.pdf" [Broken]

    (These slides are better than the Wiki article)
    Last edited by a moderator: May 4, 2017
  5. Aug 5, 2010 #4
    Re: permutations

    nice problem...

    Consider a number line made of 2d line segments of variable length. each line segment representing one of your 2d numbers. These line segments will be divided by 2d-1 points.. or lets represent by sticks instead of points. so there are 2d-1 sticks.

    Now consider N balls. Each representing the numeric value 1. So total number balls is the sum of 2d numbers that you need to be.

    now... if you arrange these N balls and 2d-1 sticks randomly, it will be kind off a pictorial representation of your problem. the number of balls between two sticks being a particular value xk.. and there will be 2d such numbers.

    Since there can be two suck sticks together... the numbers will be greater than or equal to zero. Hence belonging to the set of whole numbers.

    Now the question remains... in how many different ways can we arrange these 2d-1 sticks and N balls.

    that will (N+2d-1)!

    Now N of them are alike (balls) and 2d-1 of them are alike (sticks). so...

    To total number of ways would be... (N+2d-1)!/N!(2d-1)! or simply (N+2d-1)C(2d-1)
  6. Aug 5, 2010 #5
    Re: permutations

    Thanks for the awesome solution... that was really well explained :) and has solved one of my biggest troubles. :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook