Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For all real numbers $x$, and all non-negative integers $n$, $$ x^n = \sum_{k=0}^{n} S(n,k)\frac{x!}{(x-k)!} $$

I have a 2 questions with the proof that my textbook presents.

First they say that they will prove this for a stronger statement -- that the equality holds for all positive integers $x$. (1) Why is this a stronger statement? Aren't stronger statements usually more generalized?

The LHS is the number of all functions from $1,\ldots,n$ to $1,\ldots,x.$ (2) Why is this "obvious"? (What does it mean?).

share|improve this question
    
Are you sure that the stronger statement isn’t that the equality holds for all positive real numbers $x$, with the fraction replaced by $x(x-1)\dots(x-k+1)$? –  Brian M. Scott Jan 5 '13 at 23:43
1  
I'm not sure about the first, but for the second. If we are mapping elements of $\{1,...,n\}$ to elements of $\{1,...,x\}$, for each of 1 to $n$, we have $x$ choices for our value of our function, so in total we have $x^n$ possibilities for our function. –  Alex J Best Jan 5 '13 at 23:44
    
@BrianM.Scott Yeah, I'm looking at it right now and it says, in italics, all positive integers x. –  AlanH Jan 5 '13 at 23:51
    
As stated, it doesn’t really make sense when $x$ is a positive integer less than $k$: it requires you to take the factorial of a negative integer. –  Brian M. Scott Jan 6 '13 at 0:01
    
@BrianM.Scott Maybe it's assumed for all positive integers greater than equal to $k$? –  AlanH Jan 6 '13 at 1:15

2 Answers 2

up vote 4 down vote accepted

I don’t know exactly what your text actually says, but the general fact is that

$$x^n=\sum_{k\ge 0}\left\{n\atop k\right\}x^{\underline k}\;,\tag{1}$$

where $x^{\underline k}=x(x-1)(x-2)\dots(x-k+1)$; this holds for integer $n\ge 0$. Note that if $x$ is an integer and $x\ge k$, then $$x^{\underline k}=\frac{x!}{(x-k)!}\;,$$ and $(1)$ becomes your formula.

As for the second question, if $n$ and $x$ are positive integers, choosing a function $f$ from $\{1,\dots,n\}$ to $\{1,\dots,x\}$ is the same as choosing a value in $\{1,\dots,x\}$ for each $k\in\{1,\dots,n\}$. There are $x$ different ways to choose $f(1)$. For each of those there are $x$ ways to choose $f(2)$, so there are altogether $x^2$ combinations of values of $f(1)$ and $f(2)$. Each new choice of an $f(k)$ can be made in $x$ different ways, so in the end you have $x^n$ possible sequences of choices, i.e., $x^n$ functions from from $\{1,\dots,n\}$ to $\{1,\dots,x\}$.

share|improve this answer

The number $x^n$ is the number of functions from a size-$n$ set to a size-$x$ set. For example, $3^2=9$ is the number of functions from $\{a,b\}$ into $\{1,2,3\}$. You have $f(a)=\text{one of }1,2,3$ and $f(b)=\text{one of }1,2,3$, and it can be any of the three each time, so there are $9$ such functions.

The Stirling number $S(n,k)$ is the number of (un-ordered) partitions of a set of size $n$ into $k$ subsets. By definition of "partition" these are non-empty non-intersecting subsets whose union is the whole size-$n$ set.

For every function $f$ from a size-$n$ set $A$ to a size-$x$ set $B$, there is a partition of the domain $A$ defined by saying $x,y$ both belong to the same part if and only if $f(x)=f(y)$. So one way of specifying a function is this: First choose that partition. Call the number of parts $k$. Then choose which of the $x$ members of $B$ you'll map the members of the first part to. There are $x$ possible choices. Then choose which member of $B$ you'll map the members of the second part to. There are $x-1$ possible choices. Keep going, until you've chosen from among $x(x-1)(x-2)\cdots(x-k+1)$ possibilities.

So there are $S(n,k)$ ways to choose a partition of size $k$, then $x(x-1)(x-2)\cdots(x-k+1)$ possible choices of which function you pick from among those yielding that partition. Thus $S(n,k)x(x-1)(x-2)\cdots(x-k+1)$ is the number of functions that take $k$ values.

Each such function takes has a number of values in its range that is either $1$ or $2$ or $\cdots\cdots$ or $n$. So the number of functions is $$ \sum_{k=1}^n S(n,k)x(x-1)(x-2)\cdots(x-k+1). $$ But the number of functions is also $x^n$. Therefore those numbers are equal.

This assumes $n$ and $x$ are non-negative integers, and that is less general than the statement that it holds for $n$ and non-negative integer and $x$ real. The latter statement must be true because the expression on both sides of the "$=$" is a polynomial in $x$, and a polynomial in one variable is determined by its value at infinitely many points.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.