Proving the Equality of Combinatorial Functions

[Poopsilon]

Comparing Partions of a Natural Number

Homework Statement

Let r(n) denote the number of ordered triples of natural numbers (a,b,c) such that a + 2b + 3c = n, for n\geq 0. Prove that this is equal to the number of ways of writing n = x + y + z with 0\leq x \leq y \leq z for x,y,z natural numbers.

The Attempt at a Solution

I don't really have a whole lot of combinatorial tools at my disposal here. I proved earlier that r(n) = the integer nearest to \frac{(n+3)^2}{12}, but I don't think that's really going to help. I feel like I need to construct some 1-1 function between these two sets. But I can't find any way of uniquely associating a choice of (a,b,c) with an x≤y≤z or visa-versa.

 

[wnorman27]

define D(x,y,z) = (x-1,y-1,z-1) for x>0.
define d(x,y,z) = (0,y-1,z-1) for x=0

notice that D^k(x,y,z)=(x-k,y-k,z-k) and
d^k(0,y,z)=(0,y-k,z-k)

now D^x(x,y,z) = (0,y-x,z-x) and
d^(y-x)[D^x(x,y,z)] = (0,0,z-x-(y-x)) =(0,0,z-y)

this suggests:

a=-y+z
b=-x+y
c=x

x=c
y=b+c
z=a+b+c

the matrix
|0 -1 1|
|-1 1 0|
|1 0 0|

takes (x,y,z) to (a,b,c) and is invertible (there's your bijection).

 

[Poopsilon]

brilliant! thanks.