I want to count something similar to unsigned Stirling numbers of the first kind. Can someone tell me what math describes the quantity I'm interested in?
Suppose I have $n$ people numbered $1, 2, ..., n$ and a sequence of $n$ empty sets. I sequentially choose one person at a time, in the ordering of their numbers, and either place that person in any non-empty set in my sequence or in the first empty set in my sequence. For example, if $n=3$, I start with the sequence of 3 empty sets:
{}{}{}
For person $1$, I must place them in the first empty set:
{1}{}{}
For person $2$, I have two choices. I can either add them to the first set or the second set:
{1, 2}{}{}
{1}{2}{}
For person $3$, if I took the first option for person $2$, I now have two choices:
{1, 2, 3}{}{}
{1, 2}{3}{}
And if I took the second option for person $2$, I now have three choices:
{1, 3}{2}{}
{1}{2, 3}{}
{1}{2}{3}
I'm interested in counting the number of ways that the last person $n$ can end up in each set. In this example, there are 2 ways for person $3$ to end up in the first set, 2 ways to end up in the second set, and 1 way to end up in the third set. What combinatoric function describes the number of ways that the last person $n$ can end up in each set?
In order for item $n$ to end up in set $k$, the first $n-1$ items need to span at least $k-1$ sets. The number of ways $n-1$ objects can span exactly $i$ sets is the Stirling number ${n-1 \brace i }$. Therefore, the number of ways to have item $n$ in spot $k$ is $$ {n-1 \brace k-1} + {n-1 \brace k} + \dots + {n-1 \brace n-1} $$