A276975 Number of permutations of [n] such that the minimal distance between elements of the same cycle equals one, a(1)=1 by convention.

1, 1, 4, 19, 103, 651, 4702, 38413, 350559, 3539511, 39196758, 472612883, 6165080443, 86526834271, 1300282224846, 20832761552453, 354515666646827, 6386139146435035, 121406489336263622, 2429193186525638435, 51030147426536745655, 1122952442325988152627

Offset

1,3

Links

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

Per Alexandersson et al., d-regular partitions and permutations, MathOverflow, 2014

Example

a(2) = 1: (1,2).
a(3) = 4: (1,2,3), (1,3,2), (1)(2,3), (1,2)(3).

Maple

b:= proc(n, i, l) option remember; `if`(n=0, mul(j!, j=l),
      (m-> add(`if`(i=j, 0, b(n-1, j, `if`(j>m, [l[], 0],
        subsop(j=l[j]+1, l)))), j=1..m+1))(nops(l)))
    end:
a:= n-> `if`(n=1, 1, n!-b(n, 0, [])):
seq(a(n), n=1..15);

Mathematica

b[n_, i_, l_] := b[n, i, l] = If[n == 0, Product[j!, {j, l}], Function[m, Sum[If[i == j, 0, b[n - 1, j, If[j > m, Append[l, 0], ReplacePart[l, j -> l[[j]] + 1]]]], {j, 1, m + 1}]][Length[l]]];
a[n_] := If[n == 1, 1, n! - b[n, 0, {}]];
Array[a, 15] (* Jean-François Alcover, Oct 28 2020, after Maple code *)

Crossrefs

Column k=1 of A276974.

Cf. A002467, A180191, A277032.

Sequence in context: A078940 A110531 A367808 * A178302 A292098 A186997

Adjacent sequences: A276972 A276973 A276974 * A276976 A276977 A276978

Keyword

nonn

Author

Alois P. Heinz, Sep 23 2016

Status

approved