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 > S−ia 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+1−an), Δa is n.f.
a is an n.f. > backward difference of a(an−an−1), Δa is n.f.
S−1(▽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 r≥k
- 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 b∈O(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|a∈A,b∈B}
- αA={αa|a∈A}
- AB={ab|a∈A,b∈B}
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 b∈O(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 (r≥k)
For given n.f. a, let b∈Θ(a) such taht ther exist positive constants m, m', and k with mar≤|br|≤m′ar (r≥k)
- 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 S−ia is z−i[A(z)−a0−a1z−⋯−ai−1zi−1]
g.f. of b=△a is B(z)=z−1[A(z)−a0]−A(z) // b=(a1−a0,a2−a1,⋯), B(z)=g.f.(a)−g.f.(S1a))
g.f. of c=a∗b is C(z)=A(z)B(z)
Combinatorial problems
ar=C(n,r)=Σri=0C(k,i)C(n−k,r−i)
we can write a=d∗e where
D(z)=C(k,0)+C(k,1)z+⋯+C(k,k)zk
E(z)=C(n−k,0)+C(n−k,1)z+⋯+C(n−k,n−k)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(n−1,r)+C(n−1,r−1)
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 |