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,5

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.

Links

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

Wikipedia, Permutation

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

Example

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

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 *)

Crossrefs

Column k=1 of A186754.

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

Sequence in context: A271055 A212329 A338487 * A015547 A067376 A098305

Adjacent sequences: A349785 A349786 A349787 * A349789 A349790 A349791

Keyword

nonn

Author

Alois P. Heinz, Nov 30 2021

Status

approved