- #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?
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?