It's very easy to prove that:
$$\sum_k \left\{k\atop n\right\}z^k=\frac{z^n}{(1-z)(1-2z)…(1-nz)}$$
But this generating function looks very pretty, so my question is: does this identity have some simple combinatorial interpretation?
[Math] Generating function with Stirling’s numbers of the second kind
combinatoricsgenerating-functionsstirling-numbers
Related Solutions
The most conceptual explanation uses composition of species.
Recall that your Stirling number of the first kind counts collections of $k$ cycles that together contain $n$ points.
Now, you first determine the exponential generating function for cycles:
There are $(n-1)!$ cycles of length $n$, for example, because you regard the list of elements coming after 1 in the cycle.
So, you get $Cycles(z)=\sum_n \frac{(n-1)!}{n!}z^n= \sum \frac{z^n}{n}= \log(\frac 1 {1-z})$.
Then, you determine the exponential generating function for sets of size $k$.
There is only one possibility to do so and it has size $k$:
$Sets_k(z)=\frac{z^k}{k!}$
And, now the miracle occurs:
You want to count $k$-sets of cycles and you find the exponential generating function by calculating $Sets_k$ of $Cycles$ with composition of functions.
So, you get $Sets_k(Cycles(z))= \frac{(\log(\frac 1 {1-z}))^k}{k!}$.
You can read more on this on the corresponding Wikipedia page or you can read much more on this in the book Combinatorial Species and Tree-Like Structures by F. Bergeron, Gilbert Labelle, Pierre LeRoux.
I do not think EGF's are the way to go here. There is just no nice way to extract the EGF for $F_{2n}$ from that of $F_n$. But here is an OGF solution.
First, calculate the OGF of the left hand side. \begin{align} \sum_{n\ge 0}x^n\sum_{k=0}^n \binom{n}kF_k &=\sum_{k\ge 0}F_k\sum_{n\ge k} \binom{n}kx^n \\&=\sum_{k\ge 0}F_k\sum_{n\ge k} (-1)^{n-k}\binom{-k-1}{n-k}x^n \\&=\sum_{k\ge 0}F_kx^k\sum_{n\ge k} \binom{-k-1}{n-k}(-x)^{n-k} \\&=\sum_{k\ge 0}F_kx^k\sum_{n\ge 0} \binom{-k-1}{n}(-x)^{n} \\&=\sum_{k\ge 0}F_kx^k(1-x)^{-k-1} \\&=(1-x)^{-1}\sum_{k\ge 0}F_k\times \left(\frac{x}{1-x}\right)^k \end{align} Now, recalling that the generating function for the Fibonacci numbers is $f(z):=\sum_{k\ge 0} F_kz^k=\frac{z}{1-z-z^2}$, this is equal to $$ \sum_{n\ge 0}x^n\left(\sum_{k=0}^n \binom{n}kF_k\right)=(1-x)^{-1}\cdot \frac{\left(\frac{x}{1-x}\right)}{1-\left(\frac{x}{1-x}\right)-\left(\frac{x}{1-x}\right)^2}. $$ You can then verify this is the same thing as $\frac{F(\sqrt{x})+F(-\sqrt{x})}2$, the OGF for $F_{2n}$.
Best Answer
Yes, this equation has a combinatorial interpretation.
The number $\left\{k\atop n\right\}$ counts the number of partitions of the linearly ordered set $\mathbf k=\{1, \dots, k\}$ into $n$ nonempty subsets. Let us see how one can think of such a partition. Below, you can see a partition of $\mathbf{15}$ into $4$ nonempty subsets (the linear order goes from left to right).
The data of this partition is equivalent to the following data:
Here, a vertical line was inserted just before a new color is encountered when going from left to right. The colors were ordered by their order of occurence:
$$\text{Red}<\text{Blue}<\text{Green}<\text{Pink}$$
and were assigned the numbers $0,1,2,3$ respectively. Now, remark that the data of the above decomposition is also equivalent to the data of the diagram
because the obscured numbers are just $0,1,2,3$ in order of occurence. The initial partition can be completely reconstructed from this last diagram. I'll leave it up to you to check that this decomposition yields the claimed identity of power series.