Generating Function Questions

rdj5933mile5math64 · **Posted:** Sat, 4 Aug 2012 02:44:44 UTC

Hmmm I guess generating functions aren't my thing~ I may have to post more questions as the weekend goes by :O

Question #1:
Show that the number of compositions of n into an odd number of parts, each of which is at least

, is [

] $\frac{x^3-x^4}{1-2x+x^2-x^6}$ .

My Work:
Well I didn't know what a composition of a positive integer

was so I had to look it up. Then I found out that it is the number of ordered partitions of

. I thought about subtracting

from each part, but I don't see how that's going to help with the fact that there are an odd number of parts... I tried summing based on the number of odd parts, but that wasn't working for me because the values the parts can take change based on the number of parts.

outermeasure · **Posted:** Sat, 4 Aug 2012 10:51:03 UTC

rdj5933mile5math64 wrote:

Hmmm I guess generating functions aren't my thing~ I may have to post more questions as the weekend goes by :O

Question #1:
Show that the number of compositions of n into an odd number of parts, each of which is at least

, is [

] $\frac{x^3-x^4}{1-2x+x^2-x^6}$ .

My Work:
Well I didn't know what a composition of a positive integer

was so I had to look it up. Then I found out that it is the number of ordered partitions of

. I thought about subtracting

from each part, but I don't see how that's going to help with the fact that there are an odd number of parts... I tried summing based on the number of odd parts, but that wasn't working for me because the values the parts can take change based on the number of parts.

I don't believe it is true --- $\dfrac{x^3-x^4}{1-2x+x^2-x^6}=x^3+x^4+x^5+x^6+x^7+x^8+2x^9+4x^{10}+\dots$ which cannot be the generating function: there is only 2 ways to partition 10 into odd number of parts each at least 3, viz. (10) and (4,3,3).

What you want is obviously $\displaystyle\sum_{k\text{ odd}}\frac{x^{3k}}{(1-x)(1-x^2)\cdots(1-x^k)}$ . I'm not sure this has a nicer expression, indeed OEIS sequence A027195 doesn't give anything.

rdj5933mile5math64 · **Posted:** Sat, 4 Aug 2012 17:50:29 UTC

Hmmm I see how it works a little more now. Does

mark anything in the generating function (e.g. when considering the number of partitions of

with

parts, we let

mark a part)?

outermeasure wrote:

2 ways to partition 10 into odd number of parts each at least 3, viz. (10) and (4,3,3).

Sorry, I should have explained what a composition was. A composition (or an ordered partion) is different from a partition.

Hence, $(4,3,3) \neq (3,4,3) \neq (3,3,4)$ and the number of ways is indeed

.

outermeasure · **Posted:** Sun, 5 Aug 2012 04:55:24 UTC