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.

1, 1, 2, 4, 11, 21, 36, 57, 85, 121, 166, 221, 287, 365, 456, 561, 681, 817, 970, 1141, 1331, 1541, 1772, 2025, 2301, 2601, 2926, 3277, 3655, 4061, 4496, 4961, 5457, 5985, 6546, 7141, 7771, 8437, 9140, 9881, 10661, 11481, 12342, 13245, 14191, 15181, 16216

Offset

0,3

Comments

Also, number of distinct values taken by sum(k=1..n, k * pi(k) ). - Joerg Arndt, Apr 22 2011

For n>=4, sum(k=1..n, k * pi(k) ) takes every value in the interval [A000292(n),A000330(n)] (cf. A175929). - Max Alekseyev, Jan 28 2012

Links

Table of n, a(n) for n=0..46.

J. Sack and H. Úlfarsson, Refined inversion statistics on permutations, arXiv preprint arXiv:1106.1995 [math.CO], 2011-2012.

Zhi-Wei Sun, On permutations of {1, ..., n} and related topics, arXiv:1811.10503 [math.CO], 2018.

Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Formula

For n>=4, a(n) = 1 + binomial(n+1,3) = 1 + A000330(n) - A000292(n) = 1 + A000292(n-1).

G.f.: -(x^7-4*x^6+6*x^5-4*x^4+2*x^3-4*x^2+3*x-1)/(x-1)^4. - M. F. Hasler, Jan 12 2012

Example

For 24 permutations of {1,2,3,4}, the set of sum(k=1..n, (pi(k)-k)^2) yields {0,2,4,6,8,10,12,14,16,18,20} (11 distinct values).
For 120 permutations of {1,2,3,4,5}, the set of sum(k=1..n, (pi(k)-k)^2) yields {0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,36,38,40} (21 values).

Mathematica

LinearRecurrence[{4, -6, 4, -1}, {1, 1, 2, 4, 11, 21, 36, 57}, 50] (* Harvey P. Dale, Jun 01 2016; a(0)=1 prepended by Georg Fischer, Apr 10 2019 *)

Prog

(PARI) A126972(n)=(n!=3)+binomial(n+1, 3)  \\ - M. F. Hasler, Jan 29 2012
(PARI) /* the following inefficient code is for illustrative purpose only: */ A126972(n)={my(u=0, v=vector(n, i, i), t); sum(k=1, n!, !bittest(u, t=norml2(numtoperm(n, k)-v)) & u+=1<<t) } /* M. F. Hasler, Jan 29 2012 */

Crossrefs

Cf. A007290 (largest permutation entropy), A000292 (average permutation entropy), A135298, A175929.

Sequence in context: A026275 A152597 A320679 * A295947 A018774 A102608

Adjacent sequences: A126969 A126970 A126971 * A126973 A126974 A126975

Keyword

nonn,easy

Author

Jeff Boscole (jazzerciser(AT)hotmail.com), Mar 20 2007

Extensions

Formula corrected by Joel Brewster Lewis, Aug 18 2009.

Terms corrected, more terms added, and definition clarified by Joerg Arndt, Apr 22 2011.

a(0)=1 prepended by Alois P. Heinz, Jan 22 2019

Status

approved