A349788 Number of permutations of [n] having exactly one increasing cycle.

0, 1, 1, 1, 5, 36, 234, 1597, 12459, 111451, 1116277, 12298958, 147655760, 1919465237, 26870436345, 403044639709, 6448695657957, 109628096021612, 1973308547820586, 37492874766408001, 749857477972731979, 15747006284752049759, 346434131946498886045

Offset: 0

Author

Alois P. Heinz, Nov 30 2021

Keywords

• nonn

Comments

Cycle (b(1), b(2), ...) is said to be increasing if, when written with its smallest element in the first position, it satisfies b(1) < b(2) < ... .

Exponential convolution of A000587 with A002627.

Examples

			a(4) = 5: (1)(243), (143)(2), (142)(3), (132)(4), (1234).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..450
• Wikipedia, Permutation

Crossrefs

Column k=1 of A186754.

Cf. A000587, A002627, A131719, A186755, A186758.

Programs

Maple

b:= proc(n) option remember; series(`if`(n=0, 1, add((x+
     (j-1)!-1)*binomial(n-1, j-1)*b(n-j), j=1..n)), x, 2)
    end:
a:= n-> coeff(b(n), x, 1):
seq(a(n), n=0..23);

Mathematica

b[n_] := b[n] = Series[If[n == 0, 1, Sum[(x+
     (j-1)!-1)*Binomial[n-1, j-1]*b[n-j], {j, 1, n}]], {x, 0, 2}];
a[n_] := Coefficient[b[n], x, 1];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Apr 15 2022, after Alois P. Heinz *)

Formula

E.g.f.: exp(1-exp(x))*(exp(x)-1)/(1-x).

a(n) = A186758(n) - A186755(n).

a(n) = Sum_{j=0..n} binomial(n,j)*A000587(j)*A002627(n-j).

a(n) mod 2 = A131719(n).

a(n) ~ (exp(1) - 1) * exp(1 - exp(1)) * n!. - Vaclav Kotesovec, Dec 05 2021