[seqfan] Re: GF or recursion requested

[Max Alekseyev]

On Thu, Sep 20, 2012 at 12:32 PM, Meeussen Wouter (bkarnd)
<wouter.meeussen at vandemoortele.com> wrote:
> dear all,
>
> take a set [y1,y2,...,yn] of integers, and look at them as vertical increments on a x-y grid, defining the path
> 0,y1, y1+y2, y1+y2+y3,... , Sum(i); yi
> then it makes sense to differentiate several paths generated by permuting the yi on the basis of 'total weight below the path';
> for the example above, that would be n*y1+ (n-1)*y2 +...+  2*y_sub_(n-1) + yn.
> Now I was wondering how many distinct weights there are for the set [y1,y2,...,yn] going through all permutations of  n.
>
> I found 1, 2, 4, 11, 21, 36, 57, 85, 121, 166 known as
> A126972   Number of distinct values taken by the entropy for permutations of [1..n], where the entropy of a permutation pi is sum(k=1..n, (pi(k)-k)^2).   formula   Binomial[n+1,3] + If[  n=!=3, 1, 0]
>
> Is it evident that these counts match?

Yes. Notice that

sum(k=1..n, (pi(k)-k)^2)
= sum(k=1..n, pi(k)^2) - 2*sum(k=1..n, pi(k)*k) + sum(k=1..n, k^2)

The first and third sums here are constants both equal 1^2 + 2^2 + ...
+ n^2, and the second sum is twice the weight and only it is
responsible for the number of distinct values.

Regards,
Max