This site is supported by donations to The OEIS Foundation.

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

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.