Question #304661

8. Find a generating function for the sequence (a0, a1,....ar.....), where ar=the number of non negative integral solutions to e1+e2 +....en=r where 0 less than or equal to e1 less than or equal to 1 for each i=1,2,3,.....n


1
Expert's answer
2022-03-07T04:57:01-0500

The number of non-negative integral solutions to e1+e2 +...+en=r, where ei{0,1}e_i\in\{0,1\} is equal to the number of all r-subsets of the set In={0,1,,n}I_n=\{0,1,\dots,n\}.

The 1-to-1 correspondence can be given as following:

AIn(e1,e2,,en){0,1}n:ei=1iffiAA\subset I_n \leftrightarrow (e_1,e_2,\dots,e_n)\in\{0,1\}^n: e_i=1\, {\rm iff }\, i\in A

The number of all r-subsets of the set InI_n , is equal to the binomial coefficient (nr)\binom{n}{r}.

Therefore, the generating function for the sequence (a0,a1,,ar,)=((n0),(n1),,(nr),)(a_0, a_1,\dots,a_r,\dots)=(\binom{n}{0},\binom{n}{1},\dots,\binom{n}{r},\dots) is

f(z)=r=0arzr=r=0(nr)zr=(1+z)nf(z)=\sum\limits_{r=0}^{\infty}a_rz^r=\sum\limits_{r=0}^{\infty}\binom{n}{r}z^r=(1+z)^n

The final answer does not depend on rr, because, by definition, a generating function f(z)f(z) for the sequence (a0, a1,....ar.....) is the sum of the series f(z)=r=0arzrf(z)=\sum\limits_{r=0}^{\infty}a_rz^r, which does not depend on rr.

Answer. f(z)=(1+z)nf(z)=(1+z)^n


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS