Discrete Mathematics for Computer Science

1. If \(S_n = 3^n\text{,}\)\(n \geq 0\text{,}\) then

   \begin{equation*} \begin{split} G(S;z) &= 1 + 3z + 9z^2 + 27z^3 +\cdots \\ & =\sum_{n=0}^{\infty} 3^n z^n\\ &=\sum_{n=0}^{\infty} (3 z)^n\\ \end{split} \end{equation*}

   We can get a closed form expression for \(G(S;z)\) by observing that \(G(S;z) - 3z G(S;z) = 1\text{.}\) Therefore, \(G(S;z) =\frac{1}{1-3 z}\text{.}\)

2. Finite sequences have generating functions. For example, the sequence of binomial coefficients \(\binom{n}{0} \text{,}\) \(\binom{n}{1} \text{,}\) \(\ldots\text{,}\)\(\binom{n}{n} \text{,}\) \(n \geq 1\) has generating function

   \begin{equation*} \begin{split} G(\binom{n}{\cdot}; z) & = \binom{n}{0} + \binom{n}{1} z +\cdots + \binom{n}{n} z^n\\ & = \sum_{k=0}^{\infty} \binom{n}{k} z^k\\ &=(1+z)^n\\ \end{split} \end{equation*}

   by application of the binomial formula.

3. If \(Q(n) = n^2\text{,}\) \(G(Q;z)=\sum_{n=0}^{\infty} n^2 z^n=\sum_{k=0}^{\infty} k^2 z^k\text{.}\) Note that the index that is used in the summation has no significance. Also, note that the lower limit of the summation could start at 1 since \(Q(0)=0\text{.}\)

If \(S(n) = n\text{,}\) \(T(n) = n^2\text{,}\) \(U(n) = 2^n\text{,}\) and \(R(n) =n 2^n\text{:}\)

1. \((S + T)(n) = n + n^2\)

2. \((U + R)(n) = 2^n+ n 2^n= (1+n)2^n\)

3. \((2 U)(n) = 2\cdot 2^n= 2^{n+1}\)

4. \(\left(\frac{1}{2}R\right)(n)= \frac{1}{2}n 2^n= n 2^{n-1}\)

5. \((S\cdot T)(n) = n n^2 = n^3\)

6. \((S*T)(n)= \sum_{j=0}^n S(j) T(n-j)= \sum_{j=0}^n j (n-j)^2\\ \\ \quad \quad =\sum_{j=0}^n \left( j n^2-2 n j^2 + j^3\right)\\ \\ \quad \quad = n^2\sum_{j=0}^n j-2n \sum_{j=0}^n j^2 + \sum_{j=0}^n j ^3\\ \\ \quad \quad =n^{2 }\left(\frac{n (n+1)}{2}\right)- 2n\left(\frac{(2n+1)(n+1)n}{6}\right)+\frac{1}{4} n^2 (n+1)^2\\ \\ \quad \quad = \frac{n^2(n+1)(n-1)}{12}\)

7. \((U*U)(n) =\sum_{j=0}^n U(j) U(n-j)\\ \\ \quad \quad =\sum_{j=0}^n 2^j 2^{n-j}\\ \\ \quad \quad = (n+1)2^n\)

8. \((S\uparrow )(n)=n+1\)

9. \((S\downarrow )(n)=\max (0,n-1)\)

10. \(((S\downarrow )\downarrow )(n)= \max (0, n - 2)\)

11. \((U\downarrow )(n)=\left\{ \begin{array}{cc} 2^{n-1} & \textrm{ if } n>0 \\ 0 & \textrm{ if } n=0 \\ \end{array} \right.\)

12. \(((U\downarrow )\uparrow )(n)=(U\downarrow )(n+1)= 2^n= U(n)\)

13. \(((U\uparrow )\downarrow ) (n)=\left\{ \begin{array}{cc} 0 & \textrm{ if } n = 0 \\ U(n) & \textrm{ if } n>0 \\ \end{array} \right.\)

If \(D(z) =\sum_{k=0}^{\infty} kz^k\) and \(H(z) =\sum_{k=0}^{\infty} 2^k z^k\) then

Note: \(D(z) = G(S;z)\text{,}\) and \(H(z) = G(U;z)\) from Example 5.

1. If \(S(n) = 9\cdot 5^n\text{,}\) \(n \geq 0\text{,}\) \(G(S;z)\) is an infinite geometric series with \(a = 9\) and \(r = 5z\text{.}\)Therefore, \(G(S;z) = \frac{9}{1 - 5z}\text{.}\)

2. If \(T(n) = 4\text{,}\) \(n \geq\)0, then \(G(T;z) = 4/(1 - z)\text{.}\)

3. If \(U(n) = 3(-1)^n\text{,}\) then \(G(U;z) = 3/(1 + z)\text{.}\)

4. Let \(C(n) = S(n) + T(n) + U(n) = 9 \cdot 5^n + 4 + 3(-1)^n\text{.}\) Then

   \begin{equation*} \begin{split} G(C;z) & = G(S;z) + G(T;z) + G(U;z)\\ & = \frac{9}{1-5z} + \frac{4}{1-z}+ \frac{3}{1+z}\\ & = -\frac{14 z^2+34z-16}{5 z^3-z^2-5 z+1} \end{split}\text{.} \end{equation*}

   Given a choice between the last form of \(G(C;z)\) and the previous sum of three fractions, we would prefer leaving it as a sum of three functions. As we saw in an earlier example, a partial fractions decomposition of a fraction such as the last expression requires some effort to produce.

5. If \(G(Q;z) = 34/(2 - 3z)\text{,}\) then \(Q\) can be determined by multiplying the numerator and denominator by 1/2 to obtain \(\frac{17}{1-\frac{3}{2}z}\text{.}\) We recognize this fraction as the sum of the infinite geometric series with \(a = 17\) and \(r = \frac{3}{2}z\text{.}\) Therefore \(Q(n) = 17(3/2)^n\text{.}\)

6. If \(G(A;z) = (1 + z)^3\) , then we expand \((1 + z)^3\) to \(1 + 3z + 3z^2 + z^{3}\) . Therefore \(A(0) = 1\text{,}\) \(A(1) = 3\) \(A(2)= 3\text{,}\) \(A(3) = 1\text{,}\) and, since there are no higher-powered terms, \(A(n) = 0\text{,}\) \(n \geq 4\text{.}\) A more concise way of describing \(A\) is \(A(k) = \binom{3}{k} \text{,}\) since \(\binom{n}{k} \) is interpreted as 0 of \(k > n\text{.}\)

Solve \(S(k) + 3S(k - 1) - 4S(k -2) = 0\text{,}\) \(k\geq 2\text{,}\) with \(S(0) = 3\) and \(S(1) = -2\text{.}\) The solution will be derived using the same steps that were used earlier in this section, with one variation.

1. Translate to an equation about generating functions. First, we change the index of the recurrence relation by substituting \(n + 2\) for \(k\text{.}\) The result is \(S(n + 2) + 3S(n + 1) - 4S(n) = 0\text{,}\) \(n \geq 0\text{.}\) Now, if \(V(n) = S(n + 2) + 3 S(n + 1) - 4S(n)\text{,}\) then \(V\) is the zero sequence, which has a zero generating function. Furthermore, \(V = S\uparrow 2+3(S\uparrow )-4 S\text{.}\) Therefore,

   \begin{equation*} \begin{split} 0 &= G(V;z) \\ & = G(S\uparrow 2; z) + 3 G(S\uparrow ;z) - 4G(S;z) \\ & = \frac{G(S;z) - S(0) - S(1)z }{z^2}+4 \frac{(G(S;z) - S(0))}{z} - 4G(S;z)\\ \end{split} \end{equation*}

2. We want to now solve the following equation for \(G(S;z)\text{:}\)

   \begin{equation*} \frac{G(S;z) - S(0) - S(1)z }{z^2}+4 \frac{(G(S;z) - S(0))}{z} - 4G(S;z) = 0 \end{equation*}

   Multiply by \(z^2\) :

   \begin{equation*} G(S;z) - 3 + 2z + 3z(G(S;z) - 3) - 4z^2 G(S;z) = 0 \end{equation*}

   Expand and collect all terms involving \(G(S;z)\) on one side of the equation:

   \begin{equation*} \begin{array}{c} G(S;z) + 3z G(S;z) - 4z^2 G(S;z) = 3 + 7z\\ \left(1 + 3z - 4z^2 \right)G(S;z)= 3 + 7z\\ \end{array} \end{equation*}

   Therefore,

   \begin{equation*} G(S;z)= \frac{3+7z}{1 + 3z - 4z^2} \end{equation*}

3. Determine S from its generating function. \(1 + 3z - 4z^2 = (1 + 4z) (1 - z)\) thus a partial fraction decomposition of \(G(S;z)\) would be:

   \begin{equation*} \frac{A}{1+4z}+ \frac{B}{1-z}=\frac{A z-A-4 B z-B}{(z-1) (4 z+1)} =\frac{(A+B)+(4B-A)z}{(z-1) (4 z+1)} \end{equation*}

   Therefore, \(A + B = 3\) and \(4B - A = 7\text{.}\) The solution of this set of equations is \(A = 1\) and \(B = 2\text{.}\) \(G(S;z)= \frac{1}{1+4z}+ \frac{2}{1-z}\text{.}\)

   \begin{equation*} \begin{array}{c} \frac{1}{1+4z} \textrm{ is the generating function of }S_1(n)=(-4)^n\textrm{, and}\\ \frac{2}{1-z} \textrm{ is the generating function of }S_2(n) = 2(1)^n = 2\\ \end{array} \end{equation*}

   In conclusion, since \(G(S;z) = G\left(S_1;z\right) + G\left(S _2;z\right)\text{,}\) \(S(n) = 2 + (-4)^n\text{.}\)

Let \(A = \{a, b, c, d, e\}\) and let \(A^*\) be the set of all strings of length zero or more that can be made using each of the elements of \(A\) zero or more times. By the generalized rule of products, there are \(5^n\) such strings that have length \(n\text{,}\) \(n\geq 0\text{,}\) Suppose that \(X_n\) is the set of strings of length \(n\) with the property that all of the \(a\)'s and \(b\)'s precede all of the \(c\)'s, \(d\)'s, and \(e\)'s. Thus \(aaabde \in X_6\text{,}\) but \(abcabc \notin X_6\text{.}\) Let \(R(n) =\lvert X_n \rvert\text{.}\) A closed form expression for \(R\) can be obtained by recognizing \(R\) as the convolution of two sequences. To illustrate our point, we will consider the calculation of \(R(6)\text{.}\)

Note that if a string belongs to \(X_6\text{,}\) it starts with \(k\) characters from \(\{a, b\}\) and is followed by \(6 - k\) characters from \(\{c, d, e\}\text{.}\) Let \(S(k)\) be the number of strings of \(a\)'s and \(b\)'s with length \(k\) and let \(T(k)\) be the number of strings of \(c\)'s, \(d\)'s, and \(e\)'s with length \(k\text{.}\) By the generalized rule of products, \(S(k) = 2^k\) and \(T(k) = 3^k\text{.}\) Among the strings in \(X_6\) are the ones that start with two \(a\)'s and \(b\)'s and end with \(c\)'s, \(d\)'s, and \(e\)'s. There are \(S(2)T(4)\) such strings. By the law of addition,

Note that the sixth term of R is the sixth term of the convolution of \(S\) with \(T\text{,}\) \(S*T\text{.}\) Think about the general situation for a while and it should be clear that \(R =S*T\text{.}\) Now, our course of action will be to:

1. Determine the generating functions of \(S\) and \(T\text{,}\)

2. Multiply \(G(S;z)\) and \(G(T;z)\) to obtain \(G(S*T;z) = G(R;z)\)\, and

3. Determine \(R\) on the basis of \(G(R;z)\text{.}\)

1. \(G(S;z) =\sum_{k=0}^{\infty} 2^k z^k=\frac{1}{1-2z}\) , and \(G(T;z) =\sum_{k=0}^{\infty} 3^k z^k=\frac{1}{1-3z}\)

2. \(G(R;z) = G(S;z)G(T;z) = \frac{1}{(1-2z)(1-3z)}\)

3. To recognize \(R\) from \(G(R;z)\text{,}\) we must do a partial fractions decomposition:

   \begin{equation*} \frac{1}{(1-2z)(1-3z)}=\frac{A}{1-2z}+\frac{B}{1-3z}=\frac{-3 A z+A-2 B z+B}{(2 z-1) (3 z-1)}=\frac{(A+B)+(-3 A -2 B )z}{(2 z-1) (3 z-1)} \end{equation*}

   Therefore, \(A + B = 1\) and \(-3A - 2B = 0\text{.}\) The solution of this pair of equations is \(A = - 2\) and \(B = 3\text{.}\) Since \(G(R;z) =\frac{-2}{1-2z}+\frac{3}{1-3z}\text{,}\) which is the sum of the generating functions of \(-2(2)^k\) and \(3 (3)^k\text{,}\) \(R(k) =-2(2)^k+3 (3)^k = 3^{k+1}-2^{k+1}\)

   For example, \(R(6) = 3^7 - 2^7= 2187 - 128 = 2059\text{.}\) Naturally, this equals the sum that we get from \((S*T)(6)\text{.}\) To put this number in perspective, the total number of strings of length 6 with no restrictions is \(5^6=15625\text{,}\) and \(\frac{2059}{15625}\approx 0.131776\text{.}\) Therefore approximately 13 percent of the strings of length 6 satisfy the conditions of the problem.

Suppose that you roll a die two times and add up the numbers on the top face for each roll. Since the faces on the die represent the integers 1 through 6, the sum must be between 2 and 12. How many ways can any one of these sums be obtained? Obviously, 2 can be obtained only one way, with two 1's. There are two sequences that yield a sum of 3: 1-2 and 2-1. To obtain all of the frequencies with which the numbers 2 through 12 can be obtained, we set up the situation as follows. For \(j = 1, 2\text{;}\) \(P_j\) is the rolling of the die for the \(j^{\text{th}}\) time. \(X_j = \{1, 2, . . . , 6\}\) and \(Q_j : X_j \rightarrow \{0, 1, 2, 3,\ldots \}\) is defined by \(Q_j(x) = x\text{.}\) Since each number appears on a die exactly once, the frequency function is \(F_j(k)=1\) if \(1 \leq k \leq 6\text{,}\) and \(F_j(k) = 0\) otherwise. The process of rolling the die two times is quantified by adding up the \({Q_j}'s\text{;}\) that is, \(Q\left(a_1, a_2\right) =Q_{1}\left(a_1\right)+Q_2\left(a_2\right)\) . The generating function for the frequency function of rolling the die two times is then

Now, to get \(F(k)\text{,}\) just read the coefficient of \(z^k\text{.}\) For example, the coefficient of \(z^5\) is 4, so there are four ways to roll a total of 5.

To apply this method, the crucial step is to decompose a large process in the proper way so that it fits into the general situation that we've described.

Suppose that an organization is divided into three geographic sections, A, B, and C. Suppose that an executive committee of 11 members must be selected so that no more than 5 members from any one section are on the committee and that Sections A, B, and C must have minimums of 3, 2, and 2 members, respectively, on the committee. Looking only at the number of members from each section on the committee, how many ways can the committee be made up? One example of a valid committee would be 4 A's, 4 B's, and 3 C's.

Let \(P_A\) be the action of deciding how many members (not who) from Section A will serve on the committee. \(X_A= \{3, 4, 5\}\) and \(Q_A(k)=k\text{.}\) The frequency function, \(F_A\) , is defined by \(F_A(k)=1\) if \(k\in X_k\) , with \(F_A(k)=0\) otherwise. \(G\left(F_A;z\right)\) is then \(z^3+ z^4+z^5\) . Similarly, \(G\left(F_B;z\right) =z^2+ z^3+ z ^4 + z^5= G\left(F_C ;z\right)\text{.}\) Since the committee must have 11 members, our answer will be the coefficient of \(z^{11}\) in \(G\left(F_A;z\right)G\left(F_B;z\right)G\left(F_C;z\right)\text{,}\) which is 10.