Compositions into relatively prime parts

[TimNguyen]

Hello.

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.

(i)!/2^n

Like:
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...

 

[code.master]

at first glance, my thought is to separate 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 don't 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. I am 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 isn't bogging me down so much.

 

[TimNguyen]

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

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.

 

[TimNguyen]

I was wondering... could this be solved by some sort of induction...?

 

[TimNguyen]

Any other math people?

 

[TimNguyen]

Could anyone help?