Partitioning Problem: Solving for Pairs & Triplets

[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

 

[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:

(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.

 

[ramsey2879]

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:

(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.

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/