Register to reply

Mathematics Journal, Proof for

by TimNguyen
Tags: journal, mathematics, proof
Share this thread:
TimNguyen
#1
Sep26-05, 11:25 PM
P: 81
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...
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
TimNguyen
#2
Sep29-05, 02:42 AM
P: 81
Any algebraist in here that could help?
TimNguyen
#3
Oct8-05, 04:22 AM
P: 81
Well, I've still been trying to prove this for the past week. I think there may be some recursion sequence or something. Well, I've tried listing the compositions and here's the results:

n=3 : 3 compositions
n=4 : 6 compositions
n=5 : 15 compositions
n=6 : 27 compositions
n=7 : 63 compositions
n=8 : 129 compositions

I'm predicting that n=9 : 387 compositions
n=10 : 687 compositions

Anyone feel like lending a hand...?

VietDao29
#4
Oct8-05, 05:07 AM
HW Helper
VietDao29's Avatar
P: 1,422
Mathematics Journal, Proof for

Maybe I don't really get what you mean... But for n = 5, I get 10 compositions, which means it fails for n = 5.
n = 5:
(1, 4), (4, 1)
(1, 1, 3), (1, 3, 1), (3, 1, 1)
(1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1)
(1, 1, 1, 1, 1)
That's 2 + 3 + 4 + 1 = 10...
Viet Dao,
TimNguyen
#5
Oct9-05, 04:47 AM
P: 81
Quote Quote by VietDao29
Maybe I don't really get what you mean... But for n = 5, I get 10 compositions, which means it fails for n = 5.
n = 5:
(1, 4), (4, 1)
(1, 1, 3), (1, 3, 1), (3, 1, 1)
(1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1)
(1, 1, 1, 1, 1)
That's 2 + 3 + 4 + 1 = 10...
Viet Dao,
You're forgetting:
(3,2), (2,3), (2,2,1), (2,1,2), (1,2,2),

which adds to 15.


Register to reply

Related Discussions
Discrete Mathematics Absolute Value Proof Calculus & Beyond Homework 3
Mathematics by proof General Math 4
Journal access Atomic, Solid State, Comp. Physics 2
My Journal of Basic Concepts of Mathematics Calculus 30
A Mathematics Proof Book Calculus 13