TITLE: Weighted sum of arrangements
QUESTION [2 upvotes]: I was pondering this problem (not a homework):

What are the coefficients {a_i} that cancel all powers except the biggest one ?
The values for n=1,2,3 are easy to find, Wolfram-alpha helped find the next ones.
Is there a formula to generate them?

REPLY [3 votes]: We have that
$$\sum_{k=1}^n {n\brace k} x^{\underline{k}} =
\sum_{k=1}^n {n\brace k} \frac{x!}{(x-k)!} = x^n.$$
with the Stirling numbers of the second kind.
To see this combinatorially write it as
$$\sum_{k=1}^n {x\choose k} {n\brace k} k! = x^n.$$
Let $x$ be the number of elements of some set. Then $x^n$ counts the
number of $n$-tuples with components chosen from this set. This is the
RHS. The LHS  classifies the tuples according to the number of different
values that  appear, say there are $k$ of these. Then we must first
choose these values which  gives ${x\choose k}.$ Next we partition the
$n$ slots into $k$  non-empty disjoint subsets where the slots in a
subset all hold the same value  from the $k$ that we have chosen. We can
assign the latter to the subsets  in $k!$ different ways. This gives the
factor ${n\brace k}\times k!$ and  hence the LHS. (We have shown that it
holds  for positive integers $x.$ With both sides being polynomials in
$x$ it  holds for all $x$ where we define ${x\choose k} =
x^{\underline{k}}/k!.$)
{"set_name": "stack_exchange", "score": 2, "question_id": 4023456}