# Partitioning problem

1. Jan 7, 2008

### ramsey2879

Let A be the complete set of ordered pairs of non-negative numbers which have a sum less or equal to N.
1. How many pairs are in the set?
2. If set A is sorted in ascending order 1st by the sum of the elements then by the value of each number reading from left to right the first such pair would be (0,0) the second (0,1), but can you find the sorted position of pair (a,b) as a function of a and b?
3. Answer questions 1 and 2 under the same assumptions but when dealing with triplets instead of pairs.
For the solutions to 1 and 2 see http://answers.yahoo.com/question/;...A3N1YmplY3Q-;_ylv=3?qid=20080103222238AAh2KWA

Last edited: Jan 7, 2008
2. Jan 7, 2008

### CompuChip

How I'd solve them:

1. What is the number of pairs with sum equal to N? Try building them one by one: how many numbers can you pick first and then how many choices are there to complement the pair?

2. Try writing out the first ... and see if you can find a pattern. Hint: write them in a grid:
Code (Text):

(2, 0) (2, 1) ...
(1, 0) (1, 1) (1, 2)
(0, 0) (0, 1) (0, 2) (0, 3)

and try to draw the ordering in it.

3. Repeat with three numbers: more work, probably same ideas

Nicest is if you can do it without looking at the answers in the link you provided.

3. Jan 7, 2008

### ramsey2879

Sure but what if you take it to partitions of more than 3 parts, the same method applies also. Since it is hard to work with grids of more than 2 dimensions. I think that I should point out that the answers for sorted ordered sets of K non-negative integers would also be based upon the properties of Pascal's triangle as are the solutions for K = 2 and 3. Also, partition theory can be applied if you can figure how many permutations there are of partitions of less than K parts padded with zeros to make K parts. I think the solution(s) I found for sorted ordered sets of 2 and 3 parts respectively can be generalized for sorted sets of more than 3 parts. See also my blog entry https://www.physicsforums.com/blogs/ramsey2879-21221/help-needed-with-n-dimensional-table-1229/ [Broken]

Last edited by a moderator: May 3, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook