login
A375836
Number of chains in the poset of permutations of [n].
3
1, 1, 3, 17, 165, 2539, 57597, 1813797, 75733683, 4048845673, 269701306809, 21901093760303, 2129681860984785, 244316156443454237, 32650648748310672739, 5028367353617766838085, 884047390780977994754809, 175979907431515249448486007, 39376198947363790655257792497
OFFSET
0,3
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.
Sequence in context: A175607 A052143 A268758 * A069856 A214346 A015083
KEYWORD
nonn
AUTHOR
STATUS
approved