Permutations

The set {a,b,c} has the following 6 permutations: abc, acb, bac, bca, cab, cba.

Theorem 2.4 The number of permutations of n objects in n!.

2^n <n!<n^n.

_{Theorem 2.5 [Stirling’s Formula] 
n! ∼ (n/e)^n * sqr (2Pin)}

2.32 n boys and n girls go out to dance. In how many ways can they all dance simultaneously? (We assume that only couples of different sex dance with each other.)

n!

2.34 (a) Which is larger, n or n(n − 1)/2?

(b) Which is larger, n^2 or 2^n?
2.35 (a) Prove that 2^n > n^3 if n is large enough.

(b) Use (a) to prove that 2^n/n^2 becomes arbitrarily large if n is large enough.

(a) n(n−1)/2 is larger for n ≥ 4. (b) 2^n is larger for n ≥ 5.

2.35 (a) Prove that 2^n > n^3 if n is large enough.

(b) Use (a) to prove that 2^n/n^2 becomes arbitrarily large if n is large enough.

(a)This is true for n≥10. (b)2^n/n^2 >n for n≥10.

Induction

the sum of the first n odd numbers is n^2

The principle of induction says that if (a) and (b) are true, then every natural number has the property.

3.1 Prove, using induction but also without it, that n(n + 1) is an even number for every non-negative integer n.

One of n and n+1 is even, so the product n(n+1) is even. By induction: true for n = 1; if n > 1 then n(n+1) = (n−1)n+2n, and n(n−1) is even by the induction hypothesis, 2n is even, and the sum of two even numbers is even.

3.2 Prove by induction that the sum of the first n positive integers is n(n + 1)/2.

True for n=1. Ifn>1 then
 1+2+...+n = (1+2+...+(n−1))+n = ^{(n−1)n /2}+n = ^{n(n+1) /2}

3.3 Observe that the number n(n + 1)/2 is the number of handshakes among n + 1 people. Suppose that everyone counts only handshakes with people older than him/her (pretty snobbish, isn’t it?). Who will count the largest number of handshakes? How many people count 6 handshakes?

The youngest person will count n − 1 handshakes. The 7-th oldest will count 6 hand- shakes. So they count 1+2+...+(n−1) handshakes. We also know that there are n(n−1)/2 handshakes.


3.5 Prove the following identity:

1·2+2·3+3·4+...+(n−1)·n = ^{(n−1)·n·(n+1).} /3

By induction on n true for n=1. For n>1,we have

1·2+2·3+3·4+...+(n−1)·n = ^{(n−2)·(n−1)·n /3}+(n−1)·n = ^{(n−1)·n·(n+1).} /3

Counting subsets

Theorem 4.1 The number of ordered k-subsets of an n-set is n(n−1)...(n−k+1).

Theorem 4.2 The number of k-subsets of an n-set is n(n−1)...(n−k+1) /k!₌ n!/ k!(n − k)!

^{Theorem 4.3 (The Binomial Theorem) The coefficient of x^k*y^(n−k) in the expansion of (x + y)^n is (n k).} In other words, we have the identity:

(x+y)^n=y^n+(n 1)*x^(n-1)*y+…+(n n-1)*x^(n-1)*y+(n n)*x^n

Thus the number of ways of distributing the presents is

n!/ n1!n2!...nk! + for anagrams

Theorem 4.4 The number of ways to distribute n identical pennies to k children, so that each child gets at least one, is (n-1 k-1)

Theorem 4.5 The number of ways to distribute n identical pennies to k children is ^{(n+k-1 k-1)}

4.2 Suppose that we record the order of all 100 athletes.

(a) How many different outcomes can we have then?

(b) How many of these give the same for the first 10 places?

(c) Show that the result above for the number of possible outcomes for the first 10 places can be also obtained using (a) and (b).

(a) 100!. (b) 90!. (c) 100!/90! = 100 · 99 · ... · 91.

4.18 How many anagrams can you make from the word COMBINATORICS?

13!/23.

Pascal’s triangle

^{Theorem 5.1 For all integers 0 ≤ t ≤ m,
 (2m m)/ (2m m-t)>1+t^2/m}

5.2 Prove that each row in the Pascal Triangle starts and ends with 1.

^{(n 0)= (n n)} = 1 (e.g. by the general formula for the binomial coefficients).

Fibonacci

In other words, if we denote by Fn the number of rabbits during the n-th month, then we have, for n = 2,3,4,...,

F(n+1) = Fn + F(n−1).

We also know that F1 =1,F2 =1,F3 =2,F4 =3,F5 =5. It is convenient to define F0 = 0; then equation (14) will remain valid for n = 1 as well. Using the equation (14), we can easily determine any number of terms in this sequence of numbers:

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597...

We just give a rule that computes each Fibonacci number from the two previous numbers, and specify the first two values. Such a definition is called a recurrence. It is quite similar in spirit to induction (except that it not a proof technique, but a definition method), and is sometimes also called definition by induction.

6.1 Why do we have to specify exactly two of the elements to begin with? Why not one or three?

Because we use the two previous elements to compute the next.