cp's OEIS Frontend

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

%I A136128 #49 Aug 09 2025 17:23:05
%S A136128 1,3,10,40,192,1092,7248,55296,478080,4625280,49524480,581368320,
%T A136128 7422589440,102372076800,1516402944000,24004657152000,404347023360000,
%U A136128 7220327288832000,136227009945600000,2707657158721536000,56546150835879936000,1237826569587277824000
%N A136128 Number of components in all permutations of [1,2,...,n].
%D A136128 Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 262 (#14).
%H A136128 Alois P. Heinz, <a href="/A136128/b136128.txt">Table of n, a(n) for n = 1..450</a>
%H A136128 Yujia Kang, Thomas Selig, Guanyi Yang, Yanting Zhang, and Haoyue Zhu, <a href="https://arxiv.org/abs/2310.06560">On friendship and cyclic parking functions</a>, arXiv:2310.06560 [math.CO], 2023-2024. See p. 13.
%H A136128 Jun Yan, <a href="https://arxiv.org/abs/2404.07958">Results on pattern avoidance in parking functions</a>, arXiv:2404.07958 [math.CO], 2024. See p. 5.
%F A136128 a(n) = A003149(n) - n!.
%F A136128 a(n) = A059371(n) + n! (n>=2).
%F A136128 a(n) = Sum_{k=1..n} k*A059438(n,k).
%F A136128 a(n) = Sum_{i=0..n-1} i!*(n-i)!.
%F A136128 a(n) = (n+1)!*(1 + Sum_{j=1..n-1} 2^j/(j+1))/2^n.
%F A136128 a(n) = (n+1)*a(n-1)/2 + (n-1)!*(n+1)/2, a(1)=1.
%F A136128 G.f.: f(f-1), where f(x) = Sum_{j>=0} j!*x^j.
%F A136128 a(n) = (n + 1)!*Re(-LerchPhi(2, 1, n + 1)). - _Peter Luschny_, Jan 04 2018
%F A136128 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
%F A136128 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
%F A136128 E.g.f.: x/((2-x)*(1-x)) - 2*log(1-x)/((2-x)^2). - _Vladimir Kruchinin_, Nov 16 2022
%e A136128 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.
%p A136128 seq(add(factorial(i)*factorial(n-i),i=0..n-1),n=1..20);
%p A136128 # second Maple program:
%p A136128 a:= proc(n) option remember; `if`(n<2, n,
%p A136128       (a(n-1)+(n-1)!)*(n+1)/2)
%p A136128     end:
%p A136128 seq(a(n), n=1..23);  # _Alois P. Heinz_, Jun 13 2019
%t A136128 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 *)
%t A136128 Table[(n + 1)! Re[-LerchPhi[2, 1, n + 1]], {n, 1, 20}]  (* _Peter Luschny_, Jan 04 2018 *)
%o A136128 (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
%o A136128 (PARI) a(n) = my(A = 1, B = 1); for(k=1, n, B *= k; A = (n-k+1)*A + B); A-B \\ _Mikhail Kurkov_, Aug 09 2025
%o A136128 (Python)
%o A136128 def aList(n) -> list[int]:
%o A136128     f, al, A = 1, 1, [1]
%o A136128     for i in range(2, n + 1):
%o A136128         f, al = f * i, (al + f) * (i + 1) >> 1
%o A136128         A.append(al)
%o A136128     return A
%o A136128 print(aList(22))  # _Peter Luschny_, Aug 09 2025
%Y A136128 Cf. A003149, A059371, A059438.
%K A136128 nonn
%O A136128 1,2
%A A136128 _Emeric Deutsch_, Jan 21 2008