04 Numeric Generating Supp u3l1y

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

Chapter 9 Discrete Numeric Functions and Generating Functions 9.1 Introduction » Discrete numeric functions (numeric functions) „ The class of functions - whose domain is the set of natural numbers - whose range is the set of real numbers „ Exhaustively listing: (a0, a1, a2, …, ar, …), values of the function a at 0, 1, 2, …, r, … - Or a(0), a(1), … „ Concise specification: - ar = 7r 3 + 1

⎧ 2r b = - r ⎨3 r − 1 ⎩

⎧ −4

r≥0 0 ≤ r ≤ 11 r ≥ 12

- cr = ⎨ ⎩0

r = 3, 5, 7 otherwise

⎧2 + r ⎪ - d r = ⎨2 − r ⎪⎩2 / r

0≤r≤5 r > 5 r is odd r > 5 r is even

» Ex 9.1: Deposit $100 at an interest rate of 7% per year, compounded annually „ total amount at the end of each year is a numeric function a - a = (100, 107, 114.49, 122.50, …), or - ar = 100(1.07)r r≥0 » Ex 9.2: an aircraft - spends 10 minutes on the ground before takes off - climbs up at a uniform speed to 30000 feet in 10 minutes - flies at the same altitude for 110 minutes - lands down at a uniform speed in 10 minutes - altitude of the aircraft, in thousands of feet is a function cthuang, 2008

1

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

-

⎧0 ⎪3(r − 10) ⎪⎪ a r = ⎨30 ⎪3(130 − r ) ⎪ ⎪⎩0

0 ≤ r ≤ 10 11 ≤ r ≤ 20 21 ≤ r ≤ 130 131 ≤ r ≤ 140 r ≥ 141

- Graph: altitude vs time 9.2 Manipulation of Numeric Functions » Sum of two numeric functions: c = a + b, i.e., cr = ar + br „ A numeric function whose value at r is equal to the sum of the two functions at r » Product of two numeric functions: c = a b, i.e., cr = ar br „ A numeric function whose value at r is equal to the product of the two functions at r » Ex: Consider the two function a and b where 0≤r≤2 ⎧3 - 2r 0 ≤ r ≤1 ⎧0 b = a = ⎨ r „ r ⎨2 − r + 5 r ≥ 3 r≥2 ⎩ ⎩r + 2 „ Sum of the two functions a and b

⎧3 − 2 r 0 ≤ r ≤1 ⎪ r=2 - cr = a r + br = ⎨4 ⎪2 − r + r + 7 r ≥ 3 ⎩ „ Product of the two functions a and b

0≤r≤2 ⎧0 −r − r +1 + 5r + 10 r≥3 ⎩r ⋅ 2 + 2

- d r = a r br = ⎨

» *Ex: a: monthly income of a husband b: monthly income of his wife - a + b: t monthly income » *Ex: a: balance in a saving in each month b: monthly interest rate which fluctuates from month to month - ab: interest earned in each month cthuang, 2008

2

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

» Scaled: Let a be a numeric function; α be a real number „ αa: a scaled version of a with scaling factor α - a numeric function whose value at r is equal to α times ar » *Ex: Let a be a numeric function whose value at r is (1.07)r total amount in an for an initial deposit of $1 - 100a: a numeric function whose value at r is 100(1.07)r total amount in the for an initial deposit of $100 » |a|: a numeric function whose value at r is equal to - ar if ar is nonnegative - −ar if ar is negative

⎛ 2 ⎞

⎟⎟ » Ex: a r = ( −1) r ⎜⎜ 2 ⎝r ⎠

2 r ≥ 0 => br = ar = r2

r≥0

» *Ex: a: different between the output voltage of an electrical power supply after r hours of operation and a normal reference voltage „ |a|: derivation of the output voltage from the reference voltage » Shifting: let a be a numeric function and i a positive integer

⎧0 ⎩ar-i

„ b = Sia: br = ⎨

0 ≤ r ≤ i −1 r ≥i

- function a is shifted i positions to the right

⎧1

- Ex: a: a r = ⎨ ⎩2

⎧0 ⎪ b = S5a: br = ⎨1 ⎪⎩2

0 ≤ r ≤ 10 r ≥ 11 0≤r≤4 5 ≤ r ≤ 15 r ≥ 16

- Ex: a: the altitude of an aircraft (e.g. 9.2)

⎧0 ⎪3( r − 10) ⎪ a r = ⎨30 ⎪3(130 − r ) ⎪0 ⎩ cthuang, 2008

0 ≤ r ≤ 10 11 ≤ r ≤ 20 21 ≤ r ≤ 120 121 ≤ r ≤ 130 r ≥ 131 3

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

b = S17a: takes off is delayed by 17 minutes

⎧0 ⎪3( r − 27) ⎪ br = ⎨30 ⎪3(147 − r ) ⎪0 ⎩

0 ≤ r ≤ 16, 17 ≤ r ≤ 27 28 ≤ r ≤ 37 37 ≤ r ≤ 137 138 ≤ r ≤ 147 r ≥ 148

„ b = S-ia: br = ar +i - function a is shifted i positions to the left

⎧1

- Ex: a: a r = ⎨ ⎩2

⎧1 ⎩2

- b = S-7a: br = ⎨

0 ≤ r ≤ 10 r ≥ 11 0≤r≤3 r≥4

- *Ex: Let a be a numeric function where ar: number of applicants whose height is r inches above the minimum requirement Ö S-2a: numbers of applicants in the height groups if two inches have been added to the minimum requirement » Def: Accumulated sum of a numeric function a: „ a numeric function whose value at r is equal to ∑ r ai i =0 r - Ex: Let ar = 100(1.07) r≥0 z b be the accumulated sum of a

r r i 10,000 ⎡(1.07) r +1 − 1⎤ z br = ∑ ai = ∑100(1.07) = ⎥⎦ 7 ⎢⎣ i =0 i =0 *deposit $100 each year at an annual compounded interest rate of 7% Ö br: total amount we have after r year

cthuang, 2008

4

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

» Def: Forward difference of a numeric function a: Δa „ a numeric function whose value at r is equal to ar+1 − ar » Def: Backward difference of a numeric function a: ∇a

⎧a „ a numeric function whose value is equal to ⎨ 0

at 0 ⎩a r − a r −1 at r ≥ 1

» Ex: a: total income of a company in each month „ Δa: increase of income from the rth month to the (r+1)st month „ ∇a: increase of income for the rth month over the (r−1)st month » Ex: Let a be a numeric function

⎧0 ar = ⎨ − r ⎩2 + 5

0≤r ≤2 r≥3

» b = Δa:

⎧0 0 ≤ r ≤1 ⎪⎪ 41 r=2 ⇐ (2-3 + 5) − 0 br = ⎨ ⎪8 ⎪⎩− 2−(r +1) r ≥ 3 ⇐ (2-(r +1) + 5) − (2-r + 5) » c = ∇a:

⎧0 ⎪⎪ 41 cr = ⎨ ⎪8 ⎪⎩− 2− r

cthuang, 2008

0≤r≤2 r =3 r≥4

⇐ (2-3 + 5) − 0 ⇐ (2-r + 5) − (2-(r -1) + 5)

5

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

» Def: Convolution of two functions a and b: a∗b „ a function c such that

cr = a0 br + a1br −1 + a 2 br − 2 + L + ai br −i + L + a r −1b1 + a r b0

» Ex 9.3: Let ar = 3r r ≥ 0 , br = 2r „ Convolution c = a∗b r

cr = ∑ 3i 2r-i

r≥0

r≥0

i =0

- ar: # sequences of length r made up of the letters {x, y, z} - br: # sequences of length r made up of the letters {α, β} For sequences made up of the letters {x, y, z, α, β} - cr: # sequences of length r such that the first portion made up of the letters {x, y, z} the second portion made up of the letters {α, β} » Ex 9.4: a savings with an annually compounded interest rate of 7% per year. „ Suppose we deposit - $100 at the beginning - $110 at the end of the first year - $120 at the end of the second year - $100(1+0.1r) at the end of the rth year - total amount in the at the end of the rth year? a: yearly deposit ar = 100(1+0.1r) r≥0 r r≥0 b: compounded interest br = (1.07) if ai was deposited at the end of the ith year Ö aibr-i dollars r − i years later (or at the end of rth year) Ö total amount at the end of the rth year

r cr = ∑ aibr −i i =0

cthuang, 2008

6

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

9.3 Asymptotic Behavior of Numeric Functions » Asymptotic Behavior of a Numeric Function - how the value of the function varies for large r - Ex: ar = 5, r≥ 0 => constant with increasing r - Ex: br = 5r2, r≥ 0 => increases w/ r and is proportional to r2 - Ex: cr = 5 log r, r≥ 0 => increases w/ r and is proportional to log r - Ex: dr = 5/r, r≥ 0 => decreases w/ r and is proportional to 1/r and is approaches 0 as a limit » Asymptotic dominance (asymptotic bound) „ Let a and b are two numeric functions. If there exist positive constants k and m such that |br| ≤ m ar for r ≥ k - a asymptotically dominates b, or - b is asymptotically dominated by a Ö a grows faster than b Ö For sufficiently large r, the absolute value of br does not exceed a fixed proportion of ar „ Ex: ar = r + 1

r ≥ 0, br =

1 +7 r

r≥0

for r ≥ 7 - for k = 7 and m = 1, |br| ≤ ar Ö a asymptotically dominates b „ Ex: ar =

1 2 r − 1000 100

⎧− 1,000,000 br = ⎨ ⎩− 100,000r

0 ≤ r ≤ 10 r > 10

- for k = 106 + 1 and m = 10, |br| ≤ 10ar for r ≥ 106 + 1 Ö a asymptotically dominates b » b does not dominate a asymptotically „ for any choice of k and m, there exists r0 such that | ar | > m br 0

cthuang, 2008

for r0 ≥ k

7

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

» Ex: deposit $1 in two s „ A: total deposit become 1 + 0.2r after r years „ B: total deposit become (1 + 0.03)4r after r years Let ar = 1 + 0.2r, r ≥ 0; br = (1 + 0.03)4r , r ≥ 0 - b asymptotically dominates a for k = 9 and m = 1, |1 + 0.2r| ≤ (1 + 0.03)4r for r ≥ 9 - B: growth rate is higher - the total in B exceeds that in A in the long run » O(a): the set of all numeric functions that are asymptotically dominated by a „ b is asymptotically dominated by a „ b ∈ O(a) or b is O(a) „ Ex: function b is O(r2) - b is asymptotically dominated by a function a = r2. „ Ex: function b is O( r log r ) - b is asymptotically dominated by a function a = r log r . „ Ex: function b is O(a) - b does not grow faster than a r „ “b grows too faster because b is O( 2 )” is not meaningful r - b could grow much slower than 2 - asymptotical upper bound could be meaningless „ Ex: - a = r2 - b = 10r2 + 25 - c=5−r - d=

1 2 r log r − r 2 2 Ö b is O(a), c is O(a), but d is not O(a) Ö a is O(d), b is O(d), c is O(d)

cthuang, 2008

8

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

Truth in asymptotic dominance » 1. |a| asymptotically dominates a - a is O(|a|) » 2. If b is asymptotically dominated by a - for any constant α, αb is also asymptotically dominated by a - If b is O(a), for any constant α, αb is also O(a) » 3. If b is asymptotically dominated by a - for any integer i, Sib is asymptotically dominated by Sia - If b is O(a), for any integer i, Sib is O(Sia) » 4. If both b and c are asymptotically dominated by a - for any constant α and β, αb + βc is also asymptotically dominated by a - If both b and c are O(a), for any constant α and β, αb + βc is also O(a) » 5. If c is asymptotically dominated by b and b is asymptotically dominated by a - c is asymptotically dominated by a - If c is O(b) and b is O(a), c is O(a) » 6. It is possible that a asymptotically dominates b and b also asymptotically dominates a - It is possible that a is O(b) and b is O(a). - Ex: ar = r 2 + r + 1

br = 0.05r 2 − r1 / 3 − 9

r≥0 r≥0

» 7. It is possible that a does not asymptotically dominate b nor does b asymptotically dominate a - It is possible that a is not O(b) and b is not O(a).

⎧1 ⎩0

- Ex: ar = ⎨

cthuang, 2008

r is even r is odd

9

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

⎧0 br = ⎨ ⎩1

r is even r is odd

» 8. It is possible that both a and b asymptotically dominate c, - while a does not asymptotically dominate b, nor does b asymptotically dominate a - It is possible that c is both O(a) and O(b), while a is not O(b) and b is not O(a)

⎧1 ⎩0

- Ex: ar = ⎨

r = 3i or 3i + 1 r = 3i + 2

⎧1 br = ⎨ ⎩0

r = 3i or 3i + 2 r = 3i + 1

⎧1 cr = ⎨ ⎩0

r = 3i otherwise

» Ex 9.6: Show that for i ≤ j, αri is O(rj) „ for k = 1 and m = 1 |ri| ≤ rj for r ≥1 Ö ri is O(rj) Ö from truth 2, αri is O(rj) » Ex 9.7: a = α0 + α1r + α2r2 +L+ αnrn, show that a is O(rn) „ for i ≤ n, αιri is O(rn) Ö from truth 4, a is O(rn)

cthuang, 2008

10

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

» » » » » » »

O(1) O(log n) O(n) O(n log n) O(ni) O(αn) O(n!)

cthuang, 2008

11

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

9.4 Generating Function » Generating function of the numeric function , , ,…, ,… „ An alternative way to represent numeric functions „ : indicator of » Ex: 1,1,1,1,1,1,1, …

» Ex:

1,1,1,1,1,1,0,0,0,0,0, …

» Ex:

3 ,3 ,3 ,, 3 3

-

,…, 3

Ö

,… 3 (a close form)

» Generating function representation: possibility of expressing infinite series in closed forms so that they can be manipulated conveniently „ Let , then - Ex: 7·3 , 0

Ö 3

- Ex:

,

0

Ö „ Let - Ex:

, then 2 3 ,

0

Ö „ Ex: cthuang, 2008

12

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

2, 0 __________, 1 __________, 2 for some constant

Ö „ Let -

Ö 1,

- Ex:

0

Ö 0

,

- Ex:

Ö - Ex: 2

Ö

2 , 0,

Ö Or „ For „ Let

,

2

0 odd even

, no simple form to express , , then

- Ex:

Ö ,

„ Let

3

- Ex:

Ö

cthuang, 2008

0, 0 2 , , then ,

3 4

0 1

3

13

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

- Ex: Hourly productivity of a machinist

- Ex: 3 machinists: one comes to work at 6am, another at 8am, the last one at 9am

Ö Total hourly productivity

„ For

∆ , then

„ For

, then

1

„ Convolution function - Namely, the coefficient of - i.e., - Ex:

3 ,

Ö

2 ,

of

0. Let

,

Ö Ö

cthuang, 2008

14

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

- Ex: Let and

be an arbitrary numeric function,

1,1,1, … ,

∑ ∑ Ö Ö c is the accumulated sum of a

Ö

cthuang, 2008

15

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

Binomial Coefficients » Binomial Theorem: „ Let x, y be variables, and let n be a nonnegative integer. Then ∑

-

,

,0 ,

,1

,2

1

,

„ Ex: -

in the expansion of 2

„ Ex: coefficient of

» Some useful identities „ Corollary 1: - Let n be nonnegative integer. Then

Ö ∑

,

2

„ Corollary 2: - Let n be a positive integer. Then

Ö∑

1

,

0

» Pascal’s identity (Ex 9.15, p297) „ Let n and k be positive integers with

Ö

cthuang, 2008

,

1,

. Then 1,

1

16

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

„ Combinatorial argument - Select r objects from n objects: C(n, r) z C(n-1, r) ways to select r objects excluding a particular one z C(n-1, r-1) ways when this particular objects is always included „ Corollary 3: - Let n and k be positive integers with . Then

Ö∑

,

2

3

Extended Binomial Coefficient » Def:

!

∑

» Def: 1

…

…

,

!

!

,

,0

,

Ö 1 More on Generating Function » Ex: Let m, k be a positive integer. Let „ ,0 ,1 ,2 1 7 15 » Ex: 0 1 3 „ 1 8 16 „ 1 2 4

cthuang, 2008

,

17

Discrete Mathematics: Discrete Numeric Functions and Generating Functions

» Ex: Find the solutions of 17, where , , are nonnegative integers with 2 5, 3 6, 4 7. in the following product „ Equivalent to the coefficient of

» Ex: # ways to distribute 8 identical cookies among 3 distinct children „ Each child receives at least two cookies and no more than 4 cookies

To find the coefficient of » Ex (9.17): # r-combinations from a set with n objects when repetition allowed „ The selection of one specific object with repetition „ n objects:

» Ex (9.18): # ways in which 2t+1 marbles can be distributed among 3 distinct boxes „ No box will contain more than t marbles

cthuang, 2008

18