A375836 Number of chains in the poset of permutations of [n].

1, 1, 3, 17, 165, 2539, 57597, 1813797, 75733683, 4048845673, 269701306809, 21901093760303, 2129681860984785, 244316156443454237, 32650648748310672739, 5028367353617766838085, 884047390780977994754809, 175979907431515249448486007, 39376198947363790655257792497

Offset

0,3

Links

Table of n, a(n) for n=0..18.

Formula

a(n) = Sum_{k=0..n} A375835(n,k).

Example

Consider the set S = {1, 2, 3}. The a(3) = 6 + 8 + 3 = 17 in the poset of permutations of {1,2,3}:
|{(1)(2)(3), (1)(23), (2)(13), (3)(12), (123), (132)}| = 6;
|{(1)(2)(3) < (1)(23), (1)(2)(3) < (2)(13), (1)(2)(3) < (3)(12), (1)(2)(3) < (123),(1)(2)(3) < (132), (1)(23) < (123), (2)(13) < (132), (3)(12) < (123)}|=8;
|{(1)(2)(3) < (1)(23) < (123), (1)(2)(3) < (2)(13) < (132), (1)(2)(3) < (3)(12) < (123)}| = 3.

Mathematica

b[n_, k_, t_] := b[n, k, t] = If[k < 0, 0, If[Union@{n, k} == {0}, 1, Sum[If[k == 1, 1, b[v, k - 1, 1]]*Abs[StirlingS1[n, v]], {v, k, n - t}]]];
a[n_] := Sum[b[n, k, 0], {k, 0, n}]; a /@ Range[0, 20]

Crossrefs

Row sums of A375835.

Cf. A048994, A331955, A330804, A331956, A331957.

Sequence in context: A175607 A052143 A268758 * A069856 A214346 A015083

Adjacent sequences: A375833 A375834 A375835 * A375837 A375838 A375839

Keyword

nonn

Author

Rajesh Kumar Mohapatra, Aug 31 2024

Status

approved