login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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

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

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. A007920 (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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 7 19:57 EDT 2020. Contains 336279 sequences. (Running on oeis4.)