A186758 Number of permutations of {1,2,...,n} with no increasing cycles of length >=2. A 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)<b(3)<... .

1, 1, 1, 2, 10, 59, 363, 2491, 19661, 176536, 1767540, 19460671, 233578585, 3036411429, 42507793209, 637606959466, 10201702712738, 173429224591607, 3121728583605435, 59312852905363623, 1186257030934984061, 24911396924131631880, 548050726738352726108

Offset

0,4

Comments

a(n) = A186757(n,0).

Links

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

Formula

E.g.f.: exp(1+z-exp(z))/(1-z).

a(n) ~ n! * exp(2-exp(1)). - Vaclav Kotesovec, Oct 05 2013

a(n) = Sum_{k=0..1} A186754(n,k). - Alois P. Heinz, Dec 02 2021

Example

a(3)=2 because we have (1)(2)(3) and (132).
a(4)=10 because we have (1)(2)(34), (1)(243), (132)(4), (142)(3), (143)(2), and the 5 cyclic permutations of {1,2,3,4} different from (1234).

Maple

g := exp(1+z-exp(z))/(1-z): gser := series(g, z = 0, 25): seq(factorial(n)*coeff(gser, z, n), n = 0 .. 22);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(a(n-j)*
      binomial(n-1, j-1)*((j-1)!-`if`(j=1, 0, 1)), j=1..n))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Apr 13 2017

Mathematica

CoefficientList[Series[E^(1+x-E^x)/(1-x), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 05 2013 *)

Crossrefs

Cf. A186754, A186755, A186756, A186757, A186759, A186760.

Sequence in context: A370273 A309955 A340987 * A372415 A372476 A262910

Adjacent sequences: A186755 A186756 A186757 * A186759 A186760 A186761

Keyword

nonn

Author

Emeric Deutsch, Feb 26 2011

Status

approved