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

Alois P. Heinz, Table of n, a(n) for n = 0..261

Formula

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

a(n) = n! + Sum_{k=1..n-1} abs(Stirling1(n,k))*a(k). - Rajesh Kumar Mohapatra, Jul 01 2025

a(n) = 2 * A375838(n) - 1. - Rajesh Kumar Mohapatra, Jul 01 2025

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.

Maple

a:= proc(n) option remember;
      n!+add(abs(Stirling1(n, k))*a(k), k=1..n-1)
    end:
seq(a(n), n=0..18);  # Alois P. Heinz, Jul 01 2025

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]

Prog

(Python)
from math import factorial as f
from sympy.functions.combinatorial.numbers import stirling as s
from functools import cache
@cache
def a(n): return f(n) + sum(abs(s(n, k, kind=1)) * a(k) for k in range(1, n)) # David Radcliffe, Jul 01 2025

Crossrefs

Row sums of A375835.

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

Sequence in context: A052143 A268758 A387067 * A069856 A214346 A015083

Adjacent sequences: A375833 A375834 A375835 * A375837 A375838 A375839

Keyword

nonn

Author

Rajesh Kumar Mohapatra, Aug 31 2024

Status

approved