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.; $\alpha$ is real number > $\alpha 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 > $S^ia$ is an n.f.

$a$ is an n.f.; i is a positive integer > $S^{-i}a$ 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$($a_{n+1} - a_n$), $\Delta a$ is n.f.

$a$ is an n.f. > backward difference of $a$($a_n - a_{n-1}$), $\Delta a$ is n.f.

$S^{-1}(\triangledown a) = \triangle 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 $|b_r|\leq ma_r$ for $r\geq 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\in O(a)$, simply say $b$ is $O(a)$

(a, b, c are n.f.'s; $\alpha$, $\beta$ are constants; i is positive integer)

1. $a$ is $O(a)$

2. If $b$ is $O(a)$, $\alpha b$ is $O(a)$

3. If $b$ is $O(a)$, $S^i b$ is $O(S^ia)$

4. If both $b$ and $c$ are $O(a)$, then $\alpha b +\beta 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!)\supset O(\alpha^r)\supset O(r^i)\supset O(r)\supset O(log r)\supset O(1)$

 

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

- $A+B = \{a+b|a\in A, b\in B\}$

- $\alpha A = \{\alpha a | a\in A\}$

- $AB = \{ab|a\in A, b\in B\}$

Let $a$ and $b$ be n.f.'s

- If $b$ is $O(a)$, $O(a)\supseteq O(b)$ 

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

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

- If $b\in O(a)$, $O(a)$ + $O(b)$ = $O(a)$

- $\alpha O(a)$ = $O(\alpha a)$ = $O(a)$

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

 

For given n.f. $a$, let $b\in \Omega (a)$ such taht ther exist positive constants k and m with $|b_r|\geq ma_r$ $(r\geq k)$

For given n.f. $a$, let $b\in \Theta (a)$ such taht ther exist positive constants m, m', and k with $ma_r\leq |b_r| \leq m'a_r$ $(r\geq k)$

- which means b is both $O(a)$ and $\Omega (a)$ then b is $\Theta (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. $(a_0,a_1,\cdots ,a_r,\cdots )$, define an infinite series

generating function g.f. : $a_0 + a_1z+a_2z^2+\cdots +a_rz^r+\cdots$

 

g.f. of $b=\alpha a$ is $B(z)=\alpha A(z)$

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

g.f. of $b_r=\alpha^ra_r$ is $B(z)=A(\alpha z)$

g.f. of $S^ia$ is $z^iA(z)$

g.f. of $S^{-i}a$ is $z^{-i}[A(z)-a_0-a_1z-\cdots - a_{i-1}z^{i-1}]$

g.f. of $b=\triangle a$ is $B(z) = z^{-1}[A(z)-a_0]-A(z)$ // $b=(a_1-a_0,a_2-a_1,\cdots )$, $B(z)=g.f.(a)-g.f.(S^1a))$

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

---

Combinatorial problems

$a_r=C(n,r)=\Sigma_{i=0}^r C(k,i)C(n-k,r-i)$

 

we can write $a=d*e$ where

$D(z) = C(k,0)+C(k,1)z+\cdots + C(k,k)z^k$

$E(z) = C(n-k,0)+C(n-k,1)z+\cdots + C(n-k,n-k)z^k$

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

---

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