login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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=1..45.

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. = (1 - 2*x + 2*x^2 + 3*x^3 - 6*x^4 + 4*x^5 - x^6)/(1 - x)^4. Thus, linear recurrent sequence with coefficients (4,-6,4,-1). \\ - 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, 2, 4, 11, 21, 36, 57}, 50] (* Harvey P. Dale, Jun 01 2016 *)

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: A278446 A026275 A152597 * A018774 A102608 A290439

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.

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 18 18:46 EST 2017. Contains 294894 sequences.