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

Author

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

Keywords

• nonn
• easy
• changed

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

Examples

			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).
		

Links

• 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).

Crossrefs

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

Programs

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 *)

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<M. F. Hasler, Jan 29 2012 */

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

Extensions

Formula corrected by Joel B. 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