Processing math: 100%
본문 바로가기

Study/이산수학

Discrete Numeric Functions and Generating Functions

반응형

Discrete Numeric Functions and Generating Functions


function : binary relation that assigns to each element in domain a unique value which is element in range

discrete numeric function / numeric function

- functions whose domain is natural numbers and range is set of real numbers

- denote n.f.


Manipulation of numeric functions

sum of two n.f.'s : n.f. whose value at r is equal to sum of values of two n.f.'s at r

product of two n.f.'s : n.f. whose value at r is equal to product of values of two n.f.'s at r

 

a is an n.f.; α is real number > αa is an n.f.

a is an n.f. > |a| is an n.f.

a is an n.f.; i is a positive integer > Sia is an n.f.

a is an n.f.; i is a positive integer > Sia is an n.f.

a is an n.f. > accumulated sum of a is n.f.

a is an n.f. > forward difference of a(an+1an), Δa is n.f.

a is an n.f. > backward difference of a(anan1), Δa is n.f.

S1(a)=a

convolution : a and b are n.f.'s > convolution of a and b, c = a * b is n.f.


Asymptotic behavior of numeric functions

asymptotic behavior of n.f. : how the value of function varies for large r

asymptotic dominance : Let a and b n.f.'s. a asymptotically dominates b, or b is asymptotically dominated by a, if there exist positive constants k and m such that |br|mar for rk

- for given discrete n.f. a, let O(a) denote set of all n.f. that are asymptotically dominated by a

 - read "order a" or "big-oh of a". When bO(a), simply say b is O(a)

(a, b, c are n.f.'s; α, β are constants; i is positive integer)

1. a is O(a)

2. If b is O(a), αb is O(a)

3. If b is O(a), Sib is O(Sia)

4. If both b and c are O(a), then αb+βc is O(a)

5. If c is O(b) and b is O(a), c is O(a)

6. It is possible that a is O(b), and b is also O(a)

7. It is possible that a is not O(b), and b is not O(a)

8. It is possible that c is both O(a) and O(b), while a is not O(b) and b is not O(a)

 

O(r!)O(αr)O(ri)O(r)O(logr)O(1)

 

Let A and B be two sets of n.f.'s

- A+B={a+b|aA,bB}

- αA={αa|aA}

- AB={ab|aA,bB}

Let a and b be n.f.'s

- If b is O(a), O(a)O(b) 

- If b is O(a) and a is O(b), O(a) = O(b)

- O(a) + O(a) = O(a)

- If bO(a), O(a) + O(b) = O(a)

- αO(a) = O(αa) = O(a)

- O(a)O(b) = O(ab)

 

For given n.f. a, let bΩ(a) such taht ther exist positive constants k and m with |br|mar (rk)

For given n.f. a, let bΘ(a) such taht ther exist positive constants m, m', and k with mar|br|mar (rk)

- which means b is both O(a) and Ω(a) then b is Θ(a)


Generating functions

For given x and y, ther are alternative ways of calculating xy and x/y.

n.f. can be represented by an alternative way

 

For an n.f. (a0,a1,,ar,), define an infinite series

generating function g.f. : a0+a1z+a2z2++arzr+

 

g.f. of b=αa is B(z)=αA(z)

g.f. of c=a+b is C(z)=A(z)+B(z)

g.f. of br=αrar is B(z)=A(αz)

g.f. of Sia is ziA(z)

g.f. of Sia is zi[A(z)a0a1zai1zi1]

g.f. of b=a is B(z)=z1[A(z)a0]A(z) // b=(a1a0,a2a1,), B(z)=g.f.(a)g.f.(S1a))

g.f. of c=ab is C(z)=A(z)B(z)


Combinatorial problems

ar=C(n,r)=Σri=0C(k,i)C(nk,ri)

 

we can write a=de where

D(z)=C(k,0)+C(k,1)z++C(k,k)zk

E(z)=C(nk,0)+C(nk,1)z++C(nk,nk)zk

That is, A(z)=D(z)E(z)

Therefore, A(z)=[(C(1,0)+C(1,1)z]n=(1+z)n

 

prove C(n,r)=C(n1,r)+C(n1,r1)

method 1. algebraic manipulation

method 2. combinatiorial argument

method 3. generating function


학교 강의를 토대로 개인 공부 목적으로 작성되어 오타가 및 오류가 있을 수 있으며, 문제가 될 시 삭제될 수 있습니다.

반응형

'Study > 이산수학' 카테고리의 다른 글

Logic  (0) 2021.12.17
Recurrence Relations and Recursive Algorithms  (0) 2021.12.13
Analysis of Algorithms  (2) 2021.12.13
Graphs  (2) 2021.12.13
Relations and Functions  (0) 2021.12.12