Consider the set $\{1, 2, 3, \ldots, n\}$. In how many ways can the elements be arranged in an array such that an entry is either placed in the top row or immediately below another entry in the array?
1: 1
2:
1 2 2 1 1 2
2 1
3:
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
1 2 1 2 2 1 2 1 1 3 1 3 3 1 3 1 2 3 2 3 3 2 3 2
3 3 3 3 2 2 2 2 1 1 1 1
1 1 2 2 3 3
2 3 1 3 1 2
3 2 3 1 2 1
4: would take a long time to format and layout here
example $n=5$:
1 2 3
4
5
which results in
1!, 2!+2!, 3!+3!+3!+3!, ...
1, 4, 24, ...
Originally, I came up with something like:
(wrong) $f(c) = \sum_{n=1}^{c} (c!)$, which gives: $1,4,18,96$
Then I came up with this:
$f\left(c\right)=2^{\left(c-1\right)}c!$
which results in the same answer $1, 4, 24, 192, \ldots$, but I don't know if its correct beyond that point up to infinity, and I of course don't want to list them out because even $f(4)=192$.
Is my solution correct?
Your proposed answer $2^{n - 1}n!$ is correct.
Notice that each column corresponds to a nonempty subset of $\{1, 2, 3, \ldots, n\}$. For instance, in your example, \begin{matrix} 1 & 2 & 3\\ & & 4\\ & & 5 \end{matrix} the set $\{1, 2, 3, 4, 5\}$ is decomposed into the sequence of subsets $\{1\}, \{2\}, \{3, 4, 5\}$. Therefore, each such array corresponds to expressing the set $\{1, 2, 3, \ldots, n\}$ as a sequence of mutually disjoint nonempty subsets whose union is $\{1, 2, 3, \ldots, n\}$.
The number of columns is the number of compositions of $n$, that is, the number of ways of writing $n$ as a sum of a sequence of positive integers. There are $2^{n - 1}$ such sequences. For instance, if $n = 5$, there are $2^{5 - 1} = 2^4 = 16$ compositions. They are \begin{align*} 5 & = 5\\ & = 4 + 1\\ & = 1 + 4\\ & = 3 + 2\\ & = 2 + 3\\ & = 3 + 1 + 1\\ & = 1 + 3 + 1\\ & = 1 + 1 + 3\\ & = 2 + 2 + 1\\ & = 2 + 1 + 2\\ & = 1 + 2 + 2\\ & = 2 + 1 + 1 + 1\\ & = 1 + 2 + 1 + 1\\ & = 1 + 1 + 2 + 1\\ & = 1 + 1 + 1 + 2\\ & = 1 + 1 + 1 + 1 + 1 \end{align*} To see why, write $n$ as a row of $n$ ones. There are $n - 1$ spaces between successive ones in the row.
$$1 \square 1 \square 1 \square \cdots \square 1 \square 1$$ A composition is determined by deciding whether to fill each such space with an addition sign or to leave it blank. For instance, if $n = 5$, the four decisions fill, fill, blank, blank yield $$1 + 1 + 1 1 1$$ which corresponds to the composition $1 + 1 + 3$, which means we place one entry in the first column, one entry in the second column, and three entries in the third column.
For each of the possible $2^{n - 1}$ compositions that tell us where we can place the numbers in the array (how many elements to place in each subset in the sequence of nonempty subsets), we can arrange the $n$ numbers in those spaces in $n!$ ways. Hence, the number of ways the elements of the set $\{1, 2, 3, \ldots, n\}$ can be arranged in an array such that an entry not in the top row always has an entry immediately above it (the number of sequences of mutually disjoint nonempty subsets whose union is the whole set) is $2^{n - 1}n!$.