Find Number of Permutations of 2D Numbers Constrained by Sum n

[Ketsha]

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 X_k, 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 (X_k) that satisfy this condition.

the numbers X_k belong to the set of whole numbers, and n belongs to the set of natural numbers.

 

[Mark44]

If you have a set of numbers for which x₁ + x₂ + ... + x_2d = n, then any permutation of the x_k's will have the same sum, so that isn't much of a constraint.

If you had 4 numbers x₁, x₂, x₃, and x₄, 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.

 

[JSuarez]

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"

(These slides are better than the Wiki article)

 

[pikolo]

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 let's 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 x_k.. 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)

 

[Ketsha]

Thanks for the awesome solution... that was really well explained :) and has solved one of my biggest troubles. :)