Combinatorial interpretations

$p_k(n) := (n)_k := n(n-1)\dots(n-k+1) = \frac{n!}{(n-k)!}
  = \frac{\Gamma(n+1)}{\Gamma(n-k+1)} = nPk$:
  ways of picking $k$ elements (in order) from an $n$ element set.
  (the $\Gamma$ is for extending to non-integers)
$q_k(n) := \binom{n}{k} = \frac{1}{k!} p_k(n)
  = \frac{1}{k!}(n)_k = nCk$:
  ways of picking $k$ elements (ignoring order) from an $n$ element set.
Presumably you can also write this in terms of the Beta function, but
I'm not sure of the use (the Beta function is almost the reciprocal).

Differentiating:
$\Delta (n)_k = k(n)_{k-1}$
Proof:
$(n+1)_k = (n)_k + k(n)_{k-1}$
This is a recurrence formula:
to pick $k$ terms from $n+1$ elements, you can either:
- miss the last term and instead pick from the remaining,
  which gives $(n)_k$ (first term)
- or hit the last term at one of the $k$ places (factor of $k$),
  each of which leaves $k-1$ choices from the remaining $n$ elements.
[give a direct interpretation of the summation:
 that's actually in my `discrete analog of Cavalieri']
-------------------------------------
Note that the combinatorial interpretation makes it clear that $q_k$
is numeric.
-------------------------------------
Expanding $2^n$ as a discrete Taylor series obviously gives a
coefficient of $1$ for all the $q_k$, since $\Delta 2^n = 2^n$.
Thus
$2^n = \sum \binom{n}{k} = \sum \frac{1}{k!} (n)_k$
Note especially that for any integer $n$, this sum is finite:
for $k>n$ the term is zero.

This is the discrete analog of the expansion of $e^x$ and for the same
formal reason:
if $Df=f$ or $\Delta f = f$, all the coefficients in the power series
must be the same, and must equal $f(0)$.

The combinatorial interpretation is that
$2^n$ is the number of subsets of a set of $n$ elements,
while the sum is the number of elements of a given order.

So cool, eh?
