Discrete Mathematics for Computer Science

Exercises 465

(b) 12 +^22 +3^2 n

(^2) = (2n+l)n(n+l)
-+n 6
Proof

(a) Since C(k, 1) = k, the sum is found using the column sum formula.

n nn (n ± 1)

I: k= 3C(k, 1) = C(n + 1,2= 2

k=1 k=1

(b) The formula for the column sum is used twice to evaluate the sum of the first n squares.

First, write k^2 = k (k - 1) +- k. Since k (k - 1) can be written as 2 C(k, 2) and k as

C(k, 1), the sum now becomes

n n n

Ek 2= E-2C(k, 2) - E C(k, 1)

k=1 k=2 k=1

= 2C(n + 1, 3) + C(n + 1,2)

(2n + I)n (n + 1)

6

U Exercises

1. How many permutations are there for the letters of the name Bathsheba? Solomon?
   Ahab? your own name?


2. How many arrangements are possible for the letters of the following words:
   (a) Tennessee
   (b) Mississippi
   (c) Kansas
   (d) Oregon
   (e) Manitoba
   (f) Visiting


3. How many words or strings of 12 letters can be formed from the symbols

a, a, a, a, b, b, b, b, b, b, b, b

provided that no two a's can occur together?

4. Find the number of arrangements of the word engineering.
   (a) In how many of these are the three e's together?
   (b) In how many of these are exactly two e's together?


5. How many ways can five identical advertisements be placed in three mailboxes if each
   mailbox receives at least one advertisement? How many ways if a mailbox may receive
   none? (The order in which a messenger delivers a message is immaterial).


6. A word consisting of five letters is just a string of five letters with no meaning required.
   For example, xqzrp is a five-letter word. How many five-letter words or strings can be
   formed using an alphabet consisting of 35 letters if no repetition of letters is allowed?
   How many repetitions of a letter are allowed?