Abstract Algebra - Compositions

  • Thread starter TimNguyen
  • Start date
  • #1
80
0
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...
 

Answers and Replies

  • #2
80
0
Any good algebraists in here?
 
  • #3
For 6, 6! = 720 divided by 2^4 = 16 will equal 45 compositions - a multiple of 3.

For 7, 7! = 5040 divided by 2^5 = 32 will equal 157.5 compositions - a multiple of something, but definitely not 3.

It doesn't work for (7, 5)... But (6, 4) works, doesn't it?


And then it resumes working at (8, 6)... That's strange.
 
Last edited:

Related Threads on Abstract Algebra - Compositions

  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
3K
Replies
13
Views
4K
Replies
3
Views
4K
Replies
8
Views
6K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
11
Views
3K
Top