DisMat UE 04

ex4-0.pdf
Diskrete_Mathematik_UE_04-0.pdf

4.1

Let $n$ be an arbitrary positive integer, and set $m:=\lceil \frac{n}{2}\rceil$. Show that we have the following inequalities:

$$m^{n-m}\le B_n\le n!(1)$$

Investigate for which $n$ the bounds in (1) are strict.

Untere Schranke: $m^{n-m}\le B_n$

Wir müssen nur zeigen dass es mindestens $m^{n-m}$ Blöcke gibt.
Angenommen es gibt $m$ Blöcke die die Zahlen von $\mathrm{1...}m$ enthalten.
Nun teilen wir die Zahlen $n-m...n$ auf diese Blöcke auf.
Dann kann man diese $n-m$ Zahlen in $m^{n-m}$ wegen aufteilen.

Striktheit:
Wenn $n=1$ ist dann ist $m=1$ und somit gilt:

$$m^{1-1}=1=B_1$$

⇒ Gleicheit
Wenn $n\ge 2$ ist gibt es immer eine Partition die nicht in der Form ensteht. Zum Beispiel alle in ein Block.
⇒ Strikt

Obere Schranke

Beweis per Induktion:

Für $n=1$:
$B_1=1=n!$

Für alle $i\le n$
Das weitere $i$ kann man auf in einen der $i-1$ bestehenden oder einen neuen Block einfügen.

Damit gilt:

$$B_i\le (i-1+1)B_{i-1}\le (i-1+1)(i-1)!=(i-1+1)!=i!$$

Striktheit:
Bei
$n=1:B_1=1=1!$
$n=2:B_2=2=2!$
⇒ Gleichheit

ab
$n=3:B_3=5<6=3!$

⇒ strikt
denn

$$(n+1)B_n<(n+1)n!\forall n\ge 3$$

4.4

Show that, the parity of the Bell numbers is described by the following statement: for all $n\ge 0$, we have:

$$\text{the Bell number }{B}_n\text{ is }\{\begin{array}{ll}\text{even}& \text{if }n=3t+2\text{ for }t\in {\mathbb{Z}}_{\ge 0};\\ \text{odd}& \text{otherwise.}\end{array}$$

n	B_n	B_n mod 2
0	1	1
1	1	1
2	2	0
3	5	1
4	15	1
5	52	0
6	203	1
7	877	1
8	4140	0

Daher müssen wir nur zeigen dass:

$$B_n\equiv B_{n+3}\mathrm{mod}2$$

betrachte gerade und ungerade Sterling numbers getrennt:

$$G_n:=\sum _{k=0\text{ und gerade}}^{n}S(n,k)$$ $$U_n:=\sum _{k=0\text{ und ungerade}}^{n}S(n,k)$$

Ab hier nehmen wir alles$\mathrm{mod}2$

$$\begin{array}{rl}{G}_{n+1}& \equiv \sum _{k\text{ gerade}}S(n+1,k)\\ & \equiv \sum _{k\text{ gerade}}(kS(n,k)+S(n,k-1))\\ & \equiv \sum _{k\text{ gerade}}S(n,k-1))\\ & \equiv U_n\end{array}$$

da

$$\sum _{k\text{ gerade}}k\cdot S(n,k)\equiv 0$$

und

$$\begin{array}{rl}{U}_{n+1}& \equiv \sum _{k\text{ ungerade}}S(n+1,k)\\ & \equiv \sum _{k\text{ ungerade}}(kS(n,k)+S(n,k-1))\\ & \equiv \sum _{k\text{ ungerade}}S(n,k)+\sum _{k\text{ ungerade}}S(n,k-1))\\ & \equiv U_n+G_n\end{array}$$

Es gilt

$$B_n=G_n+U_n$$

Und da$\mathrm{mod}2$ kann man in der Addition alle $G_n$ oder $U_n$ die zweimal Wegstreichen.

Daher gilt:

$$\begin{array}{rl}{B}_{n+1}& \equiv G_{n+1}+U_{n+1}\\ & \equiv U_n+(U_n+G_n)\\ & \equiv G_n\equiv B_n+U_n\end{array}$$ $$\begin{array}{rl}{B}_{n+2}& \equiv B_{n+1}+U_{n+1}\\ & \equiv G_n+(U_n+G_n)\\ & \equiv U_n\end{array}$$ $$\begin{array}{rl}{B}_{n+3}& \equiv B_{n+2}+U_{n+2}\\ & \equiv U_n+(U_{n+1}+G_{n+1})\\ & \equiv U_n+((U_n+G_n)+U_n)\\ & \equiv U_n+U_n+B_n\\ & \equiv B_n\end{array}$$