Show That the # of (a,b,c) s.t. a+2b+3c = n is same as # of x + y + z = n s.t. x≤y≤z

  • Thread starter Poopsilon
  • Start date
  • #1
294
1
Comparing Partions of a Natural Number

Homework Statement



Let [itex]r(n)[/itex] denote the number of ordered triples of natural numbers [itex](a,b,c)[/itex] such that [itex]a + 2b + 3c = n[/itex], for [itex]n\geq 0[/itex]. Prove that this is equal to the number of ways of writing [itex]n = x + y + z[/itex] with [itex]0\leq x \leq y \leq z[/itex] for [itex]x,y,z[/itex] 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 [itex]\frac{(n+3)^2}{12}[/itex], 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.
 
Last edited:

Answers and Replies

  • #2
14
0


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).
 
  • #3
294
1


brilliant! thanks.
 

Related Threads on Show That the # of (a,b,c) s.t. a+2b+3c = n is same as # of x + y + z = n s.t. x≤y≤z

  • Last Post
Replies
3
Views
6K
Replies
2
Views
453
Replies
5
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
15
Views
1K
  • Last Post
2
Replies
28
Views
8K
  • Last Post
Replies
3
Views
3K
Replies
3
Views
3K
Replies
1
Views
6K
Top