what is a closed form for the sequence associated to the generating function 2x2 ?

Generating functions

An important thought in mathematics is to establish connections betwixt two fields in club to apply cognition in one field to the other field, or at least accept a problem in one field and transform it to a trouble in the other field. This idea motivates the idea of a generating role, which establishes a connectedness between functions of a real variable and sequences of numbers.

Definition: Given a numeric sequence the series is called the generating part of the sequence.

To detect the generating role for a sequence means to detect a closed form formula for f(x), one that has no ellipses.

Case: The generating part for the constant sequence , has airtight form

This is because the sum of the geometric serial is (for all x less than i in accented value).

> f(x) =sum(x^'i','i'=0..infinity);

>

Problem: Find the generating function for

Problem: Observe the generating function for

Trouble: Find the generating function for

Problem: Suppose f(x) is the generating role for a and g(x) is the generating function for b. Show that f(ten) + thou(x) is the generating function for a + b, but that f(x) * g(10) is not the generating function for a*b.

Definition: The convolution of two sequences a and b is the sequence c defined by

Problem : Suppose f(x) is the generating function for a and g(x) is the generating part for b. Bear witness that is the generating function for the convolution of a and b.

Every role which has derivatives of all orders at 0 is the generating role of its Taylor expansion at 0.

> one/(1-x)=series(1/(1-ten),ten,20);

Uses of generating functions

One use for generating functions is become closed formulas for sequences which are defined recursively in terms of previous terms. The defining equations for such sequences are called recurence relations

Problem: Discover a formula for the nth term of the sequence defined by , and .

Investigation. This rule is direct programmable in Maple, using a recursive program (g refers to itself in its definition).

> 1000 := proc(n) options remember; if n = 0 then 1 else 5*m(n-1) - 3 fi end;

> one thousand(100);

> seq(a[n]=g(north),north=0..ten);

>

A Solution using generating functions.

=

=

=

= =

Doing a fractional fraction decomposition of the right hand side

> convert((1-4*x)/((1-five*x)*(1-x)),parfrac,x);

f(x) =

f(x) =

So by inspection, we see the formula for

Checking this,

>

> p :=unapply(5^due north-3*(sum(5^'i','i'=0..due north-i)),n);

> m := n-> (v^n+3)/4;

> seq(1000(n),north=0..ten);

> seq(g(n),n=0..10);

> seq(p(n),n=0..10);

> f(x) := collect(sum(a[i]*x^'i','i'=0..5),ten);

> expand( five*f(ten)*x);

Really, DeMoivre introduced the notion of generating office in 1730 to solve recurrence relations. Here is a famous one kickoff defined past Fibonacci in 1200.

Problem: Given that , find a airtight formula for

Another employ for generating functions is to solve counting problems . Well-nigh counting problems prevarication in a sequence of counting problems. If we can identify the generating function of that sequence nosotros have a cleft at finding the formula to solve the counting problems in the sequence.

Case. For fixed n, let C(due north,r) exist the number of combinations of northward things taken r at a time, r = 0 to n. The generating function for this sequence is .

The way to see this is to think of how the coefficient of in the expansion of is fabricated up. The expansion of has terms before collecting is done. Each term is a product north things some of which are x'due south and the remainder one'southward. The coefficient of is the number of those terms which has exactly r x'south. We tin programme this directly in Maple.

> binom := proc(n,r)
local x,cof;
if r = 0 or r=n then one else
coeff( aggrandize( (ane+ten)^n),x,r) ;
fi end:

> seq(binom(4,i),i=0..4);

So, for example, the number of ways to choose 10 books from a library of 40 books is

> binom(forty,10);

Checking that with the Maple word binomial --

> binomial(xl,10);

Aforementioned result.

Problem. How many Lotto tickets have only even numbers? prime numbers?

Problem . Show that for all positive integers due north and r with r < n, .

Problem. Bear witness that

This is simply the tip of the iceberg. The answers to many many counting problems are coefficients of certain polynomial generating functions.

Trouble. A library has 5 blackness books, iv red books, and 3 yellow books, all with different titles. How many means can a student accept home half dozen books, ii of each color?

Solution. Let . When A(x,y,z) is expanded out, it will accept terms each of which the production of 5 10's or one'southward with four y's or i'south and iii z's or i's. Each term can exist thought of every bit a checkout set of books. 1x111 yy11 1z1 ways the 2nd black, 1st and 2nd crimson and second yellow books were checked out. With that interpretation, the coefficient of is reply we seek, and this can be obtained by expanding out and collecting like terms.

> A := (i+x)^5*(1+y)^iv*(1+z)^iii;

> cf :=coeff(collect(expand(A) ,10),x^2);

> cf :=coeff(collect(cf ,y),y^2);

> cf :=coeff(collect(cf ,z),z^2);

Second Solution: Choose 2 of the five blacks, then choose ii of the iv reds, and concluding choose 2 of the iii yellows. This gives

> binom(5,2)*binom(4,2)*binom(3,2);

Problem. A library has 5 indistinguishable black books, 4 indistinguishable reddish books, and 3 duplicate yellow books. How many distinguishable means can a student have home six books, 2 of each color?

Solution 1 . The student chooses 2 black books (only one way to do that since the black books are indistinguishable) then 2 reds then ii yellows. The set of things we are counting is the cartesian product of three sets each with 1 chemical element, then the answer is 1.

Solution 2. Recall of choosing the blackness books first: since they are indistinguishable amonst each other, the but distinguishing characteristic of the choice is the number of black books chosen. Nosotros could represent this past choosing a term of the polynomial ; thus choosing the term ane ways no black books are chosen, etc. Similarly choosing the red books would be to choose a term of and choosing the yellow books would be to cull a term of . The polynomial when expanded has 6*5*4 = 120 terms (none alike), each of which represents a distinguisable way of taking home a set up of books from the library, including the term 1*ane*1 which is taking home the empty set of books. The coefficient of is ane which is the number of ways to accept home 6 books, two of each colour.

Problem. A library has 5 indistinguishable black books, four indistinguishable cerise books, and 3 duplicate yellow books. How many distinguishable means can a student take domicile 6 books, at to the lowest degree 1 of each color?

Solution one. Direct count. Make a list. of the triples [x,y,z] of integers satisfying x+y+z = 6, ane<= ten <=5, 1 <= y <= iv, and one <= z <= 4. [4,1,1], [iii,2,1],[3,1,ii], [2,three,1],[2,two,2],[2,1,3], [one,2,3],[one,iii,two],[one,4,1]. There are 9.

>

Solution two. Every bit above, we can course a polynomial p = , where the term 1 has been left out of each gene since at least one book of each colour is to be chosen. When expanded this polynomial has 5*iv*iii = sixty terms, each representing a way for the pupil to have dwelling house a set of books at least 1 of each color. What nosotros want is the number of terms of caste half dozen. Those represent the ways a pupil could take home half-dozen books, at least one of each color. If nosotros set x = y = z in p and collect similar terms then the coefficient of is the desired reply.

> p := (ten+x^2+ten^iii+ten^4+10^5)*(y+y^two+y^3+y^4)*(z+z^2+z^3);

> q :=subs({y=x,z=ten},p);

> coeff(q,x^six);

>

Problem. A library has 5 indistinguishable black books, 4 indistinguishable red books, and 3 indistinguishable yellow books. How many distinguishable ways can a student take domicile six books?

Solution 1. Direct count. Make a list. of the triples [x,y,z] of integers satisfying x+y+z = 6, 0<= x <=5, 0 <= y <= 4, and 0 <= z <= iv.

Solution ii. Polynomial solution.

> p := (i+x+x^2+x^3+x^4+10^five)*(i+y+y^2+y^3+y^iv)*(1+z+z^two+z^3);

> q :=subs({y=x,z=x},p);

>

> coeff(q,x^6);

>

fuentezguesse.blogspot.com

Source: http://www.ms.uky.edu/~carl/ma502/html/genfun2sln1.html

Share this post