A126972 -id:A126972 - cp's OEIS frontend

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

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

A135298 a(n) = the total number of permutations (m(1),m(2),m(3)...m(j)) of (1,2,3,...,j) where n = 1m(1) + 2m(2) + 3m(3) + ...+jm(j), where j is over all positive integers.

Original entry on oeis.org

1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 1, 3, 1, 4, 2, 2, 2, 4, 1, 3, 1, 0, 0, 0, 0, 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, 25, 20, 22, 30, 38

Offset: 0

Leroy Quet, Dec 04 2007

Does every integer greater than some positive integer N have at least one such representation?

a(n) > 0 for n > 34, a(n) > 1 for n > 56. - Alois P. Heinz, Aug 28 2014

			21 has a(21)=3 such representations: 21 = 1*4 + 2*3 + 3*1 + 4*2 = 1*4 + 2*2 + 3*3 + 4*1 = 1*3 + 2*4 + 3*2 + 4*1.
Not all representations of an integer n need to necessarily have the same j. For example, 91 = 1*1 + 2*2 + 3*3 + 4*4 + 5*5 + 6*6 (j=6). And 91 also equals 1*7 + 2*4 + 3*5 + 4*3 + 5*6 + 6*2 + 7*1 (j=7).
1 = 1*1;
4 = 1*2+2*1;
5 = 1*1+2*2;
10 = 1*3+2*2+3*1;
11 = 1*2+2*3+3*1;
11 = 1*3+2*1+3*2;
13 = 1*1+2*3+3*2;
13 = 1*2+2*1+3*3;
14 = 1*1+2*2+3*3;
20 = 1*4+2*3+3*2+4*1;
21 = 1*3+2*4+3*2+4*1;
21 = 1*4+2*2+3*3+4*1;
21 = 1*4+2*3+3*1+4*2;
22 = 1*3+2*4+3*1+4*2;
23 = 1*2+2*4+3*3+4*1;
23 = 1*3+2*2+3*4+4*1;
23 = 1*4+2*1+3*3+4*2;
23 = 1*4+2*2+3*1+4*3;
24 = 1*2+2*3+3*4+4*1;
24 = 1*4+2*1+3*2+4*3;
25 = 1*2+2*4+3*1+4*3;
25 = 1*3+2*1+3*4+4*2;
26 = 1*1+2*4+3*3+4*2;
26 = 1*3+2*2+3*1+4*4;
27 = 1*1+2*3+3*4+4*2;
27 = 1*1+2*4+3*2+4*3;
27 = 1*2+2*3+3*1+4*4;
27 = 1*3+2*1+3*2+4*4;
28 = 1*2+2*1+3*4+4*3;
29 = 1*1+2*2+3*4+4*3;
29 = 1*1+2*3+3*2+4*4;
29 = 1*2+2*1+3*3+4*4;
30 = 1*1+2*2+3*3+4*4;

Alois P. Heinz, Table of n, a(n) for n = 0..1770
FindStat - Combinatorial Statistic Finder, The rank of the permutation inside the alternating sign matrix lattice
J. Sack and H. Úlfarsson, Refined inversion statistics on permutations, arXiv preprint arXiv:1106.1995 [math.CO], 2011-2012.

Cf. A000292, A126972, A175929.

A135298rec := proc(j,n,notm) local a,m ; a := 0 ; if n = 0 then if max( seq(e,e=notm) ) >= j then RETURN(0) ; else RETURN(1) ; fi ; end: for m from 1 do if n-j*m < 0 then break ; elif not m in notm then a := a+A135298rec(j+1,n-j*m,[op(notm),m] ) ; fi ; od: RETURN(a) ; end: A135298 := proc(n) A135298rec(1,n,[]) ; end: for n from 1 to 140 do printf("%d, ",A135298(n)) ; od: # R. J. Mathar, Jan 30 2008
# second Maple program:
n:= 8 : # gives binomial(n+3, 3) terms
with(combinat):
(p-> seq(coeff(p, x, j), j=0..binomial(n+3, 3)-1))
(add(add(x^add(i*l[i], i=1..h), l=permute(h)), h=0..n));
# Alois P. Heinz, Aug 29 2014

n = 8; (* gives binomial(n+3, 3)-1 terms *) Function[p, Table[ Coefficient[p, x, j], {j, 1, Binomial[n+3, 3]-1}]] @ Sum[x^(l.Range[h]), {h, 1, n}, {l, Permutations @ Range[h]}] (* Jean-François Alcover, Jul 22 2017, after Alois P. Heinz *)

More terms from R. J. Mathar, Jan 30 2008

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

A375623 Maximum value of F(p) = Sum (|i-j| - |p(i)-p(j)|)^2 where the sum is over all 1 <= i < j <= n, for all permutations p in the symmetric group S_n.

Original entry on oeis.org

0, 0, 0, 2, 12, 30, 72, 132, 240, 380, 600, 870, 1260, 1722, 2532, 3080

Offset: 0

W. Edwin Clark, Aug 21 2024

The function F was defined by Dan Asimov on the Mailing list Math-Fun on Aug. 18, 2024. It can be considered as a sort of entropy of a permutation p like the function Sum_{k=1..n} (p(k)-k)^2 in A126972.

The terms for even n seem to agree with A047928.

Cf. A047928, A126972, A375625.

F := proc(S) local i, j, M;
M := 0;
for j from 1 to nops(S) do
    for i from 1 to j-1 do
      M := M + (abs(i - j) - abs(S[i] - S[j]))^2
    od:
od: M end:
a := proc(n) local P, m, u, mm;
P := combinat:-permute(n);
m := 0;
for u in P do
   mm := F(u);
   if mm > m then m := mm fi;
od: m end:

a375623(n) = my(m=0); forperm(n, p, m=max(m, sum(i=1,n, sum(j=1,i-1,(abs(i-j)-abs(p[i]-p[j]))^2)))); m \\ Hugo Pfoertner, Aug 22 2024

a(11)-a(13) from Hugo Pfoertner, Aug 23 2024
a(14) from Markus Sigg, Aug 25 2024
a(15) from Hugo Pfoertner, Sep 04 2024

A375625 Number of distinct values taken by F(p) = Sum (|i-j| - |p(i)-p(j)|)^2 where the sum is over all 1 <= i < j <= n, for all permutations p in the symmetric group S_n.

Original entry on oeis.org

1, 1, 1, 2, 4, 10, 17, 51, 55, 160, 140, 389, 300, 795, 566, 1290

Offset: 0

W. Edwin Clark, Aug 21 2024

The function F was defined by Dan Asimov on the Mailing list Math-Fun on Aug. 18, 2024.

Cf. A126972, A375623.

F:= S-> add(add((j-i-abs(S[j]-S[i]))^2, i=1..j-1), j=2..nops(S)):
a:= n-> nops({map(F, combinat[permute](n))[]}):
seq(a(n), n=0..10);

a(11)-a(13) from Hugo Pfoertner, Aug 24 2024

a(14)-a(15) from Hugo Pfoertner, Sep 04 2024

A189043 For all permutations of [1..n]: number of distinct values taken by sum(k=1..n, k^2 * pi(k) ).

Original entry on oeis.org

1, 2, 6, 23, 89, 232, 437, 747, 1191, 1806, 2631, 3709, 5087, 6816

Offset: 1

Joerg Arndt, Apr 22 2011

			The permutations of 4 elements and the respective sums are
[ 1 2 3 4 ] 100
[ 1 2 4 3 ]  93
[ 1 3 2 4 ]  95
[ 1 3 4 2 ]  81
[ 1 4 2 3 ]  83
[ 1 4 3 2 ]  76
[ 2 1 3 4 ]  97
[ 2 1 4 3 ]  90
[ 2 3 1 4 ]  87
[ 2 3 4 1 ]  66
[ 2 4 1 3 ]  75
[ 2 4 3 1 ]  61
[ 3 1 2 4 ]  89
[ 3 1 4 2 ]  75  // same as [ 2 4 1 3 ]
[ 3 2 1 4 ]  84
[ 3 2 4 1 ]  63
[ 3 4 1 2 ]  60
[ 3 4 2 1 ]  53
[ 4 1 2 3 ]  74
[ 4 1 3 2 ]  67
[ 4 2 1 3 ]  69
[ 4 2 3 1 ]  55
[ 4 3 1 2 ]  57
[ 4 3 2 1 ]  50
All values except 75 are unique, so a(4) = 4!-1 = 23.

Cf. A126972 (sum k*pi(k)).

Corrected terms (error pointed out by Alois P. Heinz), Joerg Arndt, Apr 28 2011.

a(14) from Alois P. Heinz, Apr 28 2011

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A135298 a(n) = the total number of permutations (m(1),m(2),m(3)...m(j)) of (1,2,3,...,j) where n = 1*m(1) + 2*m(2) + 3*m(3) + ...+j*m(j), where j is over all positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A375623 Maximum value of F(p) = Sum (|i-j| - |p(i)-p(j)|)^2 where the sum is over all 1 <= i < j <= n, for all permutations p in the symmetric group S_n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

PARI

Extensions

A375625 Number of distinct values taken by F(p) = Sum (|i-j| - |p(i)-p(j)|)^2 where the sum is over all 1 <= i < j <= n, for all permutations p in the symmetric group S_n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Extensions

A189043 For all permutations of [1..n]: number of distinct values taken by sum(k=1..n, k^2 * pi(k) ).

Views

Author

Keywords

Examples

Crossrefs

Extensions

A135298 a(n) = the total number of permutations (m(1),m(2),m(3)...m(j)) of (1,2,3,...,j) where n = 1m(1) + 2m(2) + 3m(3) + ...+jm(j), where j is over all positive integers.