A135298 -id:A135298 - cp's OEIS frontend

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.

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

Offset: 0

Jeff Boscole (jazzerciser(AT)hotmail.com), Mar 20 2007

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

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

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.
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A007290 (largest permutation entropy), A000292 (average permutation entropy), A135298, A175929.

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

A126972(n)=(n!=3)+binomial(n+1,3)  \\ M. F. Hasler, Jan 29 2012

/* 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<M. F. Hasler, Jan 29 2012 */

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

Formula corrected by Joel B. 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

A175929 Triangle T(n,v) read by rows: the number of permutations of [n] with "entropy" equal to 2*v.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 0, 2, 1, 1, 3, 1, 4, 2, 2, 2, 4, 1, 3, 1, 1, 4, 3, 6, 7, 6, 4, 10, 6, 10, 6, 10, 6, 10, 4, 6, 7, 6, 3, 4, 1, 1, 5, 6, 9, 16, 12, 14, 24, 20, 21, 23, 28, 24, 34, 20, 32, 42, 29, 29, 42, 32, 20, 34, 24, 28, 23, 21, 20, 24, 14, 12, 16, 9, 6, 5, 1, 1, 6, 10, 14, 29, 26, 35, 46, 55

Offset: 0

Emeric Deutsch and R. J. Mathar, Oct 22 2010

Define the "entropy" (or variance) of a permutation pi to be Sum_{i=1..n} (pi(i)-i)^2 = A006331(n) - 2*Sum_i i*pi(i), as in A126972.
This characteristic is obviously an even number, 2*v(pi).
Row n of the triangle shows the statistics (frequency distribution) of v for the n! = A000142(n) possible permutations of [n].
T(n,0)=1 arises the identity permutation where v=0.
T(n,1)=n-1 arises from the n-1 different ways of creating an entropy of 2 by swapping a pair of adjacent entries in the identity permutation.
The final 1 in each row arises from the permutation with maximal entropy, that is the permutation with integers reversed relative to the identity permutation.
Row n has 1+A000292(n-1) entries. Row sums are sum_{v=0..A000292(n-1)} T(n,v) = n!.
Removing zeros in A135298 creates a sequence which is similar in the initial terms, because contributions to A135298(n) stem from permutations of some unique [j] if n is not too large, which establishes a 1-to-1 correspondence between the term A006331(n)-2*sum_i i*pi(i) mentioned above and the defining formula in A135298.
The rows of this triangle have a geometric interpretation. Let P_n be the n-dimensional permutohedron, the Voronoi cell of the lattice A_n* (Conway-Sloane, 1993, p. 474), which is a polytope with (n+1)! vertices. Start at any vertex, and count how many vertices there are at squared-distance v from the starting vertex: this is T(n+1,v). For example, in three dimensions the permutohedron is a truncated octahedron, the squared distances from a vertex to all the vertices are (when suitably scaled) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and the numbers of vertices at these distances are 1, 3, 1, 4, 2, 2, 2, 4, 1, 3, 1, which is row 4 of the array. See Chap. 21, Section 3.F, op. cit., for further details. - N. J. A. Sloane, Oct 13 2015

			Triangle T(n,v) starts in row n=0 and column v=0 as follows:
  1;
  1;
  1, 1;
  1, 2, 0, 2, 1;
  1, 3, 1, 4, 2, 2, 2,  4, 1,  3, 1;
  1, 4, 3, 6, 7, 6, 4, 10, 6, 10, 6, 10, 6, 10, 4, 6, 7, 6, 3, 4, 1;
  ...

J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", Springer-Verlag, 3rd. ed., 1993.

Alois P. Heinz, Rows n = 0..20, flattened
FindStat - Combinatorial Statistic Finder, The rank of the permutation inside the alternating sign matrix lattice.

Row sums give A000142.

Cf. A000292, A001754, A006331, A126972, A135298.

with(combinat):
T:= n-> (p-> seq(coeff(p, x, j), j=ldegree(p)..degree(p)))
        (add(x^add(i*l[i], i=1..n), l=permute(n))):
seq(T(n), n=0..7);  # Alois P. Heinz, Aug 28 2014
# second Maple program:
b:= proc(s) option remember; (n-> `if`(n=0, 1, add(expand(
      x^((n-j)^2/2)*b(s minus {j})), j=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b({$1..n})):
seq(T(n), n=0..7);  # Alois P. Heinz, Mar 02 2024

b[s_] := b[s] = With[{n = Length[s]}, If[n == 0, 1, Sum[Expand[x^((n-j)^2/2)*b[s~Complement~{j}]], {j, s}]]];
T[n_] := CoefficientList[b[Range[n]], x];
Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Mar 22 2024, after Alois P. Heinz *)

Sum_{k>=0} k * T(n,k) = A001754(n+1). - Alois P. Heinz, Mar 02 2024

Row length term corrected by R. J. Mathar, Oct 23 2010

T(0,0)=1 prepended by Alois P. Heinz, Nov 23 2023

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI