A184185 Number of permutations of {1,2,...,n} having no cycles of the form (i, i+1, i+2, ..., i+j-1) (j >= 1).

1, 0, 0, 1, 6, 34, 216, 1566, 12840, 117696, 1193760, 13280520, 160841520, 2107021680, 29689833600, 447821503920, 7199590366080, 122907276334080, 2220524598297600, 42328747652446080, 849064844592518400, 17877531486897734400, 394246607165708774400

Offset

0,5

Comments

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

Links

Seiichi Manyama, Table of n, a(n) for n = 0..450

Patxi Laborde Zubieta, Occupied corners in tree-like tableaux, arXiv preprint arXiv:1505.06098 [math.CO], 2015.

Formula

G.f.: (1-z)*F(z-z^2), where F(z) = Sum_{j>=0} j!*z^j (private communication from Vladeta Jovovic, May 26 2009).

a(n) = Sum_{i=ceiling((n-1)/2)..n} (-1)^(n-i)*i!*binomial(i+1,n-i).

G.f.: 1/Q(0), where Q(k) = 1 + x/(1-x) - x*(k+1)/(1 - x*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, Apr 19 2013

a(n) ~ n! / exp(1) * (1 - 1/n - 1/(2*n^2) - 2/(3*n^3) - 23/(24*n^4) - 151/(120*n^5) - 119/(720*n^6) + 14789/(1260*n^7) + 1223843/(13440*n^8) + ...). - Vaclav Kotesovec, Nov 30 2021

a(n) = (n+2) * a(n-1) - 2 * (n-1) * a(n-2) + (n-2) * a(n-3) for n > 2. - Seiichi Manyama, Nov 30 2021

Example

a(4)=6 because we have (13)(24), (1432), (1342), (1423), (1243), and (1324).

Maple

a := proc(n) add((-1)^(n-i)*factorial(i)*binomial(i+1, n-i), i = ceil((1/2)*n-1/2) .. n) end proc: seq(a(n), n = 0 .. 22);

Mathematica

a[n_] := Sum[(-1)^(n-i)*i!*Binomial[i+1, n-i], {i, Ceiling[(n-1)/2], n}];
Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Nov 29 2017, from Maple *)

Prog

(PARI) a(n) = sum(k=n\2, n, (-1)^(n-k)*k!*binomial(k+1, n-k)); \\ Seiichi Manyama, Nov 30 2021
(PARI) a(n) = if(n<3, 0^n, (n+2)*a(n-1)-2*(n-1)*a(n-2)+(n-2)*a(n-3)); \\ Seiichi Manyama, Nov 30 2021
(PARI) my(N=40, x='x+O('x^N)); Vec(sum(k=0, N, k!*x^k*(1-x)^(k+1))) \\ Seiichi Manyama, Nov 30 2021

Crossrefs

Cf. A013999, A184184.

Sequence in context: A218893 A266431 A063090 * A216317 A370324 A230331

Adjacent sequences: A184182 A184183 A184184 * A184186 A184187 A184188

Keyword

nonn

Author

Emeric Deutsch, Feb 16 2011 (based on communication from Vladeta Jovovic)

Status

approved