A002538 -id:A002538 - cp's OEIS frontend

A370832 Triangle read by rows: T(n,k) gives the number of parking functions of size n with k lucky cars. 0 <= k <= n.

1, 0, 1, 0, 1, 2, 0, 2, 8, 6, 0, 6, 37, 58, 24, 0, 24, 204, 504, 444, 120, 0, 120, 1318, 4553, 6388, 3708, 720, 0, 720, 9792, 44176, 87296, 81136, 33984, 5040, 0, 5040, 82332, 463860, 1203921, 1582236, 1064124, 341136, 40320, 0, 40320, 773280, 5270480, 17164320, 29724000, 28328480, 14602320, 3733920, 362880

Offset: 0

Peter Kagey, Mar 02 2024

A car is called "lucky" if it gets its preferred parking spot.

Closely related to A220884.

			Table begins:
n\k|  0     1     2      3       4       5       6      7     8
---+-------------------------------------------------------------
 0 |  1
 1 |  0     1
 2 |  0     1     2
 3 |  0     2     8      6
 4 |  0     6    37     58      24
 5 |  0    24   204    504     444     120
 6 |  0   120  1318   4553    6388    3708     720
 7 |  0   720  9792  44176   87296   81136   33984   5040
 8 |  0  5040 82332 463860 1203921 1582236 1064124 341136 40320
      ...

Alois P. Heinz, Rows n = 0..140, flattened
Irfan Durmić, Alex Han, Pamela E. Harris, Rodrigo Ribeiro, and Mei Yin, Probabilistic Parking Functions, arXiv:2211.00536 [math.CO], 2022.
FindStat, St000135: The number of lucky cars of the parking function.

Cf. A002538, A067948, A220884.
Row sums give A000272(n+1).
Cf. A000142 (main diagonal and column k=1 shifted).

b:= proc(n) option remember; `if`(n=0, 1,
      expand(x*mul((n+1-k)+k*x, k=2..n)))
    end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n,k), k=0..n), n=0..10);  # Alois P. Heinz, Jun 26 2024

row[n_] := (x (x - 1)^n Pochhammer[(n + x) / (x - 1), n]) / (n + x);
Table[CoefficientList[Series[row[n], {x, 0, n}], x], {n, 0, 8}] // Flatten
(* Peter Luschny, Jun 27 2024 *)

T(n, n) = n!.
T(n, 1) = (n-1)!.
Sum_{k=1..n} T(n, k) = (n+1)^(n-1).
T(n+1, n) = A002538(n).
G.f. for row n>0: x * Product_{j=2..n} (n + 1 + j*(x-1)).
T(n, k) = [x^k] (x*(x - 1)^n*Pochhammer((n + x) / (x - 1), n)) / (n + x). - Peter Luschny, Jun 27 2024

Edited by Alois P. Heinz, Jun 26 2024

A121579 Triangle read by rows: T(n,k) is the number of deco polyominoes of height n having along the lower contour exactly k reentrant corners, i.e., a vertical step that is followed by a horizontal step (n>=1, k>=0).

Original entry on oeis.org

1, 2, 5, 1, 16, 8, 65, 52, 3, 326, 344, 50, 1957, 2473, 595, 15, 13700, 19676, 6524, 420, 109601, 173472, 71862, 7840, 105, 986410, 1686912, 823836, 127232, 4410, 9864101, 17981193, 9976686, 1975750, 118125, 945, 108505112, 208769296, 128350992

Offset: 1

Emeric Deutsch, Aug 08 2006

A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.
Row n contains ceiling(n/2) terms.
Row sums are the factorials (A000142).
T(n,0) = A000522(n).
T(2n+1,n) = (2n-1)!! = A001147(n) (the double factorials).
Sum_{k=0..n} k*T(n,k) = A002538(n-2) for n >= 3.

			T(2,0)=2 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, having no reentrant corners along the lower contour.
Triangle starts:
    1;
    2;
    5,   1;
   16,   8;
   65,  52,   3;
  326, 344,  50;

E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.

Cf. A000142, A000522, A001147, A002538.

Q[1]:=1: for n from 2 to 13 do Q[n]:=sort(expand(subs(x=t,Q[n-1])+(n-1)*x*subs(x=1,Q[n-1]))) od: for n from 1 to 13 do P[n]:=subs(x=1,Q[n]) od: for n from 1 to 13 do seq(coeff(P[n],t,j),j=0..ceil(n/2)-1) od; # yields sequence in triangular form

The row generating polynomials are P(n,t) = Q(n,t,1), where Q(1,t,x) = 1 and Q(n,t,x) = Q(n-1,t,t) + (n-1)xQ(n-1,t,1) for n >= 2.

A321853 a(n) is the sum of the fill times of all 1-dimensional fountains given by the permutations in S_n.

Original entry on oeis.org

0, 1, 10, 86, 756, 7092, 71856, 787824, 9329760, 118956960, 1627067520, 23786386560, 370371536640, 6122231942400, 107109431654400, 1977781262284800, 38445562145894400, 784885857270681600, 16792523049093120000, 375755553108633600000, 8777531590107033600000

Offset: 1

Peter Kagey, Nov 19 2018

nonn

A 1-dimensional fountain given by a permutation is a 1 X n grid of squares with a source on the left and a sink on the right, where the permutation gives the height of each square of the fountain. Starting from the source, the water fills up each square of the fountain at the rate of one unit volume per unit time. The water immediately flows to all adjacent regions of lower height. The water flows out immediately upon reaching the sink.
The expected amount of time to fill a fountain given by a random permutation in S_n is a(n)/n!.
a(n) <= (n!-1)*binomial(n,2).

			For the permutation 15234, the well takes a total of seven seconds to reach the sink: it takes 4 seconds to fill to 55234, then it takes 1 second to fill to 55334, then it takes 2 seconds to fill to 55444, where it reaches the sink.
For n = 3 the a(3) = 10 sum occurs from summing over the times in the following table:
+-------------+------+-------------+
| permutation | time | final state |
+-------------+------+-------------+
|     123     |   3  |     333     |
|     132     |   2  |     332     |
|     213     |   3  |     333     |
|     231     |   1  |     331     |
|     312     |   1  |     322     |
|     321     |   0  |     321     |
+-------------+------+-------------+

Peter Kagey, Table of n, a(n) for n = 1..400
Chalkdust Magazine, Well, well, well.... (Construction is slightly different.)

Cf. A002538.

List([1..22],n->Factorial(n)*Sum([0..n],k->(n-k)*k/(k+1))); # Muniru A Asiru, Dec 05 2018

[Factorial(n)*(&+[(n-k)*k/(k+1): k in [1..n]]): n in [1..25]]; // G. C. Greubel, Dec 04 2018

a:=n->factorial(n)*add((n-k)*k/(k+1),k=0..n): seq(a(n),n=1..22); # Muniru A Asiru, Dec 05 2018

Table[n!*Sum[(n - k)*k/(k + 1), {k, 1, n - 1}], {n, 1, 21}]

vector(25, n, n!*sum(k=0,n, (n-k)*k/(k+1))) \\ G. C. Greubel, Dec 04 2018

from sympy.abc import k, a, b
from sympy import factorial
from sympy import Sum
for n in range(1,25): print(int(factorial(n)*Sum((n-k)*k/(k+1), (k, 0, n)).doit().evalf()), end=', ') # Stefano Spezia, Dec 05 2018

[factorial(n)*sum((n-k)*k/(k+1) for k in (1..n)) for n in (1..25)] # G. C. Greubel, Dec 04 2018

a(n) = n!*Sum_{k=0..n} (n-k)*k/(k+1).
a(n) = A001804(n) - A002538(n-1) for n > 1.
E.g.f.: (x + (1-x)*log(1-x))/(1-x)^3. - G. C. Greubel, Dec 04 2018
a(n) = (n+1)!(n+2-2H(n+1))/2, where H(n) = 1+1/2+...+1/n is the n-th Harmonic number. - Jeffrey Shallit, Dec 31 2018

A367850 Total sum of the block maxima minus the block minima over all partitions of [n].

Original entry on oeis.org

0, 0, 1, 6, 33, 182, 1034, 6122, 37927, 246030, 1669941, 11844324, 87644672, 675494180, 5413500801, 45040155758, 388441330457, 3467619369538, 31998729152474, 304846692965822, 2994781617653439, 30304301968015582, 315536869771786501, 3377398077726963112

Offset: 0

Alois P. Heinz, Dec 15 2023

nonn

			a(3) = 6 = 2 + 1 + 2 + 1 + 0: 123, 12|3, 13|2, 1|23, 1|2|3.

Alois P. Heinz, Table of n, a(n) for n = 0..574
Wikipedia, Partition of a set

Cf. A000110, A002538 (the same for permutations), A002620, A120325, A124325, A278677, A368338.

b:= proc(n, m, t) option remember; `if`(n=0, [1, 0], (p->
      p+[0, p[1]*(n-t)])(b(n-1, m+1, t+1))+m*b(n-1, m, t+1))
    end:
a:= n-> b(n, 0, 1)[2]:
seq(a(n), n=0..23);
# second Maple program:
egf:= (z-2)*exp(2*z+exp(z)-1)+(2*z+1)*exp(z+exp(z)-1)+exp(exp(z)-1):
a:= n-> n!*coeff(series(egf, z, n+1), z, n):
seq(a(n), n=0..23);

E.g.f.: (z-2)*exp(2*z+exp(z)-1)+(2*z+1)*exp(z+exp(z)-1)+exp(exp(z)-1).
a(n) = A278677(n-1) - A124325(n+1) for n>=1.
a(n) = Bell(n+1)+(n+1)*Bell(n)-Bell(n+2)+Sum_{k=0..n} Stirling2(n+1,k)*(n+1-k).
a(n) = Sum_{k=0..A002620(n)} k * A368338(n,k).
a(n) mod 2 = A120325(n).

A368401 Number T(n,k) of permutations of [n] whose sum of cycle maxima minus cycle minima gives k, triangle T(n,k), n>=0, 0<=k<=A002620(n), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 1, 3, 7, 11, 2, 1, 4, 12, 28, 53, 12, 10, 1, 5, 18, 52, 135, 289, 84, 72, 58, 6, 1, 6, 25, 84, 257, 734, 1825, 524, 564, 496, 422, 60, 42, 1, 7, 33, 125, 429, 1407, 4545, 12983, 3520, 3976, 4292, 3950, 3422, 790, 486, 330, 24

Offset: 0

Alois P. Heinz, Dec 22 2023

			T(3,0) = 1: (1)(2)(3).
T(3,1) = 2: (12)(3), (1)(23).
T(3,2) = 3: (123), (132), (13)(2).
Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 2,  3;
  1, 3,  7, 11,   2;
  1, 4, 12, 28,  53,  12,   10;
  1, 5, 18, 52, 135, 289,   84,  72,  58,   6;
  1, 6, 25, 84, 257, 734, 1825, 524, 564, 496, 422, 60, 42;
  ...

Alois P. Heinz, Rows n = 0..21, flattened
Wikipedia, Permutation

Row sums give A000142.

Cf. A002538, A002620, A124327, A143946, A367955, A368338.

b:= proc(n, s) option remember; `if`(n=0, 1, (k-> `if`(n>k,
      b(n-1, s)+add(b(n-1, subs(h=h+[0, 1], s)), h=s), 0)+
      `if`(n>k+1, b(n-1, {s[], [n,1]}), 0)+add(h[2]!*expand(
      x^(h[1]-n)*b(n-1, s minus {h})), h=s))(nops(s)))
    end:
T:= (n, k)-> coeff(b(n, {}), x, k):
seq(seq(T(n, k), k=0..floor(n^2/4)), n=0..10);

Sum_{k=0..A002620(n)} k * T(n,k) = A002538(n-1) for n >= 1.

A383875 Number of pairs in the Bruhat order of type A_n.

Original entry on oeis.org

1, 3, 19, 213, 3781, 98407, 3550919

Offset: 0

Dmitry I. Ignatov, May 18 2025

The number of ordered pairs in the Bruhat poset of the Weyl group A_n (isomorphic to the symmetric group S_{n+1}).

			For n=0, the only element is 1 (identity) so a(0)=1.
For n=1 the elements are 1 (identity) and s1. The order relation consists of pairs (1, 1), (1, s1), and (s1, s1). So a(1) = 3.
For n=2 the line (Hasse) diagram is below.
       s1*s2*s1
        /   \
      s2*s1 s1*s2
       |  X  |
       s2    s1
        \   /
          1
The order relation consists of the six reflexive pairs, the eight pairs shown in the diagram as edges, and the five pairs (1, s2*s1), (1, s1*s2), (1, s1*s2*s1), (s1, s1*s2*s1), and (s2, s1*s2*s1). So a(2) = 6+8+5 = 19.

A. Bjorner and F. Brenti, Combinatorics of Coxeter Groups, Springer, 2009, 27-64.

V. V. Deodhar, On Bruhat ordering and weight-lattice ordering for a Weyl group, Indagationes Mathematicae, vol. 81, 1 (1978), 423-435.

Cf. A000142 (the order size), A002538 (edges in the cover relation), A005130 (the size of Dedekind-MacNeille completion), A384061 (antichains), A384062 (maximal antichains).

a(0)=1 prepended by Sara Billey, Jul 02 2025

cp's OEIS Frontend

A370832 Triangle read by rows: T(n,k) gives the number of parking functions of size n with k lucky cars. 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A121579 Triangle read by rows: T(n,k) is the number of deco polyominoes of height n having along the lower contour exactly k reentrant corners, i.e., a vertical step that is followed by a horizontal step (n>=1, k>=0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A321853 a(n) is the sum of the fill times of all 1-dimensional fountains given by the permutations in S_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

A367850 Total sum of the block maxima minus the block minima over all partitions of [n].

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A368401 Number T(n,k) of permutations of [n] whose sum of cycle maxima minus cycle minima gives k, triangle T(n,k), n>=0, 0<=k<=A002620(n), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A383875 Number of pairs in the Bruhat order of type A_n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions