Constructive Expectation Question Six balls numbered $1$ through $6$ are in a bin. You randomly draw them out one at a time, without replacement, and put them into boxes numbered $1$ through $6$ (one ball in each box). For each ball whose number matches the number of the box you put it in, you win that number of dollars. (For example, if ball $\#2$ ends up in box $2$, you win $\$2$ for that ball.)
What are your expected total winnings (in dollars)?

Would the answer be $(6)(21/6)=21$? Because the expected winning for each roll is $(1/6)(1+2+3+4+5+6)$ and there are $6$ rolls
Thanks!
 A: For $i=1$ to $6$, let $X_i=1$ if Ball $i$ lands in Box $i$, and let $X_i=0$ otherwise. Then our total winnings $Y$ are given by$Y=X_1+2X_2+3X_3+\cdots +6X_6$. By the linearity of expectation we have 
$$E(Y)=E(X_1)+2E(X_2)+3E(X_3)+\cdots +6E(X_6).$$
Note that $E(X_i)=\Pr(X_i=1)=\frac{1}{6}$. Now calculate. We get $E(Y)=\frac{21}{6}$.
A: Permit me to contribute a proof using generating functions
which is quite pretty.

We have by inspection that the desired expectation is
$$\frac{1}{n!}
\left.\frac{\partial}{\partial x} \prod_{q=1}^n (u+x^q)
\right|_{x=1, u^p=!p.}$$
Starting with the derivative we get
$$\frac{1}{n!}
\left.\prod_{q=1}^n (u+x^q)\sum_{q=1}^n \frac{qx^{q-1}}{u+x^q}
\right|_{x=1, u^p=!p.}$$
Now do the assignment, putting $x=1$, to obtain
$$\frac{1}{n!}
\left.\prod_{q=1}^n (u+1)\sum_{q=1}^n \frac{q}{u+1}
\right|_{u^p=!p.}$$
This simplifies to
$$\frac{1}{n!}\left.(u+1)^{n-1}\right|_{u^p=!p} \sum_{q=1}^n q
= \frac{1}{n!}\frac{1}{2}n(n+1)
\times \left.(u+1)^{n-1}\right|_{u^p=!p}.$$ 
The polynomial in $u$ gives
$$\left.\sum_{p=0}^{n-1} {n-1\choose p} u^p\right|_{u^p=!p}
= \sum_{p=0}^{n-1} {n-1\choose p} \times !p.$$ 
Note that $$\sum_{p=0}^{n-1} {n-1\choose n-1-p} \times !p
= (n-1)!$$
by definition (classify the permutations on $[1,n-1]$ according to the
number of fixed points).
Collecting everything we get
$$\frac{1}{n!}\frac{1}{2}n(n+1) (n-1)!
= \frac{1}{2}(n+1).$$
Addendum.

We could have evaluated the sum directly, as follows.

The species  of decompositions of  permutations into cycles  marked by
the number of cycles is
$$\mathfrak{P}(\mathcal{U}\mathfrak{C}(\mathcal{Z}))$$
which gives the (exponential) generating function
$$G(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$
It follows that the generating function of derangements is given by
$$H(z) = \exp\left(-z + \log\frac{1}{1-z}\right)
= \exp(-z) \frac{1}{1-z}.$$
Substituting this into the sum yields
$$\sum_{p=0}^{n-1} {n-1\choose p} 
p! [z^p] \exp(-z) \frac{1}{1-z}
\\ = (n-1)! [z^{n-1}] \exp(z) \exp(-z) \frac{1}{1-z}
\\ = (n-1)! [z^{n-1}] \frac{1}{1-z}
= (n-1)!$$
as claimed.

The following Maple code can serve to verify the formula
$$\frac{1}{2}(n+1).$$

with(combinat);

v :=
proc(n)
    option remember;
    local p, payout, q, s;

    s := 0;

    p := firstperm(n);
    while type(p, list) do
        payout := 0;

        for q to n do
            if p[q] = q then
                payout := payout + q;
            fi;
        od;

        s := s + payout;

        p := nextperm(p);
    od;


    s/n!
end;

This is the output.

> seq(v(n), n=1..8);
                           1, 3/2, 2, 5/2, 3, 7/2, 4, 9/2

Remark. Another short proof goes as follows. As we are averaging over all $n!$ permutations we know that the element $q$ is in position $q$ exactly $(n-1)!$ times. Hence the average payout is
$$\frac{1}{n!} \times \sum_{q=1}^n q (n-1)!
= \frac{1}{n}\frac{1}{2}n(n+1) = \frac{1}{2}(n+1).$$
