Number of ways to pair elements, then pair up pairs, and so on Assume you have a set of $n$ distinct elements. A single element can be placed in a group, and groups can be combined to form more groups. A group must contain at least one element to be valid, and cannot contain any element more than once.
Valid Groups
$(1)$
$(1\to2)$
$(3\to(1\to2))$
Invalid Groups
$(1\to1)$
$()$
When combining groups, the order of the elements does not matter.
$(1\to2) = (2\to1)$
However, each group is it's own distinct entity so the order of combinations does matter
$((1\to2)\to3) \ne ((1\to3)\to2)$
Under these rules, how many valid groups can be created from a set of $n$ elements? I know, calculating by hand that when $n = 1$ there is $1$ valid group, when $n = 2$ there are $3$ valid groups, when $n = 3$ there are $9$ valid groups, and when $n = 4$ there are $37$ valid groups.
Apologies if I'm using the notation and terminology incorrectly. I'm ignorant to whatever branch of mathematics this is.
 A: Answer: The number of ways to form groups is
$$
\binom n1+\binom n2 1!!+\binom n3 3!! + \binom n4 5!!+ \dots + \binom nn (2n-3)!!
$$
Here, $(2k-1)!!=(2k-1)\times (2k-3)\times \cdots \times 3\times 1$ is the product of the first $k$ odd numbers. The above formula can be written succinctly as $$\sum_{k=1}^n \binom nk (2k-3)!!$$ as long as we adopt the funny-looking convention that $(-1)!!=1$.
Proof: First, let us count the number of ways to form this hierarchical group structure which uses all of the numbers in $\{1,\dots,n\}$. This is exactly answered by this other MSE question:
How many ways to write a commutative non-associative product of $n$ terms?
Two answers there prove that the number of ways is $(2n-3)!!$ for all $n\ge 1$. For your question, you first need choose the number of elements $k$ your group structure will use, then choose the particular elements in $\binom{n}k$ ways, then finally put a group structure on them in $(2k-3)!!$ ways. This leads exactly to the advertised sum.
For example, when $n=4$, my formula gives
$$
\binom 41 + \binom 42 + \binom 43\cdot 3+\binom 44\cdot 3\cdot 5=4+6+12+15=37\;\;\color{green}{\checkmark}
$$
