|
| |
|
|
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).
|
|
3
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| A007290 supplies the last term (highest "permutation entropy"). A000292 yields average of "permutation entropy": 1/n * sum(k=1..n, (c(k)-k)^2 ).
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)]. - Max Alekseyev, Jan 28 2012
|
|
|
FORMULA
| For n>=4, a(n) = 1 + binomial(n+1,3) = 1 + A000330(n) - A000292(n).
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 on elements 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 on elements 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).
|
|
|
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, A000292.
Sequence in context: A011954 A026275 A152597 * A018774 A102608 A018259
Adjacent sequences: A126969 A126970 A126971 * A126973 A126974 A126975
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Jeff Boscole (jazzerciser(AT)hotmail.com), Mar 20 2007
|
|
|
EXTENSIONS
| Formula corrected by Joel Brewster Lewis, Aug 18 2009.
Terms corrected, more terms, and clarified definition, Joerg Arndt, Apr 22 2011.
|
| |
|
|
