compare iterative and recursive programs

which is faster ?

iterative version: about 2n arithmetic operations

recursive version ?

total number of function calls: r(n) = 1 + r(n-1) + r(n-2)

r(0) = 1 r(1) = 1

notice: for n ≥ 0, r(n) = 2f(n+1) - 1

exercise: prove by induction

f(100) = 354224848179261915075

r(100) = 1146295688027634168201

section 1: see text

set notation

set properties and proofs

algebraic rules for sets

Venn diagrams and proofs of set equations

element method for proofs of set equations

tabular method for proofs of set equations

an algebraic proof

ordering sets

lex order

really, defined only for sequences

for (multi-)sets, first order elements in (multi-)set

theorem

defn: for integers n,k, C(n,k) = number of k-element subsets of n-set

defn: for non-negative integer n, n!

defn: for non-negative integers n,k,

theorem: C(n,k) =

proof: in text

why values C(n,k) called binomial coefficients ?

because of this identity:

combinatorial identity

for integers 0 ≤ k ≤ n,

proof: consider n-set with 1 element marked

k-subsets ?

k-subsets with marked element?

k-subsets without marked element?

QED

pascal(11)

[1] [1, 1] [1, 2, 1] [1, 3, 3, 1] [1, 4, 6, 4, 1] [1, 5, 10, 10, 5, 1] [1, 6, 15, 20, 15, 6, 1] [1, 7, 21, 35, 35, 21, 7, 1] [1, 8, 28, 56, 70, 56, 28, 8, 1] [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1]

computing Pascal's triangle

# assume n at least 1 # print rows 0..n of Pascal's triangle def pascal(n): print [1] # row 0 a = [1,1] print a # row 1 for j in range(n-1): # j = 0..n-2 a.append(1) a.reverse() for k in range(j+1): a[k+1] += a[k+2] print a #row j+2

representing subsets

consider set U = { a, b, …, k }

to describe subset S of U:

can list elements, eg. S = { c, f, g, k }

can give

*characteristic vector*, eg. S = (0 0 1 0 0 1 1 0 0 0 1)(0 0 0 0 0 0 0 0 0 0 0) represents what subset ?

(1 1 1 0 0 0 0 0 0 0 0) represents what subset ?

another combinatorial identity

for non-negative integers n,

proof

sum is total number of subsets of n-set

1-1 correspondence between subsets of n-set and 0/1-n-vector

number 01-n-vectors = number n-sequences of 2-set = 2

^{n}

another proof

binomial coefficients identity, with x=y=1

power set

set of all subsets of set S is

*power set*by preceding identity,