A175929 -id:A175929 - 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

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

A367313 Triangle read by rows: T(n,k) is the number of permutations of [n] with weighted inversion index k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 3, 4, 3, 3, 2, 1, 1, 1, 1, 2, 3, 5, 5, 8, 9, 10, 10, 12, 10, 10, 9, 8, 5, 5, 3, 2, 1, 1, 1, 1, 2, 3, 5, 7, 9, 12, 16, 20, 23, 28, 31, 36, 38, 41, 43, 44, 44, 43, 41, 38, 36, 31, 28, 23, 20, 16, 12, 9, 7, 5, 3, 2, 1, 1

Offset: 0

Todd Simpson, Nov 13 2023

T(n,k) represents two statistics that can be shown to be equal:
(1) Permutations of {1,2,...,n} counted by a "weighted inversion index": for a permutation pi, the weighted inversion index is the sum of i over all pairs i,j with i < j and pi(i) > pi(j).
(2) Partitions lambda with at most n-1 parts counted by weight, where the inequality lambda(i) - lambda(i+1) <= n - i holds for 1 <= i < n (with lambda(n) = 0).
Possible values of this index range from 0 to (n-1)*n*(n+1)/6.  The permutation with the largest weighted inversion index is (n,n-1,...,2,1) and the partition with the largest weight is (n(n-1)/2,(n-1)(n-2)/2,...,3,1).
Let t_n(q) be the sum of T(n,k)q^k, for 0 <= k <= (n-1)*n*(n+1)/6.  Then t_n(q) is the product of (1 - q^(k*(n+1-k)))/(1 - q^k), for 1 <= k <= n-1.

			The permutation pi = (2,5,3,1,4) has these inversions, with the given contributions to weighted inversion index:
   (2,1), 1
   (5,3), 2
   (5,1), 2
   (5,4), 2
   (3,1), 3
The corresponding partition can be created as follows.  For each i <= 5, write the number of j > i with pi(i) > pi(j): (1,3,1,0,0).
For each i, the i-th number in this sequence is at most n-i.
Let lambda(i) be the sum of the values of the sequence starting with the i-th value: lambda = (5,4,1,0,0).
This permutation and partition are counted by T(5,10).  In the product expansion of t_5(q), they correspond to the following choice of terms:
   (1 - q^5)/(1 - q) = 1 + q + q^2 + q^3 + q^4:  choose q,
   (1 - q^8)/(1 - q^2) = 1 + q^2 + q^4 + q^6:  choose q^6,
   (1 - q^9)/(1 - q^3) = 1 + q^3 + q^6:  choose q^3,
   (1 - q^8)/(1 - q^4) = 1 + q^4:  choose 1.
Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 1, 2, 1, 1;
  1, 1, 2, 3, 3, 4, 3, 3,  2,  1,  1;
  1, 1, 2, 3, 5, 5, 8, 9, 10, 10, 12, 10, 10, 9, 8, 5, 5, 3, 2, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..25, flattened

Row sums give A000142.
Row n contains A050407(n+2) terms.
T(n+1,n) gives A000041(n).
Cf. A000165, A001754, A175929.

From Alois P. Heinz, Nov 25 2023: (Start)
Sum_{k=0..A050407(n+2)-1} k * T(n,k) = A001754(n+1).
Sum_{k=0..A050407(2n+3)-1} (-1)^k * T(2n+1,k) = A000165(n). (End)

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

PARI

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 = 1m(1) + 2m(2) + 3m(3) + ...+jm(j), where j is over all positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A367313 Triangle read by rows: T(n,k) is the number of permutations of [n] with weighted inversion index k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

PARI

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

A367313 Triangle read by rows: T(n,k) is the number of permutations of [n] with weighted inversion index k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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.