Combinatorics: generating functions

[calvino]

I'm unsure about the following questions. Theyre from my introductory combinatorics class.

1) Let a_n denote the number of ways to distribute n objects to three people: A, B, C. A must have at least 2 of the objects, and B must have an amount divisible by 5. Find the generating function of {a_n} 0 to infinity.

2) let a_n be the number of partitions of n that obey the following restriction: for each m, there is at most one part of size 3m. find the generating function of a_n.

Looking at 1), obviously the a_0 and a_1 are 0. 0 is divisible by 5, so we can start with A_2. I get the folloqing sequence: 0,0,1,2,3,4,5,7,9,11,13,15,18,21...

i see that from a_2 to a_6 each value increases by 1, and then from a_7to a_11 ithere are increases of 2, then 3 for the next set of 4, and then 4, etc.

From here i see a_(n)= (a_(n-5)) + (n -6).

I multiply both sides by x^n and sum for all n to somehow get a series i can work with.

So i get the following on the LEFT SIDE:

1x^2 + 2x^3 +... (n-1)x^n + ... = xnx^n -> x ( x/(1-x)^2)= (x^2)/(1-x)^2.


I get stuck when evaluating the right side, since it has a value n and not anything of the form a_n , as well as the a_(n-5). I have class now so I'll further explain where I'm at a littlelater. any help with the RIGHT SIDE would be great, or any input as to what I'm doing so far would be as well.



As for 2), we're talking about partitions of numbers (un-ordered I would assume). I've also assumed m is an integer greater than 0. the partitions of the natural numbers starting with 1 follow the sequence 1,2,3,5,7,...
Those are the first 5. obviously at 6 were going to start getting multiples of 3. so the breakdown of 6 is as follows

6= 3+3 (negated, since we have two threes)
=5+1 = 4+1+1
=4+2 = 2+2+2 = 2+2+1+1 = 2+1+1+1+1 = 1+1+1+1+1+1
=3+2+1 = 3+1+1+1

So it has 10 partitions that work.

I calculate the actual sequence of a_n considering that every time we pass have a_n with n=3m, we're going to have more partitions to negate. I get the following sequence:

1,2,3,5,7,10,14,20,27,37,48,... which starts at a_1.

At this point, I can't find any recurrence relationship. Any help?

 

[ircdan]

1) looks wrong, but ignoring that for a moment concerning your RHS,

(x^2)/(1-x)^2
= x^2 * (1 + (-x))^(-2) =
= x^2 * SUM(C(-2, k)(-x)^k, k = 0,1...) =
= x^2 * SUM((-1)^k C(2 + k - 1, k)*(-x)^k, k = 0, 1, ...)
= x^2 *SUM(C(k + 1, k)*x^k, k = 0, 1, 2, ...)
= x^2 *SUM((k + 1)x^k, k = 0, 1, 2, ...)
= SUM((k - 1)*x^k, k = 2, 3,...),
so in this case a_k = k - 1 for k>=2, a_k = 0 otherwise
I didn't get that, for my gf I got,

G(x) = (x^2 + x^3 + ...)*(1 + x^5 + x^10 + ...)*(1 + x+ x^2 + x^3 + ...)
= x^2(1 + x + x^2 + ...)^2 *(1 + x^5 + ...)
= x^2/(1 -x)^2 * 1/(1 - x^5)

And the coefficient of x^k in G(x) is a_k = the # of ways to distribute k objects to A, B, C with the conditions you specifiedUnless I'm totally missing something, that's what I got. Anyways goodluck.
(woops i used k instead of n, but yea)

 

[mehrts]

I'm unsure about the following questions. Theyre from my introductory combinatorics class.

1) Let a_n denote the number of ways to distribute n objects to three people: A, B, C. A must have at least 2 of the objects, and B must have an amount divisible by 5. Find the generating function of {a_n} 0 to infinity.

2) let a_n be the number of partitions of n that obey the following restriction: for each m, there is at most one part of size 3m. find the generating function of a_n.

Looking at 1), obviously the a_0 and a_1 are 0. 0 is divisible by 5, so we can start with A_2. I get the folloqing sequence: 0,0,1,2,3,4,5,7,9,11,13,15,18,21...

i see that from a_2 to a_6 each value increases by 1, and then from a_7to a_11 ithere are increases of 2, then 3 for the next set of 4, and then 4, etc.

From here i see a_(n)= (a_(n-5)) + (n -6).

I multiply both sides by x^n and sum for all n to somehow get a series i can work with.

So i get the following on the LEFT SIDE:

1x^2 + 2x^3 +... (n-1)x^n + ... = xnx^n -> x ( x/(1-x)^2)= (x^2)/(1-x)^2.


I get stuck when evaluating the right side, since it has a value n and not anything of the form a_n , as well as the a_(n-5). I have class now so I'll further explain where I'm at a littlelater. any help with the RIGHT SIDE would be great, or any input as to what I'm doing so far would be as well.



As for 2), we're talking about partitions of numbers (un-ordered I would assume). I've also assumed m is an integer greater than 0. the partitions of the natural numbers starting with 1 follow the sequence 1,2,3,5,7,...
Those are the first 5. obviously at 6 were going to start getting multiples of 3. so the breakdown of 6 is as follows

6= 3+3 (negated, since we have two threes)
=5+1 = 4+1+1
=4+2 = 2+2+2 = 2+2+1+1 = 2+1+1+1+1 = 1+1+1+1+1+1
=3+2+1 = 3+1+1+1

So it has 10 partitions that work.

I calculate the actual sequence of a_n considering that every time we pass have a_n with n=3m, we're going to have more partitions to negate. I get the following sequence:

1,2,3,5,7,10,14,20,27,37,48,... which starts at a_1.

At this point, I can't find any recurrence relationship. Any help?

Looks like the MATH 4160 assignment we had. :)

 

[calvino]

weird...im pretty sure i responded to this thread twice earlier.

ircdan..thanks for your input no 1). i did learn something from it, and I decided to apply it to 2). I guess I shouldn't have tried to make the sequence first.

for 2), i got a generating funtion (in a sense), but it is infinite, since we are talking about a general n.

1/(1-x) * 1/(1-x^2) * (1+x^3) * 1/(1-x^4) * 1/(1-x^5) * (1+x^6) *...

is what I came up with, using the technique ircdan used earlier. here, the 1+x^3 means that there are either 0 or 1 part size 3. this is why I do that for all 3m, m a natural number. Now how do i simplify this? this is where I'm stuck