Let $N = \{1,2,3\}$. Then we can encounter $2^3-1$ coalitions $S \subset 2^N \setminus \emptyset$, namely $\{\{1\}, \{2\}, \{3\}, \{12\}, \{13\}, \{23\}, \{123\}\}$ and five coalitions structures $CS = \{\{1,2,3\}, \{1,23\}, \{12,3\}, \{13,2\}, \{123\}\}$. In Sandholm et al they state that the number of coalitions structures for an arbitrary set $N \subset \mathbb N$ with $n = |N|$ is given by \begin{align} |CS| = \sum_{i \in N}Z(n,i) \end{align} with $Z(n,i) = iZ(n-1,i) + Z(n-1,i-1)$ (Stirling number of the second kind) and $Z(n,n) = Z(n,1) = 1$. They further state.
Proposition 1 The number of coalition structures is $\mathcal O(n^n)$ and $\omega(n^\frac{n}{2})$.
I would't know how to interpret the statements. Can someone provide an example for $n = 4$? (Sorry, I don't know what tag would suit.)
An explicit expression is given by \begin{align} &|CS|(n) = \sum_{i = 1}^n{\frac{1}{i!}\sum_{k = 0}^i{(-1)^k\frac{i!}{k!(i-k)!}(i-k)^n}}\\ &|CS|(n) = \sum_{k=0}^{n-1}{\frac{(n-1)!}{k!(n-1-k)!}}|CS|(n-1) . \end{align}