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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A175929 Triangle T(n,v) read by rows: the number of permutations of [n] with "entropy" equal to 2*v. 3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

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

REFERENCES

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

LINKS

Alois P. Heinz, Rows n = 1..14, flattened

FindStat - Combinatorial Statistic Finder, The rank of the permutation inside the alternating sign matrix lattice.

EXAMPLE

The triangle starts in row n=1 and column v=0 as follows:

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;

...

MAPLE

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=1..7);  # Alois P. Heinz, Aug 28 2014

CROSSREFS

Sequence in context: A046069 A320042 A055651 * A079627 A061398 A080232

Adjacent sequences:  A175926 A175927 A175928 * A175930 A175931 A175932

KEYWORD

nonn,tabf

AUTHOR

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

EXTENSIONS

Corrected row length term - R. J. Mathar, Oct 23 2010

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 May 23 19:07 EDT 2019. Contains 323528 sequences. (Running on oeis4.)