---
title: 離散 part4
---
{%hackmd @NTNUCSIE112/DM_card %}

# Counting
Ch.8 Applications of Recurrence Relation
Reading assignment: 6.3, 6.4, 6.5, 6.6
Reading assignment: 8.1.1, 8.1.2, 8.2.1, 8.2.2, 8.4.1, 8.4.4, 8.4.5
Slide: Counting techniques, Counting

## 8.2 Solving Linear Recurrence Relations 解線性遞迴式

A linear recurrence of degree is of the form
### Characteristic equation Example

To solve $T(n) = T(n-1) + T(n-2)$, we adopt the following steps:

- Assume $T(n)=$
<!-- - 3/29 -->
- Then the recurrence can be written as ==$r^n = r^{n-1} + r^{n-2}$（特徵方程）==(i.e. $r^2 - r - 1 = 0$)
- Let the two roots of $P(r)=r^2-r-1$ be $r_1$ and $r_2$. Then $T_{n}=a_1{r_1}^n+a_2{r_2}^n$, where $a_1$ and $a_2$ are two constants, determined by the given initial condition.

e.g. $T(0)=0, T(1)=1$.
The two roots of $P(r)=r^2-r-1$ are $\frac{1+\sqrt5}{2}$, so the solution is
$$
T(n)=a_1(\frac{1+\sqrt5}{2})^n+a_2(\frac{1-\sqrt5}{2})^n
$$
The initial condition gives two equations:
用初始狀態給的東西解方程式

- $n = 0$ : $a_1+a_2=0$
- $a_1(\frac{1+\sqrt5}{2})^n+a_2(\frac{1-\sqrt5}{2})^n=1\to a_1=\frac{1}{\sqrt5},a_2=-\frac{1}{\sqrt5}$

重根有其他解法，詳情請見課本

<!-- 矩陣跟解線性方程在第二章有提到 挨跟啡魯 ㄤ -->
### Generating function example

## Counting 計數
e.g. In how many ways can a total number of 6 attendees of the meting be listed （from top to bottom）?

e.g. How many permutations(排列) of the letters A, B, C, D

### Generating all the $r$-combination of $\{ 1, 2, \cdots, n\}$
e.g. $n=4,r=2$
$2$-combination: $1, 2| 1, 3| 1, 4| 2, 3| 2, 4| 3, 4$

We can apply Pascal's identity to generate all r-combinations recursively
Recall [Pascal's identity](#642-Pascal’s-Identity-and-Triangle): ${n\choose r}={n-1\choose r-1}+{n-1\choose r}$

void gen_comb(pint n, int r, int a[], int s, int b[], int t)
{
    // terminal condition
    if(n - s == r || r == 0)
    {
        // print_sol
    }
    else
    {
        //recursive condition
        gen_comb(n, r, a, s + 1, b, 1);
        b[t] = a[s];
        gen_comb(n, r - 1, a, s + 1, b, t + 1);
    }
    return;
}

<!-- 上面是上課直接打的筆記（簡報） 下面是對應課本章節的 -->
## Ch.6 Counting
### 6.4 Binomial Coefficient and Identity
#### 6.4.2 Pascal's Identity and Triangle
${n\choose k}={n-1\choose k-1}+{n-1\choose k}$
#### 6.4.3 Other Identity Involving Binomial Coeffients
Vandermonde's identity: ${m+n\choose r}=\sum_{k=0}^r{m\choose r-k}{n\choose k}$

### 6.5 Generalized Permutations and Combinations
#### 6.5.5 Distributing Objects into Boxes
##### Distinguishable Objects and Distinguishable Boxes
##### Indistinguishable Objects and Distinguishable Boxes

- Placing $n$ **indistinguishable objects** into $r$ **distinguishable boxes**
how many nonnegative integral solutions of $x_1+x_2+\cdots+x_r=n$ are there?
$\to\frac{(n+r-1)!}{n!(r-1)!}={n+r-1\choose r-1}={n+r-1\choose n}$
##### Distinguishable Objects and Indistinguishable Boxes
##### Indistinguishable Objects and Indistinguishable Boxes
use enumeration

e.g. $4$ indistinguishable objects into $3$ indistinguishable boxes:

we enumerate all possibility by listing the numbers of objects in the boxes in increasing order:
$0\ 0\ 4|0\ 1\ 3|0\ 2\ 2|1\ 1\ 2\to 4$ different outcome
$\begin{aligned}
0\ 0\ 4\to1&={4\choose0}{4\choose0}{4\choose4}\\
0\ 1\ 3\to4&={4\choose0}{4\choose1}{3\choose3}\\
0\ 2\ 2\to3&=\frac{1}{2!}{4\choose0}{4\choose2}{4\choose2}\\
1\ 1\ 2\to6&=\frac{1}{2!}{4\choose1}{3\choose1}{2\choose2}
\end{aligned}$

<!-- Lis e's Li And -->