Hehy's Blog

—— learning processing

0%

Discrete Mathematics_part1

Posted on Edited on In
Symbols count in article: 11k Reading time ≈ 10 mins.

离散数学 Discrete Mathematics

part 1 proposition and logic

命题 proposition

A proposition is a declarative sentence that is either true or false.

  • 真值 truth value

  • Simple Proposition:

​ cannot be broken into 2 or more propositions

  • Compound Proposition:

    not simple

logic operation

  • Negation (否定) $\neg$

  • conjunction (合取) and $\wedge $

  • Disjunction (析取) or $\vee$

  • Implication (→)

  • Bi-Implication (↔)：

​ A$\leftrightarrow$B $\Leftrightarrow$(A$\rightarrow$B)$\wedge $(B$\rightarrow$A)

  • Precedence（优先级）：

​ $\neg$， $\wedge$ ，$\vee$，$\rightarrow$，$\leftrightarrow$

Well-Formed Formulas :

​ =propositional formulas=formulas

** Translation**:

  • if A then B $\Leftrightarrow$ A$\rightarrow$B
  • A only if B $\Leftrightarrow$ A$\rightarrow$B
  • A is a sufficient condition for B $\Leftrightarrow$ A$\rightarrow$B
  • A is a necessary condition for B $\Leftrightarrow$ B$\rightarrow$A
  • A necessary condition for A is B$\Leftrightarrow$A$\rightarrow$B
  • but $\wedge $
  • A if B $\Leftrightarrow$ B$\rightarrow$A
  • A provided that B $\Leftrightarrow$ B$\rightarrow$A
  • A only if B $\Leftrightarrow$ A$\rightarrow$B

Types of WFFs:

  • tautology always true
  • contradition always false
  • contingency neither tautology nor contradiction
  • satisfiable:it is true for at least one truth assignment

Logically equivalent:

​ A and B always has the same truth table for every truth assignment(of p1,p2,…,p$_n$)

image-20210418022500577

image-20210418022528955

Tautological Implications $\Rightarrow$ :

​ How to prove A $\Rightarrow$B:

  • A$^{-1}$(T)$\subseteq$B$^{-1}$(T);
  • A$\rightarrow$B is a tautology;
  • A$\land$$\neg$B is a contradiction

image-20210418143455223

个体和谓词 Individual and Predicate

  • universal quantifier $\forall$ and existential quantifier$\exists$

  • Types of WFFs:

  • logically valid : always true

  • unsatisfiable : always false

  • satisfiable : it is true for at least one truth assignment

  • important:image-20210420213108749

    Prop:

  • $$\forall x(A(x) \land B(x)) \equiv \forall xA(x) \land \forall xB(x)$$

  • $$\exists x(A(x) \lor B(x)) \equiv \exists xA(x) \lor \exists xB(x)$$

image-20210418145546880

image-20210418145604913

image-20210418145618260

(mid,2019)$\forall x(\forall y(N(x,y) \to \forall z(G(z,x) \land G(z, y) \lor D(z, x) \lor D(z,y))))$

Logic translation：mid

part 2 set theory

Principle of Inclusion-Exclusion

cover

partition is disjoint cover

proper:真子集

complement:补集

$p(A)={x|x\subseteq A}$:the power set of A

disjoint:$A\cap B\neq \emptyset$

XOR$\oplus$: $A\oplus B =(A-B)\cup(B-A)$: the symmetric difference of A and B.

时间原因，写的仓促，详见vixbob’s set theory

part 3 combinatorial mathematics

Combinations of set:

  • Let $𝐴$ = {$a_1$, … , $a_𝑛$} be a finite set. Let $k$ $\in$ {0,1, … , 𝑛}. k-combination of $𝐴$ without repetition: an $k$-subset of $𝐴$.
  • $$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$

Permutations of set:

  • Let $𝐴$ be a finite set of 𝑛 elements. Let $k$ $\in$ [n].$k$-permutation of $𝐴$: a sequence $a_1$, $a_2$, ⋯ , $a_k$ of $k$ distinct elements of $𝐴$.
  • $$A_{n}^{k} = \frac{n!}{(n-k)!}$$

Multiset:

​ A multiset is collection of elements which are not necessarily different from each other.

  • An element 𝑥 $\in$ 𝐴 has multiplicity 𝑚 if it appears 𝑚 times in the multiset 𝐴.
  • A multiset 𝐴 is called an 𝒏-multiset if it has 𝑛 elements.
  • $A = {n_{1}\cdot a_{1},n_{2}\cdot a_{2},\ldots,n_{k}\cdot a_{k}}$ : an $(n_1 + n_2 +\cdots +n_k)$-multiset where the elements $a_1 , a_2 ,\dots ,a_k$ has multiplicities $n_1 , n_2 ,\dots ,n_k$, respectively.
    • $T = {t_1 \cdot a_1,t_2 \cdot a_2,\ldots,t_k \cdot a_k}$ is called an $r$-subset of $A$ if $0\leqslant t_i\leqslant n_i \ for \ every \ i \in[k],\ and$ $t_1 +t_2 +\ldots +t_k =r$.

Inverse Binomial Transform:

当an好列式，bn不好列式时，

​ if $$a_n = \sum_{k=s}^{n}\binom{n}{k}b_k$$ then $$b_n = \sum_{k=s}^{n}(-1)^{n-k}\binom{n}{k}a_k$$ (n$\geqslant$s)

  • prove for Inverse Binomial Transform:

    • lemma：image-20210419203320491

      这个引理显然，还可以用组合恒等式来整，时间原因先略。

    • lemma:image-20210419203419669

      $$ \sum_{i=0}^{n-r}(-1)^{(n-r)-i} \binom{n-r}{i} = (1-x)^{n-r} and \ x=1\ so \ it \equiv 0 $$
      by 二项式定理。

    • lemma:image-20210419212654162

    • prove:

    $$let \ {a_n},{b_n} \ be \ two \ sequences\ such\ that \ for\ all\ n\geqslant s,a_n=\sum_{k=s}^{n}\binom{n}{k}b_k.Then\ b_n=\sum_{k=s}^{n}(-1)^{n-k}\binom{n}{k}a_k\ (n\geqslant s)$$

$$
\begin{aligned}
\sum_{k=s}^{n}(-1)^{n-k}\binom{n}{k}a_k & = \sum_{k=s}^{n}(-1)^{n-k}\binom{n}{k}\sum_{i=s}^{k}\binom{k}{i}b_i \& =\sum_{k=s}^{n}\sum_{i=s}^{k}(-1)^{n-k}\binom{n}{k}\binom{k}{i}b_i\&=\sum_{i=s}^n\sum_{k=i}^n(-1)^{n-k}\binom{n}{k}\binom{k}{i}b_i\&=b_n
\end{aligned}
$$

背下来

  • example:
    • 染色:
      image-20210420003357738

generatng function

  • let$$a_0,a_1,\ldots,a_r,\ldots$$ be a sequence of real number. The **generating functioon **of this sequence is defined as:

    $$G(x)=a_0+a_1x+\cdots+a_rx^r+\cdots=\sum_{r=0}^{\infty}a_rx^r.$$

  • formal power series(FPS)形式幂级数

  • Operations：let $$A(x)=\sum_{r=0}^{\infty}a_rx^r,B(x)=\sum_{r=0}^{\infty}b_rx^r$$

    • $$a(x) \cdot B(x) = \sum_{r=o}^{\infty}(\sum_{j=0}^{r}a_j b_{r-j})x^r$$

    pf:

    $$\sum_{m=0}^{\infty}a_{m}x^{m}\cdot \sum_{n=0}^{\infty}b_{n}x^{n} \ =\sum_{m=0}^{\infty}\sum_{n=0}^{\infty}a_{m}b_{n}x^{m+n}\ =\sum_{r=0}^{\infty}\sum_{j=0}^{r}(a_{j}b_{r-j})x^r\quad[m+n=r]$$

    • inverse:

      we say that B(x) is an inverse of A(x) if A(x)B(x)=1.

      • the inverse of A(x) : $A^{-1}(x)$
      • When a(x) has an inverse ,define $\frac{C(x)}{A(x)}=A^{-1}(x)\cdot C(x).$
      • example:let $A(x)=\sum_{r=0}^{\infty}x^r.\ then \ A^{-1}(x)=1-x.$

  • extended binomal coefficient:

    ​ $$let u \in R \ and \ r \in N.$$

    ​ $$\binom{u}{r}= \left{ \begin{array}{}u(u-1)\cdots(u-r+1)/r! & (r>0) \1 & (r=0)\end{array}\right.$$

  • $$let\ \alpha\in R\backslash{0}\ and\ u\in Q.\ (1+\alpha)^{u}=\sum_{r=0}^{\infty}\binom{u}{r}\alpha^rx^r=\sum_{r=0}^{\infty}\frac{u(u-1)\cdots(u-r+1)}{r!}\alpha^rx^r$$

  • $$(1+\alpha)^{-n}=\sum_{r=0}^{\infty}\binom{-n}{r}\alpha^rx^r=\sum_{r=0}^{\infty}(-1)^r\binom{n+r-1}{r}\alpha^rx^r$$

  • $$(1-\alpha)^{-n}=\sum_{r=0}^{\infty}\binom{-n}{r}(-\alpha)^rx^r=\sum_{r=0}^{\infty}\binom{n+r-1}{r}\alpha^rx^r$$

  • counting combinations with GFs:

    • Let $$n>0,r\geqslant0,R_1,\ldots,R_n\subseteq N.$$Let $a_r$ be the number of r-combnination of [n] with repition where every i$\in$[n] appears $r_i$ ($r_i\in R_i$) times.

    • $$a_r = |{(r_1,\ldots,r_n):r_1\in R_1,\ldots,r_n\in R_n,r_1+\cdots+r_n=r}|$$

    • $R_i$ means $r_i\leqslant|R_i|$.$R_i$表示了第i个元素出现的次数有限制。

    • This is also the number of ways of distributing r identical objects into n different boxes such that$r_i(r_i\in R_i)$ objects are sent to box i for all i$\in$[n].

    • in the following equation $\sum {r_i\in R_i} \ maens\ \sum{r_i=0}^{|R_i|}$，theorem:
      $$
      \sum_{r=o}^{\infty}a_rx^r = \prod_{i=1}^{n}\sum_{r_i\in R_i}x^{r_i}
      $$
      prove for it:

$$
\begin{aligned}
\prod_{i=1}^{n}\sum_{r_i \in R_i}x^{r_i} &=  \sum_{r_1\in R_1}x^{r_1} \cdot \sum_{r_2\in R_2}x^{r_2} \cdots \sum_{r_n\in R_n}x^{r_n}\\
&=\sum_{r=0}^{\infty}(\sum_{r_1\in R_1,\ldots,r_n\in R_n,r_1+\cdots+r_n=r})x^r\\&=\sum_{r=0}^{\infty}a_rx^r
\end{aligned}
$$

  • example:
    image-20210419170933770

    image-20210419171056695

    image-20210419173931905

    and from homework we can know ,we can suppose $\alpha$ and let it be 0 in odd be 1 in even to do something.

  • counting permutations with Gfs

    • Let $$n>0,r\geqslant0,R_1,\ldots,R_n\subseteq N.$$Let $a_r$ be the number of r-permutations of [n] with repition where every i$\in$[n] appears $r_i$ ($r_i\in R_i$) times.

    • $$a_r = \sum_{r_1\in R_1,\ldots,r_n\in R_n,r_1+\cdots+r_n=r}\ \frac{r!}{r_1!r_2!\cdots r_n!}$$

    • This is also the number of ways of distributing r different objects into n different boxes such that $r_i(r_i\in R_i)$ objects are sent to box M for all $i\in [n]$.先随便排，任取一个序列，对每个序列，$r_i$个放入第i个box，这个box内部是无序的，所以除以ri！，i是任意的，遍历，除去每一项阶乘。

    • in the following equation $\sum {r_i\in R_i} \ maens\ \sum{r_i=0}^{|R_i|}$,theorem:

      $$
      \sum_{r=0}^{\infty}\frac{a_r}{r!}x^r =\prod {i=1}^{n}\sum{r_i\in R_i}\frac{x^{r_i}}{r_i!}
      $$

    • prove for it:

    • $$
      \begin{aligned}
      \prod_{i=1}^{n}\sum_{r_i \in R_i}\frac{x^{r_i}}{r!} &= \sum_{r_1 \in R_1}\frac{x^{r_1}}{r_1!} \cdot \sum_{r_2 \in R_2}\frac{x^{r_2}}{r_2!} \cdots \sum_{r_n \in R_n}\frac{x^{r_n}}{r_n!}\
      &=\sum_{r=0}^{\infty}(\sum_{r_1\in R_1,\ldots,r_n\in R_n,r_1+\cdots+r_n=r}\ \frac{r!}{r_1!r_2!\cdots r_n!})\frac{x^r}{r!}\&=\sum_{r=0}^{\infty}\frac{a_r}{r!}x^r
      \end{aligned}
      $$

    • example:

      image-20210419190040322

      image-20210419190226805

      image-20210419191159476

      image-20210419190351980

      the recursion of $S_2$ will be shown after (LNRR)

Pigeonhole Principle 鸽笼原理，又名抽屉原理

example:
prove :$let\ n\in Z^+.Let\ A \subseteq {1,2,\ldots,2n}\ have\ n+1\ elements.Then\ \exists x,y\in A \ such \ that\ x|y.$$

answer:

considering that $u\cdot 2^x$,$u\in[n]$ and $x\in N$.

$\forall t \in {1,2,\dots,2n}$ can be written in the formal of $u\cdot 2^x$.

we can consider the $u\in [n]$ as n boxes,and because A has (n+1) elements,so at least one boxes has two number which have the same u and they have the different x. 不妨设$X=u\cdot 2^x \ and\ Y=u\cdot 2^y$,

so if(x<y) X|Y;else if(x>y) Y|X.

QED.

linear homogeneous recurrence relation (LNRR)

image-20210420211406586

Examples for combinatorial mathematics:

  • $\binom{n+r-1}{r}$插板法一列“1”，插加号，两个加号之间“1”的数量为一个值

  • combinatorial equation:

    $$\binom{m+n}{r}=\sum_{k=0}^{r}\binom{m}{r-k}\cdot \binom{n}{k}\\binom{n+1}{r}=\binom{n}{r-1}+\binom{n}{r}\\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}^2\\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}$$

    • combinations of Multiset:

      ​ $\binom{n+r-1}{r}$

    • permutations of Multiset:

      ​ $r!/r_1!\cdots r_n! \quad\ (\sum_{r_i}=r)$

  • Principle of Inclusion-Exclusion: 注意反刨几次

    image-20210420124102390

  • $S_2(n,r)$ : the stirling number of the second kind ,is defined as the number of different ways of distributing n distinguishable objects into j indistinguishable boxes so that no box is empty.(n different balls into r indistinguishable boxes and no empty boxes)

    • $$S_2(n,k) = S_2(n-1,k-1)+S_2(n-1.k)$$

    • 边界：$$S_2(n,0)=0;S_2(0,0)=1;S_2(n,n)=1(n\neq0)$$

      • 将新元素单独放入一个子集，有$S_2(n-1,k-1)$种方案；
      • 将新元素放入一个现有的非空子集，有$kS_2(n-1,k)$种方案。

    • 通项：$$S_2(n,m)=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$

    • Principle of Inclusion-Exclusion:

      使用容斥原理证明该公式。设将n个两两不同的元素，划分到k个两两不同的集合（允许空集）的方案数为$G_i$，将n个两两不同的元素，划分到k个两两不同的非空集合（不允许空集）的方案数为$F_i$。

      Obviously,
      $$
      G_i=k^n\ G_i=\sum_{j=0}^i\binom{i}{j}F_j
      $$
      by 二项式反演:
      $$
      \begin{aligned} F_i&=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}G_j\ &=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}j^n\ &=\sum\limits_{j=0}^{i}\dfrac{i!(-1)^{i-j}j^n}{j!(i-j)!} \end{aligned}
      $$
      considering that the difference bewteen $F_i$ and $S_2(n,i)$.the boxes in $S_2$ is not distinguishable .so $F_i$ is $i!$ times as much as $S_2$

  • $P_j[n]$Partitions of Integers:$n=a_1+a_2+\cdots+a_j$ is called an n-partition with exactly j parts if $a_1 \geqslant a_2 \geqslant \cdots \geqslant a_j$ are all positive integers.

    • $$p_j(n)=|{ (a_1,a_2,\ldots,a_j):a_1+\cdots+a_j =n,a_1\geqslant a_2 \geqslant \cdots \geqslant a_j \geqslant 1 \ are\ integers}|$$

    • $p_j(n)$ is the number of ways of writing n as the sum of $j$ positive integers.

    • 递推：$p_k[n]$表示n分k份。

      • p_1(n)=1,p_n(n)=1
      • if k > n ,p_k(n)=0
      • else if k < n, $p_k(n)=p_k(n-k)+p_{k-1}(n-1)$

    image-20210420140337656
    image-20210420140356308

    • generating function:

      • $$
        \sum_{n=0}^{\infty}((\sum_{r=1}^{n} p_r(n)) \cdot x^n)=\prod_{k=1}^{\infty}(\frac{1}{1-x^k})
        $$

      • 对于具体n分成r份时：
        $$
        \sum_{n=0}^{\infty}p_r(n)x^n =x^r \prod_{j=1}^r\frac{1}{1-x^j}
        $$

image-20210420140446623
image-20210420140504115

  • easy combination and permutation application:

image-20210418165343946

image-20210419005421092

    • shortest path:

      • A $p\times q-grid$ is a collection of $pq$ squares of side length 1, organized as a rectangle of side length p and q.
      • image-20210420180738669
      • the number of the shortest paths is $\frac{(p+q)!}{p!q!}$
      • multiset A= ${p\times \rightarrow,q\times \uparrow}$ , permutation of mulitiset.
      • # of shortest paths = # of permutations of A.

    • T-path:

      • from (x,y) to (x+1,y+1) or (x+1,y-1)

      • T-condition: from A(a,$\alpha$) to B(b,$\beta$) only if

        • $b > a$
        • $b-a \geqslant|\beta -\alpha |$
        • $2|(b+\beta -a-\alpha)$

      • solve permutation of multiset.

a so easy example about generating function:例1 有1克、2克、3克、4克的砝码各一枚，问能称出多少重量，并各有几种称法。

该问题可以看成n拆分成1,2,3,4之和且不允许重复的拆分数，利用母函数计算如下：

$$
(1+x)(1+x^2)(1+x^3)(1+x^4)=1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10}
$$

$2x^4$ 表示称出4克有2种方案，是1+3和2+2，以此类推，超出10克便无法称出。

加括号是第二类斯特林数

已整理ppt：lec1,2,3,4(未举例);lec7,8,9,10,11,12

lec5,lec6（简要）

------------- The end -------------

Welcome to my other publishing channels