Next, we apply the Newton's binomial theorem to get that(-4z)*=(-1)*+1411f(a)=2-22k≥1(-1)k-12((2k-2)!Afterpluggingtheobtainedexpressionof(-wegetthatRl(k-1)!()=二±=Z(2k-2)(k-1k(k-k>1Note that f(r) is the generating function of [bk), therefore/2k-2bk=This finishes the proof.-1.9Random WalksConsider a real axis with integer points (0,+1, ±2,±3,..) marked. A frog leaps among theinteger points according to the following rules:(1). At beginning, it sits at 1.(2).In eachcoming step,thefrogleaps eitherbydistance2to theright (from ito i+2),orbydistance 1to theleft (from ito i-1),each of which is randomly chosen with probability independently of each other.Problem 1.55. What is the probability that the frog can reach " 0"?Solution. In each step, we use "+" or "_" to indicate the choice of the frog that is either to leapright or leap left.Then theprobability space 2 can beviewed as the set of infinite vectors, whereeach entry is in [+, -].Let A bethe event that the frog reaches 0.Let A; be the event that the frog reaches 0 at theith step for the first time. So A = UA, is a disjoint union. So P(A)= P(A,).To compute P(A,),we candefine atobethenumberoftrajectories(or vectors)of thefirsti steps such that the frog starts at 1 and reaches O at the ith step for the first time. SoaiP(Ai) =2iThen,oaiP(A) =>Let f(r) = E air' be the generating function of [aijiz0, where ao := 0. Thus,aiP(A) =1=12116
Next, we apply the Newton’s binomial theorem to get that f(x) = 1 2 − 1 2 X k≥0 1 2 k (−4x) k = X k≥1 (−1)k+14 k 2 1 2 k x k . After plugging the obtained expression of 1 2 k = (−1)k−12 4 k · (2k−2)! k!(k−1)! , we get that f(x) = X k≥1 (2k − 2)! k!(k − 1)!x k = X k≥1 1 k 2k − 2 k − 1 x k . Note that f(x) is the generating function of {bk}, therefore bk = 1 k 2k − 2 k − 1 . This finishes the proof. 1.9 Random Walks Consider a real axis with integer points (0, ±1, ±2, ±3, · · ·) marked. A frog leaps among the integer points according to the following rules: (1). At beginning, it sits at 1. (2). In each coming step, the frog leaps either by distance 2 to the right (from i to i + 2), or by distance 1 to the left (from i to i − 1), each of which is randomly chosen with probability 1 2 independently of each other. Problem 1.55. What is the probability that the frog can reach “ 0”? Solution. In each step, we use “+” or “−” to indicate the choice of the frog that is either to leap right or leap left. Then the probability space Ω can be viewed as the set of infinite vectors, where each entry is in {+, −}. Let A be the event that the frog reaches 0. Let Ai be the event that the frog reaches 0 at the i th step for the first time. So A = ∪ +∞ i=1 Ai is a disjoint union. So P(A) = P+∞ i=1 P(Ai). To compute P(Ai), we can define ai to be the number of trajectories (or vectors) of the first i steps such that the frog starts at 1 and reaches 0 at the i th step for the first time. So P(Ai) = ai 2 i . Then, P(A) = X +∞ i=1 ai 2 i . Let f(x) = P+∞ i=0 aix i be the generating function of {ai}i≥0, where a0 := 0. Thus, P(A) = X +∞ i=1 ai 2 i = f 1 2 . 16
We then turn to find the expression of f(r)Let b, be the number of trajectories of the first i steps such that the frog starts at “2" andreaches "o" at the ith step for the first time.Let c, be the number of trajectories of the first i steps such that the frog starts at “3" andreaches "o"at the ith step for the first time.First we express b, in terms of [ajbi≥1. Since the frog only can leap to left by distance 1,if the frog can successfully jump from "i" to “"o" in i steps, then this frog must reach "1" first.Let j be the number of steps by which the frog reaches “1" for the first time. So there are ajtrajectories from"2"to"1"at the jth step for thefirst time.in the remaining i-j steps thefrogmust jump from “1" to "0" and reach “0" at the coming (i-j)th step for the first time, so thereare ai-j trajectories that the frog can finish in exactly i-j steps. In total,i-1b =ajai-j.j=1As aj = 0,2ajai-ibi =j=0We can getbir=(airi)=f(a).i>0i>0Similarly,if we count the number c,of trajectories from 3to O, we can obtain that.ci=Lajbi-j,j=0whichimpliesthat73()i>0i>0(i>0Let us consider a from another point of view. After the first step, either the frog reaches "o"directly (if it leaps to left, so ai = 1), or it leaps to "3. In the latter case, the frog needs to jumpfrom"3"to"o"usingi-1 steps.Thus for i≥2,ai=ci-1.Combiningtheabovefacts,wehave+00+Af(n)=air=r+az=r+c-1r+r·f3()T+CiTi=0i>2(=0i>2Let a := P(A) = f(1/2). Then a = +%, ie., (a -1)(a2 +a -1) = 0, implying thatV5-1-V5-1Q=112Since P(A) e [0,1], we see P(A) = 1 or V5-117
We then turn to find the expression of f(x). Let bi be the number of trajectories of the first i steps such that the frog starts at “2” and reaches “0” at the i th step for the first time. Let ci be the number of trajectories of the first i steps such that the frog starts at “3” and reaches “0” at the i th step for the first time. First we express bi in terms of {aj}j≥1. Since the frog only can leap to left by distance 1, if the frog can successfully jump from “i” to “0” in i steps, then this frog must reach “1” first. Let j be the number of steps by which the frog reaches “1” for the first time. So there are aj trajectories from “2” to “1” at the j th step for the first time.in the remaining i − j steps the frog must jump from “1” to “0” and reach “0” at the coming (i − j) th step for the first time, so there are ai−j trajectories that the frog can finish in exactly i − j steps. In total, bi = X i−1 j=1 ajai−j . As aj = 0, bi = X i j=0 ajai−j . We can get X i≥0 bix i = (X i≥0 aix i ) 2 = f 2 (x). Similarly, if we count the number ci of trajectories from 3 to 0, we can obtain that ci = X i j=0 aj bi−j , which implies that X i≥0 cix i = X i≥0 bix i X i≥0 aix i = f 3 (x). Let us consider ai from another point of view. After the first step, either the frog reaches “0” directly (if it leaps to left, so a1 = 1), or it leaps to “3”. In the latter case, the frog needs to jump from “3” to “0” using i − 1 steps. Thus for i ≥ 2, ai = ci−1. Combining the above facts, we have f(x) = X +∞ i=0 aix i = x + X i≥2 aix i = x + X i≥2 ci−1x i = x + x X +∞ j=0 cjx j = x + x · f 3 (x). Let a := P(A) = f(1/2). Then a = 1 2 + a 3 2 , i.e., (a − 1)(a 2 + a − 1) = 0, implying that a = 1, √ 5 − 1 2 , or − √ 5 − 1 1 . Since P(A) ∈ [0, 1], we see P(A) = 1 or √ 5−1 2 . 17
Note that f(n) =+af3(a). Consider the inverse function of f(a), that is, g(r) := Consider the figure of g(a). We find that g(r) is increasing around -1 but decreasing around1. Since f() = airi is increasing, g(r) also increases. Thus it doesn't make sense for g(r)being around a = 1. This explains that P(A) = -1.1.10 ExponentialGeneratingFunctionsLet N, Ne and N。 be the sets of non-negative integers, non-negative even integers and non-negativeodd integers, respectively.Given n sets Ij of non-negative integers for j e [n], let fi(a) = Ziel, r'. Let ak be thenumber of integer solutions to i + i2 + ... + in = k, where ij e Ij.. Then II'=i fi(a) is theordinary generating function of (ax)k≥0.Problem 1.56. Let Sn be the number of selections of n letters chosen from an unlimited supplyof a's, b's and c's such that both of the numbers of a's and b's are even.Solution. We can write Sn asZ1.Sn =e1+e2+e3=n, e1,e2ENe,e3ENUsing the previous fact, we see that Sn =[r"]f, wheref(r).Problem 1.57. Let Tn be the number of arrangements (or words) of n letters chosen from anunlimited supply of a's, b's and c's such that both of the numbers of a's and b's are even.Whatis the value of Tn?Solution. To solve this, we define a new kind of generating functions.Definition 1.58. The erponential generating function for the sequence [ann>0 is the powerseries0anf(r)=Zan.n!n=0Then we have thefollowing fact.Fact 1.59. If we have n letters including r a's, y b's and z c's (i.e. r+y+z = n), then we canform yla distinct words using them.Therefore, a selection (say a's, y b's and z cs) can contribute ml arrangements to Tn.This implies thatn!Tn =ei+e2+eg=n, e1,eNe, gen elle2le3!18
Note that f(x) = x + xf 3 (x). Consider the inverse function of f(x), that is, g(x) := x 1+x3 . Consider the figure of g(x). We find that g(x) is increasing around √ 5−1 2 but decreasing around 1. Since f(x) = Paix i is increasing, g(x) also increases. Thus it doesn’t make sense for g(x) being around x = 1. This explains that P(A) = √ 5−1 2 . 1.10 Exponential Generating Functions Let N, Ne and No be the sets of non-negative integers, non-negative even integers and non-negative odd integers, respectively. Given n sets Ij of non-negative integers for j ∈ [n], let fj (x) = P i∈Ij x i . Let ak be the number of integer solutions to i1 + i2 + . + in = k, where ij ∈ Ij . Then Qn j=1 fj (x) is the ordinary generating function of {ak}k≥0. Problem 1.56. Let Sn be the number of selections of n letters chosen from an unlimited supply of a’s, b’s and c’s such that both of the numbers of a’s and b’s are even. Solution. We can write Sn as Sn = X e1+e2+e3=n, e1,e2∈Ne, e3∈N 1. Using the previous fact, we see that Sn = [x n ]f, where f(x) = X i∈Ne x i !2 X j∈N x j = 1 1 − x 2 2 · 1 1 − x . Problem 1.57. Let Tn be the number of arrangements (or words) of n letters chosen from an unlimited supply of a’s, b’s and c’s such that both of the numbers of a’s and b’s are even. What is the value of Tn? Solution. To solve this, we define a new kind of generating functions. Definition 1.58. The exponential generating function for the sequence {an}n≥0 is the power series f(x) = X∞ n=0 an · x n n! . Then we have the following fact. Fact 1.59. If we have n letters including x a’s, y b’s and z c’s (i.e. x + y + z = n), then we can form n! x!y!z! distinct words using them. Therefore, a selection (say x a’s, y b’s and z c’s) can contribute n! x!y!z! arrangements to Tn. This implies that Tn = X e1+e2+e3=n, e1,e2∈Ne, e3∈N n! e1!e2!e3! . 18
Similar to defining the above f(r) for Sn, we define the following for Tn. Letg(a) :=AiENClaim.Wehave[en]l = T.n!Proof. To see this, we expand g(r). Then the term r" in g(r) becomese3n!anre1ae2anZZTnn!ei!e!e3!erle2les!n!=1+1*cE1,e2ENe.E3EN1,e2ENe,3ENSo [r"lg = H, ie., g(r) is the exponential generating function of [Tn]. This finishes the proofof Claim.Using Taylor series: e* = Z;z0 and e- =D,≥0(-1)wehave2e"+e-rez.2-e-r:ZandJENJ!JENJ!22By the previous fact, we gete3r+2er+e3n +2+(-1)nnt+eg(r) =>n!244n>0Therefore, we get that3n + 2 +(-1)nTn=4器Recall that the erponential generating function for the sequence [anIn>o is the power series+00anf(r)=ann!n=0As we shall see, ordinary generation functions can be used to find the number of selections;while exponential generation functions can be used to find the number of arrangements or somecombinatorial objects involving ordering. We summarize this as the following facts.Fact 1.60. Given I, C N+ for j E [n], let f;(a) = E r. And let ak =71.Theniel,i1+...+in=k,ijelinIfi(a) =aak.k=0j=119
Similar to defining the above f(x) for Sn, we define the following for Tn. Let g(x) := X i∈Ne x i i! !2 X j∈N x j j! . Claim. We have [x n ]g = Tn n! . Proof. To see this, we expand g(x). Then the term x n in g(x) becomes X e1+e2+e3=n, e1,e2∈Ne, e3∈N x e1 e1! · x e2 e2! · x e3 e3! = X e1+e2+e3=n, e1,e2∈Ne, e3∈N n! e1!e2!e3! x n n! = Tn · x n n! . So [x n ]g = Tn n! , i.e., g(x) is the exponential generating function of {Tn}. This finishes the proof of Claim. Using Taylor series: e x = P j≥0 x j j! and e −x = P j≥0 (−1)j x j j! , we have e x + e −x 2 = X j∈Ne x j j! and e x − e −x 2 = X j∈No x j j! . By the previous fact, we get g(x) = e x + e −x 2 2 · e x = e 3x + 2e x + e −x 4 = X n≥0 3 n + 2 + (−1)n 4 · x n n! . Therefore, we get that Tn = 3 n + 2 + (−1)n 4 . Recall that the exponential generating function for the sequence {an}n≥0 is the power series f(x) = X +∞ n=0 an · x n n! . As we shall see, ordinary generation functions can be used to find the number of selections; while exponential generation functions can be used to find the number of arrangements or some combinatorial objects involving ordering. We summarize this as the following facts. Fact 1.60. Given Ij ⊆ N + for j ∈ [n], let fj (x) = P i∈Ij x i . And let ak = P i1+.+in=k, ij ∈Ij 1. Then Yn j=1 fj (x) = X +∞ k=0 akx k . 19
-Fact1.61.GivenI,CN+forjE[n], letgi(a)=Z.And letbk =ZThenlial.inT.iel,1+tjeljoobkkIg;(a)=)K!j=1k=0II fi(r). ThenFact 1.62. Let f(r) =7=[k]f =F[ri]fin=k,j=1520罩 ThenFact 1.63. Let f(r)=)II fi(r) and let f;(r) =k=0=+0oAkYf(r)1K:!k=0if and only ifK!()7aAk=iili2!..in!Jj=11. -ii≥0Exercise 1.64. Find the number an of ways to send n students to 4 different classrooms (sayRi,R2.R3.R4)suchthateachroomhas atleast1 students.Solution.n!>an=iilizligliy!Let Ij = [1, 2, ] for j e [4] and gi;() = Z =e-1.ByFact1.61,wehavethatM+80 na" = (e - 1)* = edr - 4e3r + 6e2 - 4e* + 1.>91929394=n=g n!Thusan=4n-4.3n+6.2n-4forn≥4.1Exercise 1.65. Let an be the number of arrangements of type A for a group of n people, and letbn be the number of arrangements of type B for a group of n people.Define a new arrangement of n people called type C as follows:·Dividethenpeopleinto2groups (say1stand 2nd). Then arrange the 1st group by an arrangement of type A, and arrange the 2nd group by anarrangement of type B.20
Fact 1.61. Given Ij ⊆ N + for j ∈ [n], let gj (x) = P i∈Ij x i i! . And let bk = P i1+.+in=k, ij ∈Ij k! i1!i2!.in! . Then Yn j=1 gj (x) = X +∞ k=0 bk k! x k . Fact 1.62. Let f(x) = Qn j=1 fj (x). Then [x k ]f = X i1+.+in=k, ij≥0 Yn j=1 [x ij ]fj . Fact 1.63. Let f(x) = Qn j=1 fj (x) and let fj (x) = + P∞ k=0 a (j) k k! x k . Then f(x) = X +∞ k=0 Ak k! x k , if and only if Ak = X i1+.+in=k, ij≥0 k! i1!i2!.in! Yn j=1 a (j) ij . Exercise 1.64. Find the number an of ways to send n students to 4 different classrooms (say R1, R2, R3, R4) such that each room has at least 1 students. Solution. an = X i1+i2+i3+i4=n, ij≥1 n! i1!i2!i3!i4! . Let Ij = {1, 2, .} for j ∈ [4] and gj (x) = P i≥1 x i i! = e x − 1. By Fact 1.61, we have that g1g2g3g4 = X +∞ n=0 an n! x n = (e x − 1)4 = e 4x − 4e 3x + 6e 2x − 4e x + 1. Thus an = 4n − 4 · 3 n + 6 · 2 n − 4 for n ≥ 4. Exercise 1.65. Let an be the number of arrangements of type A for a group of n people, and let bn be the number of arrangements of type B for a group of n people. Define a new arrangement of n people called type C as follows: • Divide the n people into 2 groups (say 1 st and 2 nd). • Then arrange the 1 st group by an arrangement of type A, and arrange the 2 nd group by an arrangement of type B. 20