1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jun 23, 2012 #1
    Comparing Partions of a Natural Number

    1. The problem statement, all variables and given/known data

    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.


    3. 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: Jun 23, 2012
  2. jcsd
  3. Jun 23, 2012 #2
    Re: Show That the # of (a,b,c) s.t. a+2b+3c = n is same as # of x + y + z = n s.t. x≤

    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).
     
  4. Jun 23, 2012 #3
    Re: Show That the # of (a,b,c) s.t. a+2b+3c = n is same as # of x + y + z = n s.t. x≤

    brilliant! thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: 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
  1. F(x, y, z) ? (Replies: 2)

  2. Temperature at (x,y,z) (Replies: 3)

Loading...