Combinatorics: generating functions

In summary: 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.In summary, the first problem involves finding the generating function for the number of ways to distribute a given number of objects to three people, with specific
  • #1
calvino
108
0
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?
 
Physics news on Phys.org
  • #2
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)
 
Last edited:
  • #3
calvino said:
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. :)
 
  • #4
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
 

Related to Combinatorics: generating functions

1. What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting, arranging, and selecting objects or elements in a specific way.

2. What is a generating function in combinatorics?

A generating function is a mathematical function used to represent a sequence of numbers, where each term in the sequence corresponds to a specific coefficient in the function. In combinatorics, generating functions are used to solve problems involving counting and arrangement of objects.

3. How are generating functions used in combinatorics?

Generating functions are used in combinatorics to simplify and solve complex problems involving counting and arrangement of objects. They allow for the use of algebraic and analytical techniques to solve problems that may be difficult to solve directly.

4. What are the benefits of using generating functions in combinatorics?

Generating functions provide a systematic and organized approach to solving problems in combinatorics. They can also help in finding closed-form solutions, as well as providing insights into the underlying structure of a problem.

5. What are some common techniques used when working with generating functions in combinatorics?

Some common techniques used when working with generating functions in combinatorics include partial fractions, series expansion, and the method of coefficients. These techniques help in simplifying and solving problems involving generating functions.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
446
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
596
  • Calculus and Beyond Homework Help
Replies
2
Views
809
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
14
Views
597
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
14
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
486
Back
Top