MATH 184 HOMEWORK 4
Math 184, Winter 2022
Homework 4
Due: Friday, Feb. 11 by 11:59PM via Gradescope (late homework will not be accepted)
Explanations should be given for your solutions. Use complete sentences.
(1) If $\sum_{n \geq 0} a_{n} x^{n}=\frac{2+3 x^{2}-2 x^{3}}{(1-5 x)^{5}}$, find a closed formula for $a_{n}$.
(2) Define a sequence by
$$
a_{0}=1, \quad a_{1}=3, \quad a_{n}=8 a_{n-1}-16 a_{n-2}+3^{n} \quad \text { for } n \geq 2 .
$$
(a) Express $A(x)=\sum_{n \geq 0} a_{n} x^{n}$ as a rational function in $x$.
(b) Find a closed formula for $a_{n}$.
(3) Let $S(n, k)$ be the Stirling number of the second kind. For each $k \geq 1$, define the ordinary generating function
$$
\mathbf{S}_{k}(x)=\sum_{n \geq 0} S(n, k) x^{n} .
$$
(a) For $k \geq 2$, translate the identity from lecture
$$
S(n, k)=S(n-1, k-1)+k \cdot S(n-1, k)
$$
into an identity involving $\mathbf{S}_{k}(x)$ and $\mathbf{S}_{k-1}(x)$.
(b) Use the identity you found in (a) and induction on $k$ to show that for all $k \geq 1$ :
$$
\mathbf{S}_{k}(x)=\frac{x^{k}}{(1-x)(1-2 x) \cdots(1-k x)} .
$$
(4) You want to build a stack of blocks that is $n$ feet high. You have 3 different kinds (unlimited of each): green blocks are 1 foot high, while red and blue blocks are 2 feet high. Blocks of the same color are considered indistinguishable. Let $a_{n}$ be the number of ways to stack these blocks.
Find a linear recurrence relation and initial conditions satisfied by $a_{n}$.
(5) You are designing a race that takes place over $n$ blocks in a city. It will consist of 3 portions: running, followed by biking, and ending with another running portion. The end of a portion should match up with the end of a block. The first running portion needs to designate 3 blocks to have a first aid tent, and the biking portion needs to designate 4 blocks to have a first aid tent. The second running portion doesn’t need anything, but must have positive length. Use generating functions to find a formula for the number of ways to design a race under these conditions.
(6) Let $n$ be a positive integer and let $a_{n}$ be the number of different ways to pay $n$ dollars using only $1,2,5,10,20$ dollar bills in which at most three 20 dollar bills are used. Express $A(x)=\sum_{n \geq 0} a_{n} x^{n}$ as a rational function.
Math 184 – Enumerative Combinatorics
MATH 184组合学代写， MATH 184代写请认准UpriviateTA. UpriviateTA为您的留学生涯保驾护航。
Math 184 – Enumerative Combinatorics (Winter 2022)
- Lecture times and location: TuTh 12:30PM – 1:50PM via Zoom (see Canvas for link)
- Textbook: Miklós Bóna, A Walk Through Combinatorics, third ed.
- Instructor: Steven Sam email
- Instructor office hours: Zoom (see Canvas for link), Tu 11:30AM-12:20PM, Th 2PM-3PM, F 2PM-3PM
- TA office hours: see Canvas for info
- Course syllabus: link
- Discord server: see Canvas for link
Homework
Submit homework through Gradescope.
- Homework 1 (due 1/14)
- Homework 2 (due 1/21)
- Homework 3 (due 2/4)
- Homework 4 (due 2/11)
Notes for course
- Notes (last updated 2/1/22)
Schedule
Lectures will be recorded, see Canvas for the videos.
| Jan 4 | Sample of problems to be studied in course Bijections (Section 1.1, 1.2 of notes) 12-fold way (Section 1.3 of notes) Review of weak induction (Sections 1.4 of notes) pdf from lecture |
| Jan 6 | Review of strong induction (Section 1.5 of notes) Permutations (Bona 3.1, notes 2.1) Words (Bona 3.2, notes 2.2) pdf from lecture |
| Jan 11 | Choice problems (Bona 3.3, notes 2.3) pdf from lecture |
| Jan 13 | Compositions (Bona 5.1, notes 3.1) Set partitions (Bona 5.2, notes 3.2) pdf from lecture |
| Jan 18 | Integer partitions (Bona 5.3, notes 3.3) pdf from lecture |
| Jan 20 | Binomial theorem (Bona 4.1, notes 4.1) Multinomial theorem (Bona 4.2, notes 4.2) pdf from lecture |
| Jan 25 | Quiz 1 |
| Jan 27 | Formal power series (notes 5.1) pdf from lecture |
| Feb 1 | General binomial theorem (notes 5.2) Linear recurrence relations (Bona 8.1.1, notes 6.1) pdf from lecture |
| Feb 3 | Combinatorial interpretations for OGF (Bona 8.1.2, notes 6.2) Partition generating functions (notes 6.3) pdf from lecture |
| Feb 8 | Catalan numbers (Bona 8.1.2.1, Section 6.4 of notes) pdf from lecture |
| Feb 10 | Exponential generating functions (Bona 8.2.1, Section 7.1 of notes) Products of EGFs (Bona 8.2.2, Section 7.2 of notes) pdf from lecture |
| Feb 15 | Quiz 2 |
| Feb 17 | |
| Feb 22 | |
| Feb 24 | |
| Mar 1 | |
| Mar 3 | |
| Mar 8 | Quiz 3 |
| Mar 10 | |
| Mar 15 | Final exam: 11:30AM-2:29PM |
