An approximation of the ordered Bell numbers

Question

So my problem is the following: I have $n$ ice-cream flavors and I must rank them, allowing that I can place more than one flavor in some ranks. So for example if I have 4 flavors, I can put in the first place chocolate and vanilla because I like them equally, and then strawberry and in the last place mint. So I made a rank with three spots in which I just placed 4 flavors.

If $a_n$ is the number of ways I can do this, I have to find its generating function and then with it compute $a_3$. I already know the answer for both of these questions, but I got them separately, as follows:

So we separate the number of ways we can rank $n$ flavors into a $k$-rank and then add them all together. For this purpose, we use the Stirling numbers of the second kind. If we label each flavor with an element of the set $[n]$, we can partition this set into $k$ equal parts in $S(n,k)$ ways, then we can label the $k$ ranks with labels of $[k]$ in $k!$ different ways. So this expression is $k!\cdot S(n,k)$, and therefore, $$a_n=\sum_{k=1}^n k!\cdot S(n,k)$$

It is easy to see here that $a_3=13$.

On the other hand, the expression above looks like the ordered Bell numbers, and I also found that its generating function is $$A(x)=\frac{1}{2-e^x}$$But I do not know how to further link these two expressions and with the generating function, find $a_3$. What am I missing/doing wrong? I can think maybe using asymptotic analysis? (I am not very familiar with this, but I think I can try, but if there is an easier reasoning, I will take it haha)

Answer 1

Its not entirely clear what you are asking.

https://oeis.org/A000670 gives further details on the sequence of ordered Bell numbers, also known as Fubini numbers.

The generating function power series is $$\frac{1}{2-e^x}=\sum _{n=0}^{\infty } \frac{x^n }{n!}\sum _{k=0}^n k! \,\mathcal{S}(n,k)$$

As the generic Taylor series expansion at $x=0$ is

$$f[x]=f(0)+x f'(0)+\frac{x^2}{2!} f''(0)+\frac{x^3}{3!} f'''(0) +...,$$

$a_3$ can be found by differenting the generating function 3 times at $x=0$, thus $$a_3=\left.f'''\left(\frac{1}{2-e^x}\right)\right|_{x=0}=\left.\frac{6 e^{2 x}}{\left(2-e^x\right)^3}+\frac{6 e^{3 x}}{\left(2-e^x\right)^4}+\frac{e^x}{\left(2-e^x\right)^2}\right|_{x=0}=13$$

Answer 2

James has already answer your question(+1) but i will introduce some ideas that will clarify the "I do not know how to further link these two expressions".

If you are asking for intuition in between the expressions, the right place for it is called "Combinatorial species". Notice that $$\frac{1}{2-e^x}=\frac{1}{1-(e^x-1)}.$$ It should be clear from the geometric series that this means taking sequences (in your context this are the orders!) of whatever $e^x-1$ counts. Notice then that what $e^x-1=\sum _{n\geq 1}\frac{x^n}{n!}$ does is it creates a sequence without order (because you are dividing by $n!$) Notice that this nonempty(because we are taking out the case $n=0$) without order is what people call blocks from a partition(in your case is when the ice cream flavor is in the same rank, you do not need to order them).