Answer to Question #304661 in Discrete Mathematics for Tege

Question

8. Find a generating function for the sequence (a₀, a₁,....a_r.....), where ar=the number of non negative integral solutions to e₁+e₂ +....e_n=r where 0 less than or equal to e₁ less than or equal to 1 for each i=1,2,3,.....n

Answer 1

The number of non-negative integral solutions to e₁+e₂ +...+e_n=r, where $e_i\in\{0,1\}$ is equal to the number of all r-subsets of the set $I_n=\{0,1,\dots,n\}$.

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

$A\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 $I_n$ , is equal to the binomial coefficient $\binom{n}{r}$.

Therefore, the generating function for the sequence $(a_0, a_1,\dots,a_r,\dots)=(\binom{n}{0},\binom{n}{1},\dots,\binom{n}{r},\dots)$ is

$f(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 $r$, because, by definition, a generating function $f(z)$ for the sequence (a₀, a₁,....a_r.....) is the sum of the series $f(z)=\sum\limits_{r=0}^{\infty}a_rz^r$, which does not depend on $r$.

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