Generalprobe B

Sechs verschiedene Kugeln werden auf drei beschriftete Schachteln verteilt. Wie viele Verteilungen lassen keine Schachtel leer?

Beweise für $n\ge1$: $\sum_{k=0}^n k\binom nk=n2^{n-1}$.

Zeige: Jede Folge von zehn verschiedenen reellen Zahlen enthält eine streng wachsende oder streng fallende Teilfolge der Länge 4.

Wie viele monotone Wege von $(0,0)$ nach $(6,6)$ bleiben auf oder unterhalb $y=x$ und vermeiden $(3,3)$?