Let's say a set $S$ has $n$ elements, and it needs to be partitioned into $3$ different, unordered partitions. How do I obtain a general formula for this?
I think I can calculate it if I know the value of $n$.
For example, if $n=3$ then it's partitioned as $1,1,1$ so there's only $1$ way.
If $n=4$ then it's $2,1,1$ so there's ${4\choose2}=6 $ ways.
If $n=5$ then it's $2,2,1$ or $3,1,1$ and there's $15+10=25$ ways.
I can't figure out $n$ in general though. My latest attempt was summation: $$\sum_{a=1}^{n-2} \quad \sum_{b=1}^{n-2-a} \quad {n\choose a}{{n-a}\choose b} $$ but the partitions won't be unordered (and the summation is probably wrong too).
I have a hint to regard the first $x$ elements in the first partition, and the $x+1$-th element in the second, but I'm not sure where to proceed from this.
The number of partitions of a set of size $n$ into $k$ non-empty sets is counted by the Stirling numbers of the second kind. As explained in the link, they satisfy the recurrence
$$ \left\{ \begin{array}{c} n \\ k \end{array} \right\} = k\left\{ \begin{array}{c} n - 1 \\ k \end{array} \right\}+\left\{ \begin{array}{c} n - 1 \\ k - 1 \end{array} \right\}. $$
In particular, we have
$$ \left\{ \begin{array}{c} n \\ 3 \end{array} \right\} = 3\left\{ \begin{array}{c} n - 1 \\ 3 \end{array} \right\}+\left\{ \begin{array}{c} n - 1 \\ 2 \end{array} \right\} = 3\left\{ \begin{array}{c} n - 1 \\ 3 \end{array} \right\} + 2^{n-1}-1, $$
and therefore,
\begin{align} \left\{ \begin{array}{c} n \\ 3 \end{array} \right\} &= 3 \left\{ \begin{array}{c} n - 1 \\ 3 \end{array} \right\} + 2^{n-2}-1 \\ &= 3^2 \left\{ \begin{array}{c} n - 2 \\ 3 \end{array} \right\} + 3 \cdot 2^{n-3} + 2^{n-2} -3-1 \\ &= 3^3 \left\{ \begin{array}{c} n - 3 \\ 3 \end{array} \right\} + 3^2 \cdot 2^{n - 4} + 3 \cdot 2^{n - 3} + 2^{n - 2} - 3^2 - 3 - 1 \\ &= 3^r \left\{ \begin{array}{c} n - r \\ 3 \end{array} \right\} + \sum_{i=1}^{r} 3^{i-1} \cdot 2^{n - 1 - i} - \sum_{i=0}^{r-2} 3^i \\ &= 3^{n-3} \left\{ \begin{array}{c} 3 \\ 3 \end{array} \right\} + \sum_{i=1}^{n-3} 3^{i-1} \cdot 2^{n - 1 - i} - \sum_{i=0}^{n-4} 3^i \\ &= 3^{n-3} + 2^{n-2} \frac{(\frac{3}{2})^{n-3} - 1}{\frac{3}{2} - 1} - \frac{3^{n - 2} - 1}{3 - 1} \\ &= \frac{1}{6} \left( 3^n - 3 \cdot 2^n + 3 \right). \end{align}
In general, one can find a formula for $\left\{ \begin{array}{c} n \\ k \end{array} \right\}$ in two ways. First, one can use the fact that the number of surjective functions $\{1,\dots,n\} \to \{1,\dots,k\}$ is $k!\left\{ \begin{array}{c} n \\ k \end{array} \right\}$ and counting this using inclusion-exclusion:
Let $A_i$, $i = 1,\dots,k$ denote the set of functions $\{1,\dots,n\} \to \{1,\dots,k\}$ whose image does not contain $i$. Let for $S \subseteq \{1,\dots,k\}$, let $A_S = \bigcap_{i \in S} A_i$. Then, by inclusion-exclusion
\begin{align} \# (A_1 \cup \dots \cup A_k) &= \sum_{\varnothing \ne S \subseteq \{1,\dots,k\}} (-1)^{\#S - 1} \# A_S \\ k^n - k!\left\{ \begin{array}{c} n \\ k \end{array} \right\} &= \sum_{i = 1}^k \sum_{\#S = i} (-1)^{i - 1} (k - i)^n \\ k!\left\{ \begin{array}{c} n \\ k \end{array} \right\} &= k^n + \sum_{i = 1}^k \sum_{\#S = i} (-1)^{i} (k - i)^n \\ &= k^n + \sum_{i = 1}^k \binom{k}{i} (-1)^{i} (k - i)^n \\ &= \sum_{i = 0}^k \binom{k}{i} (-1)^{i} (k - i)^n \\ &= \sum_{i = 0}^k \binom{k}{i} (-1)^{k - i} i^n \\ \left\{ \begin{array}{c} n \\ k \end{array} \right\} &= \frac{1}{k!} \sum_{i = 0}^k \binom{k}{i} (-1)^{k - i} i^n. \end{align}
Or, one can use a generating function approach:
Let $[x^ny^k]$ denote the coefficient of $x^ny^k$ in a given formal power series. Then
\begin{align} \left\{ \begin{array}{c} n \\ k \end{array} \right\} &= n![x^ny^k] \exp(y(e^x - 1)) \\ &= n![x^ny^k] \sum_{j = 0}^\infty \frac{y^j(e^x - 1)^j}{j!} \\ &= \frac{n!}{k!}[x^n] (e^x - 1)^k \\ &= \frac{n!}{k!}[x^n] \sum_{i = 0}^k \binom{k}{i} e^{ix}(-1)^{k-i} \\ &= \frac{1}{k!} \sum_{i = 0}^k \binom{k}{i} n![x^n]e^{ix}(-1)^{k-i} \\ &= \frac{1}{k!} \sum_{i = 0}^k \binom{k}{i} i^n (-1)^{k-i}. \end{align}
Here $e^x - 1$ is the exponential generating function for non-empty sets. That is $n$ is the number of non-empty sets of size $n$. Multiplying by $y$ lets us keep track of the number of non-empty sets we are using and taking $\exp$ gives us sets of non-empty sets (i.e. partitions into non-empty sets).