A136128 Number of components in all permutations of [1,2,...,n].

1, 3, 10, 40, 192, 1092, 7248, 55296, 478080, 4625280, 49524480, 581368320, 7422589440, 102372076800, 1516402944000, 24004657152000, 404347023360000, 7220327288832000, 136227009945600000, 2707657158721536000, 56546150835879936000, 1237826569587277824000

Offset

1,2

References

Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 262 (#14).

Links

Alois P. Heinz, Table of n, a(n) for n = 1..450

Yujia Kang, Thomas Selig, Guanyi Yang, Yanting Zhang, and Haoyue Zhu, On friendship and cyclic parking functions, arXiv:2310.06560 [math.CO], 2023. See p. 13.

Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 5.

Formula

a(n) = A003149(n) - n!.

a(n) = A059371(n) + n! (n>=2).

a(n) = Sum_{k=1..n} k*A059438(n,k).

a(n) = Sum_{i=0..n-1} i!*(n-i)!.

a(n) = (n+1)!*(1 + Sum_{j=1..n-1} 2^j/(j+1))/2^n.

Rec. rel.: a(n) = (n+1)*a(n-1)/2 + (n-1)!*(n+1)/2; a(1)=1.

G.f.: f(f-1), where f(x) = Sum_{j>=0} j!*x^j.

a(n) = (n + 1)!*Re(-LerchPhi(2, 1, n + 1)). - Peter Luschny, Jan 04 2018

D-finite with recurrence: 2*a(n) +(-3*n+1)*a(n-1) +(n^2-3*n+4)*a(n-2) +(n-1)*(n-2)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

a(n) = 2 * Sum_{k=0..floor((n+1)/2)} (4^k-1) * |Stirling1(n+1,2*k)| * Bernoulli(2*k). - Seiichi Manyama, Oct 05 2022

E.g.f.: x/((2-x)*(1-x)) - 2*log(1-x)/((2-x)^2). - Vladimir Kruchinin, Nov 16 2022

Example

a(3) = 10 because the permutations of [1,2,3], with components separated by /, are 1/2/3, 1/32, 21/3, 231, 312 and 321.

Maple

seq(add(factorial(i)*factorial(n-i), i=0..n-1), n=1..20);
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n,
      (a(n-1)+(n-1)!)*(n+1)/2)
    end:
seq(a(n), n=1..23);  # Alois P. Heinz, Jun 13 2019

Mathematica

nn=20; p=Sum[n!x^n, {n, 0, nn}]; Drop[CoefficientList[Series[p(p-1), {x, 0, nn}], x], 1] (* Geoffrey Critzer, Apr 20 2012 *)
Table[(n + 1)! Re[-LerchPhi[2, 1, n + 1]], {n, 1, 20}]  (* Peter Luschny, Jan 04 2018 *)

Prog

(PARI) a(n) = 2*sum(k=0, (n+1)\2, (4^k-1)*abs(stirling(n+1, 2*k, 1))*bernfrac(2*k)); \\ Seiichi Manyama, Oct 05 2022

Crossrefs

Cf. A003149, A059371, A059438.

Sequence in context: A003703 A242651 A231531 * A089902 A093133 A030817

Adjacent sequences: A136125 A136126 A136127 * A136129 A136130 A136131

Keyword

nonn,changed

Author

Emeric Deutsch, Jan 21 2008

Status

approved