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

A198890 Irregular triangle read by rows: row n gives expansion of g.f. for descending plane partitions of order n with no special parts and weight equal to sum of the parts.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 2, 2, 2, 3, 2, 4, 3, 4, 4, 4, 5, 4, 5, 5, 4, 6, 4, 5, 5, 4, 5, 4, 4, 4, 3, 4, 2, 3, 2, 2, 2, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 2, 3, 2, 4, 3, 5, 5, 7, 6, 8, 8, 9, 10, 12, 10, 14, 12, 14, 15, 16, 15, 18, 16, 18, 18, 20, 17, 21, 18, 20, 20, 20, 18, 21, 17, 20, 18, 18, 16, 18, 15, 16, 15, 14, 12, 14, 10, 12, 10, 9, 8, 8, 6, 7, 5, 5, 3, 4, 2, 3, 2, 1, 1, 1, 0, 1

Offset: 1

N. J. A. Sloane, Oct 30 2011

			Rows 1 through 5 are
  1
  1, 0, 1
  1, 0, 1, 1, 0, 1, 1, 0, 1
  1, 0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 0, 1
  1, 0, 1, 1, 1, 2, 2, 2, 3, 2, 4, 3, 4, 4, 4, 5, 4, 5, 5, 4, 6, 4, 5, 5, 4, 5, 4, 4, 4, 3, 4, 2, 3, 2, 2, 2, 1, 1, 1, 0, 1
From _Peter Bala_, May 29 2022: (Start)
Row 3 generating polynomial:
   Permutation p    Pairs (p(i),p(j)) with p(i) > p(j)       inv_1(p)
       123                       -                              0
       132                     (3,2)                            3
       213                     (2,1)                            2
       231                 (2,1), (3,1)                         5
       312                 (3,1), (3,2)                         6
       321              (3,2), (3,1), (2,1)                     8
Hence R(3,x) = x^0 + x^2 + x^3 + x^5 + x^6 + x^8 = (1 + x^2)*(1 + x^3 + x^6) = ((1 - x^4)/(1 - x^2)) * (1 - x^9)/(1 - x^3). (End)

Peter Bala, A note on A198890
J. Striker, A direct bijection between descending plane partitions with no special parts and permutation matrices, arXiv:1002.3391 [math.CO], 2010-2012.
J. Striker, A direct bijection between descending plane partitions with no special parts and permutation matrices, Discrete Math., 311 (2011).

Row sums give A000142 (factorial numbers).

Cf. A001754, A008302, A037223, A087153.

s:=(k,q)->add(q^i,i=0..k-1);
f:=n->mul(s(i,q^i),i=1..n);
g:=n->seriestolist(series(f(n),q,1000));
for n from 1 to 10 do lprint(g(n)); od:
# alternative program
T := proc (n, k) option remember;
if n = 0 or n = 1 and k = 0 then 1
elif k > ((1/3)*n-1/3)*n*(n+1) then 0
elif k < 0 then 0
else T(n, k-n) + T(n-1, k) - T(n-1, k-n^2) fi end:
seq(print(seq(T(n, k), k = 0..(1/3)*(n-1)*n*(n+1))), n = 1..6); # Peter Bala, Jun 07 2022

From Peter Bala, May 29 2022: (Start)
T(0, 0) = 1; T(1, 0) = 1.
T(n, k) = 0 for k < 0 or k > (1/3)*(n+1)*n*(n-1).
T(n, k) = Sum_{j = 0..n-1} T(n-1, k-n*j); T(n, k) = T(n, k-n) + T(n-1, k) - T(n-1, k-n^2).
T(n,k) = T(n, (1/3)*(n+1)*n*(n-1) - k).
Sum_{k = 0..(1/3)*(n+1)*n*(n-1)} T(n, k) = n!.
Sum_{k = 0..(1/3)*(n+1)*n*(n-1)} (-1)^k*T(n, k) = A037223(n).
Sum_{k = 0..(1/3)*(n+1)*n*(n-1)} k*T(n, k) = (1/3)*n!*binomial(n-1,2) = 2*A001754(n) for n >= 1.
n-th row polynomial R(n,x) = Product_{j = 1..n} (1 - x^(j^2))/(1 - x^j).
let k be a nonnegative integer. Let p = p(1)p(2)...p(n) be a permutation of {1,2,...,n}. We define the k-th inversion number of p by inv_k(p) = Sum_{pairs (i,j), 1 <= i < j <= n, such that p(i) > p(j)} (p(i))^k. The n-th row polynomial R(n,x) equals Sum_{permutations p of {1,2,...,n} } x^(inv_1(p)). An example is given below. For the case k = 0 see A008302.
The x-adic limit of R(n,x) as n -> 00 is the g.f. of A087153. (End)

Name clarified by Ludovic Schwob, Jun 15 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)

A200978 Number of ways to arrange n books on 3 consecutive shelves leaving none of the shelves empty.

Original entry on oeis.org

6, 72, 720, 7200, 75600, 846720, 10160640, 130636800, 1796256000, 26345088000, 410983372800, 6799906713600, 118998367488000, 2196892938240000, 42682491371520000, 870722823979008000, 18611700362551296000, 416026243398205440000

Offset: 3

Dennis P. Walsh, Nov 26 2011

To derive a(n), we note that there are n! ways to arrange n books in a row and there are binomial(n-1,2) ways to place the n arranged books on 3 consecutive shelves (since binomial(n-1,2) is the number of compositions of n with 3 summands). Hence a(n) = n!*binomial(n-1,2) for n >= 3.

The number of ways to arrange n books on two nonempty bookshelves is given by A062119(n).

			a(4)=72 since there are 72 ways to arrange books b1, b2, b3, and b4 on 3 consecutive shelves s1, s2, and s3. Note that there are 24 arrangements with two books on shelf s_i (i=1,2,3) and one book on each of the other two shelves. (For instance, there are 12 ways to select and permute the two books for s1 and 2 ways to select the single books for s2 and s3.) Hence there are 3(24)=71 book arrangements.

Cf. A156992.

Maple
```
seq(n!*C(n-1,2),n=3..20);
```

nn=20;Drop[Range[0,nn]!CoefficientList[Series[(x/(1-x))^3,{x,0,nn}],x],3] (* Geoffrey Critzer, Sep 02 2013 *)

a(n) = n!*binomial(n-1,2) = n!*(n-1)*(n-2)/2, n >= 3.
a(n) = A156992(n,3).
E.g.f.: x^3/(1-x)^3.
a(n) = A001754(n)*3!. - Geoffrey Critzer, Sep 02 2013

A366155 Expansion of e.g.f. exp(x^3/(3*(1-x)^3)).

Original entry on oeis.org

1, 0, 0, 2, 24, 240, 2440, 26880, 329280, 4518080, 69148800, 1168675200, 21564188800, 430048819200, 9195964377600, 209593877292800, 5068718054400000, 129599032442880000, 3492894468128665600, 98968805893769011200, 2940975338620999680000, 91452266705317726208000, 2969664371124258103296000

Offset: 0

Enrique Navarrete, Oct 01 2023

For n>0, a(n) is the number of ways to split n people into nonempty groups, have each group sit around a circular table, and select 3 people from each table (where two seating arrangements are considered identical if each person has the same left neighbors in both of them).
2*A001754(n) is the number of ways to seat n persons around a circular table and select 3 of them if only one table is used.
A335344 is the corresponding sequence if 2 persons are selected from each table, and A000262 if only one person is selected from each table.

			a(7)=26880 since, using one table, there are 6! circular seatings and binomial(7,3) ways to select 3 persons, hence 25200 ways. Using two tables, the only way we can select 3 persons from each one is seating 4 persons in one table and 3 in the other, which can be done in 420 ways; then choosing 3 persons from each table can be done in 4 ways, for a total of 1680 ways; hence 25200 + 1680 = 26880.

Cf. A000262, A001754, A335344.

CoefficientList[Series[Exp[x^3/(3*(1-x)^3)],{x,0,22}],x]Table[n!,{n,0,22}] (* Stefano Spezia, Oct 02 2023 *)
nmax = 25; Join[{1}, Table[n!*Sum[Binomial[n-1, 3*k-1]/(3^k*k!), {k, 1, n}], {n, 1, nmax}]] (* Vaclav Kotesovec, Aug 28 2025 *)

From Vaclav Kotesovec, Aug 28 2025: (Start)
For n > 0, a(n) = n! * Sum_{k=1..n} binomial(n-1, 3*k-1) / (3^k * k!).
a(n) = 4*(n-1)*a(n-1) - 6*(n-2)*(n-1)*a(n-2) + (n-2)*(n-1)*(4*n-11)*a(n-3) - (n-4)*(n-3)*(n-2)*(n-1)*a(n-4).
a(n) ~ exp(-1/12 + 5*n^(1/4)/24 - n^(1/2)/2 + 4*n^(3/4)/3 - n) * n^(n - 1/8) / 2 * (1 - 563/(2560*n^(1/4))). (End)

A383196 Expansion of e.g.f. (1/(1 - 3*x)^(1/3) - 1)^3 / 6.

Original entry on oeis.org

0, 0, 0, 1, 24, 520, 11880, 295960, 8090880, 242280640, 7912262400, 280384720000, 10727852889600, 441104638374400, 19407654326860800, 910140650683264000, 45332366929833984000, 2390437704451084288000, 133060566042200788992000, 7797805996570952986624000

Offset: 0

Seiichi Manyama, Apr 19 2025

nonn

Column k=3 of A371080.

Cf. A001754, A035119, A143169.

a(n) = sum(k=3, n, 3^(n-k)*abs(stirling(n, k, 1))*stirling(k, 3, 2));

a(n) = Sum_{k=3..n} 3^(n-k) * |Stirling1(n,k)| * Stirling2(k,3).

a(n) ~ sqrt(Pi/2) * n^(n + 1/2) * 3^(n-1) * exp(-n) * (1 - 3/(Gamma(2/3)*n^(1/3))). - Vaclav Kotesovec, May 03 2025

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

A198890 Irregular triangle read by rows: row n gives expansion of g.f. for descending plane partitions of order n with no special parts and weight equal to sum of the parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

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

A200978 Number of ways to arrange n books on 3 consecutive shelves leaving none of the shelves empty.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A366155 Expansion of e.g.f. exp(x^3/(3*(1-x)^3)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A383196 Expansion of e.g.f. (1/(1 - 3*x)^(1/3) - 1)^3 / 6.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula