# Proof

• Let $n,r\ge 0$ be integers.
• The number of partitions of $n$ objects into $r$ non-empty subsets corresponds to the Stirling numbers of the second kind $\left\{\begin{array}{c}n\\r\end{array}\right\}.$
• Every partition of $n$ objects into $r$ non-empty subsets leads to at least one partition of $n$ objects into $r$ cycles.
• Since the number of partitions of $n$ objects into $r$ cycles corresponds to the Stirling numbers of the first kind $\left[\begin{array}{c}n\\r\end{array}\right],$ it follows $\left[\begin{array}{c}n\\r\end{array}\right]\ge \left\{\begin{array}{c}n\\r\end{array}\right\}$ for all $n,r\ge 0.$
• The number of arrangements of $n$ objects into $n$ non-empty subsets and $n$ cycles equal each other and is $1$
• Therefore, $\left[\begin{array}{c}n\\n\end{array}\right]=\left\{\begin{array}{c}n\\n\end{array}\right\}=1.$
• In any arrangement of $n$ objects into $n-1$ non-empty subsets there is exactly one subset with $2$ elements and all remaining subsets are singletons.
• Moreover, all these subsets with either $1$ or $2$ elements correspond to cycles and there are $\binom n2=\frac{n(n-1)}{2}$ such arrangements.
• Therefore, $\left[\begin{array}{c}n-1\\n\end{array}\right]=\left\{\begin{array}{c}n\\n-1\end{array}\right\}=\left(\begin{array}{c}n\\2\end{array}\right)=\frac{n(n-1)}{2}.$

Github: ### References

#### Bibliography

1. Graham L. Ronald, Knuth E. Donald, Patashnik Oren: "Concrete Mathematics", Addison-Wesley, 1994, 2nd Edition