"Binomial theorem"-like identities There are several identities which resemble the binomial theorem.  For starters, we have the binomial theorem itself: $$(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$$
But I just learned from the book "Concrete Mathematics", Exercise 5.37, that the "falling factorial" $x^{\underline{k}} = x(x-1)\ldots(x-k+1)$ satisfies a similar identity: $$(x+y)^\underline{n} = \sum_{k=0}^n \binom{n}{k} x^\underline{k} y^\underline{n-k}$$ The "rising factorial" $x^{\overline{k}} = x(x+1)\ldots(x+k-1)$ also satisfies such an  identity.
Sometimes, the identity involves a product instead of a sum on the left side.  If $f$ and $g$ are $n$-times differentiable functions on $\mathbb{R}$, then this generalization of the product rule holds: $$(fg)^{(n)} = \sum_{k=0}^n \binom{n}{k} f^{(k)} g^{(n-k)}$$ where $f^{(k)}$ denotes the $k$-th derivative of $f$, and the 0th derivative of a function is the function itself.
Question: Are there any more of these binomial-theorem like identities in other contexts?  Are these identities part of some more general result, where we can axiomatize some conditions under which some "iterative" process satisfies a binomial-like theorem?
 A: I up-voted Qiaochu Yuan's answer.  To be more explicit: Say you have a sequence of scalars $c_1,c_2,c_3,\ldots$ (starting with $1$, not with $0$).  Then you can find a sequence of polynomials $p_0(x),p_1(x),p_2(x),\ldots$ (starting with $0$, not with $1$) such that for $n=0,1,2,3,\ldots$
$$
p_n(x+y) = \sum_{k=0}^n \binom n k p_k(x) p_{n-k}(y)
$$
and $p_n\,'(0)=c_n$ for $n\ge 1$.  This is a "polynomial sequence of binomial type".
And what I just wrote amounts to a definition by recursion, so if you want to write out, for example $p_6(x)$ with all its coefficients as polynomials in $c_1,\ldots, c_6$, just apply what I wrote above.  The polynomials in $c_1,c_2,c_3,\ldots$ that are the coefficients are the incomplete Bell polynomials, named after Eric Temple Bell.
A: Maybe the binomial transform might also be of interest to you. One example from the page:

The binomial transform is the shift operator for the Bell numbers. That is,
  $$    B_{n+1}=\sum_{k=0}^n {n\choose k} B_k $$
  where the $B_n$ are the Bell numbers.

A: Some keywords you'll want to look into: binomial type, Appell sequence, Sheffer sequence, umbral calculus. The references in the corresponding Wikipedia articles are good too. 
Edit: In some sense, all of these identities can be deduced from the last one. Setting
$$f(t) = e^{xt}, g(t) = e^{yt}$$
produces the binomial theorem, and setting
$$f(t) = (1 + t)^x = \exp (x \log (1 + t)), g(t) = (1 + t)^y = \exp ( y \log (1 + t))$$
produces the second identity. From this perspective one can think of the study of generalized binomial theorems as being all about generating functions of the form $\exp (x h(t))$ where $h(0) = 0$; setting
$$f(t) = \exp (x h(t)), g(t) = \exp (y h(t))$$
produces a fairly general binomial theorem, especially if one writes $h(t) = \sum_{n \ge 1} h_n t^n$ as a formal power series in formal variables.
A: Not sure if this qualifies as an answer: I think the coefficients $\binom{n}{k}$ say what these formula are about. You read "$n$ choose $k$" and that's basically it. There are several possibilities to form the summands on the right hand side and in you examples one sees that the number is exactly the number of ways to choose $k$ out of $n$.
