-2
votes
0answers
27 views

Coefficient question in generating functions [on hold]

In each of the following, find the coefficient of $x^{2005}$ in the generating function $A(x)$. (a) $A(x) = (1 – 2x)^{5000}$ (b) $A(x) = \frac{1}{1 + 3x}$ (c) $A(x) = \frac{1}{(1 + 5x)^2}$ (d) ...
1
vote
2answers
77 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 ...
-1
votes
2answers
69 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
47 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
53 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
74 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
20 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
45 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
12 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
65 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
31 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
44 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
31 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
3answers
57 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
54 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
76 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
112 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 ...
1
vote
2answers
73 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
75 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
186 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
187 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
341 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
41 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
65 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
30 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
62 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
143 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
242 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
394 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
41 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
103 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
150 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
49 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
73 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
270 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
82 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
86 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 ...
1
vote
1answer
72 views

Generating function question about arranging n objects with limitations

Generating functions question: There are n objects - rings, earring and bracelets. How many ways are there to arrange these objects, as the amount of earring is even and there are at most 4 bracelets. ...
3
votes
3answers
125 views

Generating function: Find a closed form of $\sum_{k=0}^n (-3)^k(k+1)$

Find the closed form of $\sum_{k=0}^n (-3)^k(k+1)$. So the generating function would be: $$A(x)=1-6x+18x^2-108x^3...$$ So what I did notice is that its closed form is perhaps some variation of ...
1
vote
2answers
139 views

Is my solution correct? Generating functions question: How many non-negative solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?

so we began studying this subject, and I tried solving this question: How many non-negative and whole ($\in \Bbb Z$) solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have? I would like to ...
1
vote
1answer
89 views

Generating functions of partition numbers

I don't understand at all why: \begin{equation} \sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1} \end{equation} Where $p_n$ is the number of partitions of $n$. Specifically ...
2
votes
2answers
48 views

New to generating functions - how do I get the function from the sequence defined by $a_n= n$ for $n\geqslant 0$?

I'm given: $a_n= n$ for $n \geqslant 0$. I'm quite good at recursive generating functions, but I haven't came across a simpler one like this, so I'm sure I'm just overlooking something really basic.
6
votes
3answers
100 views

Solve recursive equation $ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1$

Solve recursive equation: $$ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1$$ $f_0 = 0, f_1 = 1$ What I have done so far: $$ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1- [n=0]$$ I ...
2
votes
1answer
93 views

Generating function for the number of choices $I,J\!\subseteq[n]$ such that $\max\,[n]\!\setminus\!(I\!\cup\!J) < \max I\!\cap\!J$

Suppose that each pair $I,J\!\subseteq[n]=\{1,\ldots,n\}$ for which $$\max\,([n]\!\setminus\!(I\!\cup\!J)) < \max (I\!\cap\!J) \tag{1}$$ contributes $t^{|I|+|J|}$ to a generating function, and ...
4
votes
2answers
500 views

Generating function for the sequence $1,1,3,3,5,5,7,7,9,9,\ldots$

The generating function for the sequence $\left\{1,1,1,1,...\right\}$ is $$1 + x + x^2 + x^3 ... = \frac{1}{1-x}$$ What is the generating function for the sequence $\left\{1,1,3,3,5,5,7,7,9,9,\dots ...
4
votes
1answer
128 views

Finding the number of 5-node labeled connected graphs via generating functions

Problem: Find the number of ways to connect a graph having 5 labeled nodes so that each node is reachable from every other node. I have solved this problem using principle of inclusion and exclusion ...
2
votes
2answers
82 views

How is $\frac{x}{(1-x)^2}$ the equation for the sequence $0, 1, 2, 3, 4,\dots$

Our prof said this for a homework question: I get that the function shown in a is $0, 0, 0, 0, 0, 0, 1, 2, 3, 4...$ But how is $\dfrac{x}{(1-x)^2}$ the sequence $0, 1, 2, 3, 4, ...$? For the ...