login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
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 (list; graph; refs; listen; history; text; internal format)
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
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.
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. A007920 (largest permutation entropy), A000292 (average permutation entropy), A135298, A175929.
Sequence in context: A026275 A152597 A320679 * A295947 A018774 A102608
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:02 EDT 2024. Contains 371235 sequences. (Running on oeis4.)