A375838 Number of rooted chains starting with the cycle (1)(2)(3)...(n) in the permutation poset of [n].

1, 1, 2, 9, 83, 1270, 28799, 906899, 37866842, 2024422837, 134850653405, 10950546880152, 1064840930492393, 122158078221727119, 16325324374155336370, 2514183676808883419043, 442023695390488997377405, 87989953715757624724243004, 19688099473681895327628896249, 4919839221134662388853128069571, 1365091729320293490230304687026514

Offset: 0

Author

Rajesh Kumar Mohapatra, Subhashree Sahoo, and Ranjan Kumar Dhani, Sep 10 2024

Keywords

• nonn

Examples

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

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..260

Crossrefs

Row sums of A375837.

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

Cf. A385521.

Programs

Maple

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

Mathematica

T[n_, k_] := T[n, k] = If[k < 0 || k > n, 0, If[(n == 0 && k == 0) || k == 1, 1, Sum[If[r >= 0, Abs[StirlingS1[n, r]]*T[r, k - 1], 0], {r, k - 1, n - 1}]]]; Table[Sum[T[n, k], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Jul 01 2025, after A375837 *)

Formula

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

a(n) = (A375836(n)+1)/2.

Conjecture: a(n) = R(n,0) where R(n,k) = (k+1) * (Sum_{i=0..n-1} R(n-1,i) + Sum_{j=0..k-1} R(n-1,j)) for 0 <= k < n, R(n,n) = 1. - Mikhail Kurkov, Jun 21 2025

a(n) ~ c * n!^2 / (2^n * log(2)^n * n^(1-log(2)/3)), where c = A385521 = 1.59585433050036621247006569740016516964502505848324064247941890934119103861277... - Vaclav Kotesovec, Jul 01 2025

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