0
votes
1answer
41 views

Use generating functions to prove Pascal’s identity

How do I prove Pascal's identity using generating functions? $C(n,r) = C(n−1,r) + C(n−1,r−1)$ when $n$ and $r$ are positive integers with $r < n$. I am given the hint to use the identity ...
1
vote
2answers
54 views

Find a closed form for the generating function for this sequence

The sequence: $0, 0, 0, 1, 1, 1, 1, 1, 1, \ldots$ The book gives the answer of $\frac{x^3}{1-x}$ but I'm not sure how to get this answer. I understand the generating function of this sequence will be ...
4
votes
1answer
73 views

Closed form of $\sum_{k=0}^nk\binom{k}{3}\binom{2n}{k}$

Recently, I came across the following exercise on the course of discrete math Find a closed form for $\sum_{k=0}^nk\binom{k}{3}\binom{2n}{k}$ So I tried some of the usual techniques: Let ...
1
vote
1answer
41 views

How many ways you can make change for an amount N using A and B monets.

I encountered a quite interesting problem. The question is: How many ways you can make change for an amount N using monets of value A and B, knowing that GCD(A,B)=1. Any idea how to solve this? It ...
4
votes
4answers
84 views

Find a generating function for $\sum_{k=0}^{n} k^2$

Find a generating function for $\sum_{k=0}^{n} k^2$ I know my solution is wrong, but why? My solution: If $F(x)$ generates $\sum_{k=0}^{n} k^2$ then $F(x)(1-x)$ generates $k^2$. ...
1
vote
1answer
31 views

Expressing the generating function defined by $b_n = \sum_{k=0}^{n} 3^k\cdot a_k$

The title is probably somewhat unclear, sorry if it is.. Let $F$ be the generating function of the sequence $(a_n)_{n=0}^{\infty}$ Use $F$ to express the generating function for ...
1
vote
1answer
24 views

Generating functions for $n*2^n$ & the seq a0+a1+a2+…

1) What is the generating function of $a_n = n2^n, n\geq0$? My answer: $f(x) = \sum a_nx^n = \sum n2^nx^n = \sum n(2x)^n$, but I have no idea where to go from here. 2) Let the sequence $s_n = a_0 + ...
2
votes
1answer
42 views

Generating function - What is the coefficient of $x^{26}$?

What is the coefficient of $x^{26}$ given the function: $${\left[ {{{1 + {x^{10}}} \over {{{(1 - x)}^7}}}} \right]^2}$$ My work: $${\left[ {{{1 + {x^{10}}} \over {{{(1 - x)}^7}}}} \right]^2} = \left( ...
0
votes
0answers
46 views

Expectation and Variance of a Discrete Uniform Distribution using the Probability Generating Function and Cumulant Generating Function

Hi I just derived the MGF of a discrete uniform distribution and found it to be: [e^t - e^t(m+1)]/(1 - e^t)m and the pgf is ...
1
vote
1answer
194 views

Derive expressions for the formal power series $\cos(kz)$ and $\sin(kz)$, where $k$ is an arbitrary integer

I'm working on some past exam questions, and I am struggling with the second part of this question: Define the formal power series by the formulas: $$\sin(z) = \sum^{\infty}_{n=0} ...
3
votes
4answers
161 views

Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$

$g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$ With initial conditions $g_{0} = 23, g_{1} = 37, g_{2} = 42 $ This is a practice question I'm working on, and I'm running into absurd amounts of ...
1
vote
2answers
89 views

Generating Functions for collection of balls

There are 10000 identical red balls, 10000 identical yellow balls and 10000 identical green balls. In how many different ways can we select 2005 balls so that the number of red balls is even or the ...
-2
votes
2answers
105 views

Using generation functions solve the following difference equation

Using generation functions solve the following difference equation $$ a_{n+1} - 3a_{n+2} + 2a_n = 7n ; n\geq0; a_0 = -1; a_1 = 3. $$
1
vote
2answers
53 views

Coefficients of this generating function

For the first part of a problem, I solved the generating function to be $F(x) = \frac{x^3}{(1-x)^2}$ Now it's the easy part that has me a little confused. What would the coefficients be in this case? ...
0
votes
0answers
62 views

Alternating permutation exponential generating function

A permutation pi is alternating if pi_1 > pi_2 < pi_3 > pi_4 <….Let a(n) be the number of alternating permutations of size n. (a) Find a recurrence relation for a(n). (b) Evaluate the ...
0
votes
1answer
83 views

Round table exponential generating function

Let $r(n)$ be the number of different ways to seat $n$ people around a round table. Find the exponential generating function for $r$. I believe $r(n)$ is just equal to $n!/n = (n-1)!$. So then I ...
0
votes
0answers
24 views

probability in graphs - degree distribution

I am reading this paper on networks which employs probability in analyzing graphs. Suppose that a graph has $n$ vertices. Furthermore, if each vertex has a probability $p_k$ of having $k$ neighbors, ...
0
votes
2answers
47 views

Obtaining a linear recurrence from differential equation

I need some guidance with the following problem. I have a sequence $L_0,L_1,\ldots$ whose ordinary generating series satisfies $$L(x) = \sum_{n=0}^{\infty} L_n \frac{x^n}{n!} = \frac{1}{2-e^x}.$$ ...
0
votes
0answers
15 views

Derive a formula for a number of set divisions

Let $D(n;a_1,\ldots,a_m)$ be the number of divisions n for factors of the size belonging to the set$\{a_1, a_2,\ldots, a_m\}$. Show that: $1/(1-t^{a_1})(1-t^{a_2})\ldots(1-t^{a_m})$ is a generating ...
3
votes
3answers
68 views

Calculate $\sum_{n\geq 0}\frac{H_n}{10^n}$

Question is like in the title and my attempt is Let have sequence $$a_n = <\frac{H_0}{10^0},\frac{H_1}{10^1},\frac{H_2}{10^2},\dots>$$ where $H_n$ is n-th harmonic number. And we have to ...
1
vote
1answer
45 views

Easy generating functions task from concrete mathematics book

This question might seem very novice, but i'm not sure about the solution. We have domino puzzle of size $2 \times\ n$ and we get 4 points for every vertical block and 1 point for horizontal block, ...
0
votes
2answers
25 views

Help with finding the generating function (with a constant )

How do you get the generating function from this formula: $8(1+x)^{7}$ I have the following formula for $(1+x)^{n}$ : $n\choose 0$ + $n \choose 1$$x^1$ + $n \choose 2$$x^2$+... +$n \choose ...
0
votes
2answers
45 views

Calculate the $26$ term for the generating function.

Let $\lambda x.(1+x+x^{10})^{20}$. What is the the $26$ term for the series generated by this function? Thanks.
0
votes
2answers
36 views

Finding a generating function for a recursion

Let $a_1=2, a_2=10$ and $a_n=2a_{n-1}+3a_{n-2}$. I want to find the generating function, $F(x)$ for this recursion: $$F(x) = 2 + 10x + \sum\nolimits_{n \ge 2} {(2{a_{n + 1}} + 3{a_n}) \cdot {x^n}} ...
1
vote
2answers
85 views

In how many ways can you divide bonuses between employees?

How many ways are there to divide 33 000 USD between 22 employees of a company (including 1 president, 1 vice-chairman and 20 normal employees), if a normal employee can get 1000 or 1500 USD, whereas ...
3
votes
0answers
61 views

Find generating function For sequences

Can anyone out here help? The exercise says: "Find the generating function for each of the sequences below (the general term is given)" Now, the question is how do you find one for those: a) $U_n = ...
1
vote
1answer
101 views

Use generating functions to determine how many four-element subsets of S = {1,2,3,4,…15} contain no consecutive integers?

Use generating functions to determine how many four-element subsets of $$S = {1,2,3,4,...15}$$ contain no consecutive integers? How do you approach this problem?
0
votes
1answer
170 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
0
votes
2answers
196 views

Find a closed form for the generating function for each of these sequences

ind a closed form for the generating function for each of these sequences. (Assume a general form for the terms of the sequence, using the most obvious choice of such a sequence.) a) 0, 0, 3, -3, 3, ...
1
vote
5answers
82 views

Problem with understanding generating functions.

I am given generating functions $f(x)= \frac{x}{1-x}$ or $f(x)=\frac{1}{1+x^{2}}$ or $f(x)=\frac{1}{x^2-5x+6}$ and I am obliged to write sequence which are generated by this functions. What is the ...
3
votes
1answer
190 views

Find the sum of the series.

I need to find the following sum: $$\sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s}$$ First I tried to simplify this: $$\begin{split} \sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s} &= ...
1
vote
3answers
287 views

Find the coefficient of $x^9$ in the power series of each of these functions.

Find the coefficient of $x^9$ in the power series of each of these functions. a) $(x^3 + x^5 + x^6)(x^3 + x^4)(x + x^2 + x^3 + x^4 +\cdots)$ b) $(x + x^4 + x^7 + x^{10} +\cdots )(x^2 + x^4 + x^6 + ...
0
votes
1answer
689 views

Find a closed form for the generating function for each of these sequences.

Find a closed form for the generating function for each of these sequences. (Assume a general form for the terms of the sequence, using the most obvious choice of such a sequence.) ...
0
votes
1answer
73 views

Generating Function of a Recurrence Relation.

Given a sequence a(n) = a(n -2) , a(0) = 2 , a(1) = -1 Find the generating function What i have done so far: The recurrence relation is going to be a(n) - a(n-2) = 0 A = the generating function A ...
0
votes
2answers
70 views

generating function and binomial distribution - counting

I am trying to understand generating function. I have the following problem: There are 50 students in the International Mathematical Olympiad (IMO) training programme. 6 of them are to be selected to ...
1
vote
1answer
36 views

Generating function for division of $n$ into smaller subsets.

I need to find the generating function for the number of ways of dividing $n$ into parts out of even numbers. The ways are only different if their parts are different, meaning that $2+1+2$ and $2+2+1$ ...
1
vote
1answer
70 views

Using Generating Series to Find Sum of Sides of Dice

Question: " Let k be a non-negative integer. Use the theory of generating series to find the expected value of the sum of the dots when k (6-sided) dice are rolled. " I know that the generating ...
1
vote
1answer
157 views

Finding recurrence relation given the generating function

So I'm given the generating function $F(x)={1+2x\over1-3x^2}$ I'm supposed to find the recurrence relation satisfied by fn. I managed to get it into 2 separate geometric series and derive $f_n = ...
1
vote
1answer
324 views

About the generating function of the sum of roll dice values.

I thought this exercise would be fairly easy, but it seems i can't find a proper approach to it. I have to prove that $f(x) = (1-x-x^2-x^3-x^4-x^5-x^6)^{-1}$ is the function that generates the number ...
1
vote
1answer
52 views

Find generating function of given problem?

please help me to find the generating function of this problem $a_k = ( k + 1) for  k=0,1,2,3,...$
1
vote
2answers
432 views

Generating Functions in Discrete Mathematics in Computer Science

Hey Guys can anyone help me with the following question in Discrete Structures in Mathematics, relating generating functions Find a closed form for the generating function for the sequence $\{a_n\}$, ...
0
votes
1answer
47 views

Generating function question

let say I have $90 balls$ $S_{1} = $ green balls $S_{2} = $ orange balls $S_{3} = $ red balls I have the following limitations: No limit Choose at most 60 balls from each color choose even ...
0
votes
1answer
131 views

How to obtain asymptotic form for sequence, given generating function

Let $a_n$ be the number of ways to obtain the amount of $n$ cents, using a supply of 1-cent coins, 3 types of 2-cent coins, and 4-cent coins. Then, $a_n$ is the coefficient of $x^n$ in ...
1
vote
1answer
179 views

Generating functions homework question 3

This is a Homework question Determine the Closed Form generating function for the sequence $a_0,a_1,a_2...,$ where $a_n$ is the number of partitions of the non negative integer n into a) even ...
0
votes
1answer
50 views

Generating Functions Homework Question 2

This is a HW question The question is to use generating functions to count the number of six digit (positive) integers whose digits sum to $42$. Ex. $978468$ is a six digit integer whose digits sum ...
3
votes
2answers
75 views

generating function Homework Question 1

This is a HW question I am asked to find a closed form generating function for $1,1,0,1,1,0,1,1,0....$ so then $f(x)=x^0+x^1+0x^2+x^3+x^4+0x^5+x^6+x^7+0x^8$ could use some hint or help.
0
votes
2answers
306 views

Recurrence relations and generating functions question

Let $A_n$ be the set of different paving of a $2\times n$ using $2\times 1$ or $1 \times 2$ tiles. We'll define $a_n$=$|A_n|$. 1] Find recurrence relation: I found it -> $a_n=a_{n-1}+a_{n-2}$ with ...
0
votes
1answer
67 views

A small question about generating functions

just a small question: When should I use infinite geometric sequence and when should I use finite geometric sequence when solving problems involving combinations? For instance, for the problem: How ...
3
votes
1answer
90 views

Interpretation of generating function infinite product

Let $P$ denote the set of primes and let $s\in\{-1,1\}$. How can you interpret the coefficient of $x^n$ in the power series expansion of $$\prod_{p\in P} (1+sx^p)^s$$ for either choice of $s$? I ...
1
vote
1answer
97 views

Generating functions combinatorical problem

In how many ways can you choose $10$ balls, of a pile of balls containing $10$ identical blue balls, $5$ identical green balls and $5$ identical red balls? My solution (not sure if correct, would ...