Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Compositions into relatively prime parts

  1. Sep 27, 2005 #1

    I was reading a journal and an interesting problem came up. I believe the journal was in the American Mathematics Society publications. Well, here's the statement.

    "For all integers, n greater than or equal to 3, the number of compositions of n into relatively prime parts is a multiple of 3."

    Example : For 4: the compositions of relatively prime parts are:

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

    This is what I have so far for a "proof":

    Let n be an integer greater than or equal to 3.
    Then the first composition will be given by (n-1, 1), (1, n-1); since for all k, an integer, (k, 1) and (1, k) are always relatively prime.
    Also, (1, 1, ..., 1) where the composition adds to n is also an obtainable composition.

    (So basically, I've gotten the end points of the compositions to be a multiple of 3, then I need to prove that the "in-between" compositions will also be a multiple of 3.)

    Well, obviously I'm stuck there. I've tried to split it into two cases afterwards where the cases involve n - odd and n - even but it has come to no avail. Also I've tried to find a formula where the compositions of relatively prime parts is a multiple of 3 but it fails at "6". Here was the formula I came up with that failed, if it could be potentially be improved upon.

    Formula: Starting at n=1, where i=3, i being the starting point.


    For 3, 3! = 6 divided by 2^1 = 2 will equal 3 compositions- a multiple of 3
    For 4, 4! = 24 divided by 2^2 = 4 will equal 6 compositions - a multiple of 3
    For 5, 5! = 120 divided by 2^3 = 8 will equal 15 compositions - multiple of 3

    Well, hopefully people will post their ideas...
  2. jcsd
  3. Sep 27, 2005 #2
    at first glance, my thought is to seperate the cases into three. first do 3|n, then do 3|n+1 and 3|n+2 . its quite easy to show the specific case of 4,5,6 and show how the compositions break down into threes. its not quite so simple to just give a formula to derive the number of groupings, but i think you are on the right track. i think your explorations in that realm will give you something.

    your formula gives 45 compositions for 6. is that total bunk? i dont feel like doing it on paper. well, it certainly gives a multiple of 3, and that can be shown.

    i have a proof from an elementary course that gives the prime factorization breakdown for n! in the general case, and it shows that 3 must obviously be a factor of all n! for n>3, and that 2^k will be a factor too, but 2^k was determined by part of the proof, it wasnt just n-2. im rambling now. but anyways, its found by taking the largest power of 2 that is less than the number. starting with that power, say j, 2^(j!) will give the exponent to divide the number down. and n!/(2^j!) must also be divisible by 3.

    I think you got the right direction to get a full proof of the statement. Ill work on it a bit more when physics isnt bogging me down so much.
  4. Sep 28, 2005 #3
    Thanks for the reply.

    The formula I've written down is wrong for 6 because I've listed (sadly) the compositions and it wasn't 45, it was more like 20-ish. Also, for 7, it definitely fails since 7!/2^5 = 157.5 - not a multiple of 3. I think there's probably some type of "factor" that needs to be added to such proposed formula in order for it to work after 6, but is negligible before it.
  5. Sep 28, 2005 #4
    I was wondering... could this be solved by some sort of induction...?
  6. Sep 28, 2005 #5
    Any other math people?
  7. Oct 1, 2005 #6
    Could anyone help?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook