prove that $\sum_{k=0}^{n}S(n,k)(x)_k=x^n$

95 Views Asked by At

my attempt:

assume there are a teacher decided to buy $n$ different types of chocolate and present it as a reward to the students who will give a correct answer to one of the questions. The number of students in the department in which the teacher studies is $x$.

assume that :at least one student will give a correct answer

so maybe there are one student who will give a correct answer ,or maybe 2 student who will give a correct answer,and so on

if there exactly 2 student who will give a correct answer ,they must do a partition of $n$ chocolate to theme ,(note that :The number of chocolates does not necessary have to be divided equally among the students.),and the ways of distributing these $n $ chocolate is as follow: in this case($2$ student) we will put two identical bins and distribute the $n$ chocolate into the two bin and then the student $A$ must be chose one bin, so the other bin for the student $B$.so in this case all possible is that $S(n,2)(x)_2$

for more explain let's take $3$ student.so we will distribute this $n$ chocolate into $3$ bins , and then the first student must choose one bin ,and the second student must choose one bin .so all possible is that $S(n,3)(x)_3$

now maybe you are wondered why we must the distribute chocolate at bins, the answer is that : $(x)_3$ is the number of ways to choose $3$ student .but the order is important , and if we distribute to them chocolate directly the distribution can be repeat because the order of student important , and our student are not identical ,

and that $S(n,0)(x)_0+S(n,1)(1)_0+S(n,2)(x)_2 +...+S(n,n)(x)_n=\sum_{k=0}^{n}S(n,k)(x)_k$ is a result of the method used

now we can do that by another ways :each chocolate can be obtained by $x$ student , so after multiple principle there are $x^n$ possible

so finally;$\sum_{k=0}^{n}S(n,k)(x)_k=x^n$

is my attempt true?

1

There are 1 best solutions below

1
On BEST ANSWER

Your proof is a good combinatorial proof, and it shows that

$$ \sum_{k=0}^n S(n,k)x_{(k)}=x^n\tag{$*$} $$

holds whenever $x$ can be interpreted as "the number of students." That is, it only proves $(*)$ when $x$ is a natural number.

Fortunately, there is a routine way to take such results and extend them to prove that $(*)$ holds as an equation of polynomials. Considering the polynomial $-x^n+\sum_{k=0}^n S(n,k)x_{(k)}$ in $\mathbb Z[x]$, your proof shows every natural number is a root, but the only polynomial with infinitely many roots in $\Bbb Z[x]$ is identically $0$.

The extra power of proving $(*)$ as an equation of polynomials is that it allows you substitute other values for $x$. Say with $x=-1$, you get $$ \sum_{k=0}^n S(n,k)(-1)^kk!=(-1)^n \tag{$**$} $$ To me, it is surprising that your story about students and chocolates implies $(**)$.