A184181 Number of permutations of {1,2,...,n} whose shortest block is of length 1. A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 5412367 has 4 blocks: 5, 4, 123, and 67. Its shortest block has length 1.

0, 1, 1, 5, 22, 117, 713, 5026, 40285, 362799, 3628584, 39916243, 479000017, 6227016356, 87178277811, 1307674327687, 20922789759890, 355687427686481, 6402373704361521, 121645100404228662, 2432902008160575953, 51090942171652731287, 1124000727777401441884

Offset

0,4

Comments

a(n) = A184180(n,1).

a(n) = n! - A180564(n).

Links

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

Formula

a(n) = Sum_{m=1..n} binomial(n-1, m-1)*(d(m) + d(m-1)) - Sum_{m=1..floor(n/2)} binomial(n-m-1, m-1)*(d(m) + d(m-1)), where d(j) = A000166(j) are the derangement numbers.

Example

a(3)=5 because 123 is the only permutation of {1,2,3} with no block of length 1.
a(4)=22 because 1234 and 3412 are the only permutations of {1,2,3,4} with no blocks of length 1.

Maple

d[0] := 1: for n to 40 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow; sum(binomial(n-1, m-1)*(d[m]+d[m-1]), m = 1 .. n)-(sum(binomial(n-m-1, m-1)*(d[m]+d[m-1]), m = 1 .. floor((1/2)*n))) end proc: seq(a(n), n = 1 .. 22);

Mathematica

a[n_] := If[n == 0, 0, n! - With[{d = Subfactorial}, Sum[Binomial[n-j-1, j-1]*(d[j] + d[j-1]), {j, 1, Floor[n/2]}]]];
Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Sep 19 2024 *)

Crossrefs

Cf. A184180, A180564, A000166.

Sequence in context: A127620 A122951 A331836 * A020003 A276750 A131460

Adjacent sequences: A184178 A184179 A184180 * A184182 A184183 A184184

Keyword

nonn,changed

Author

Emeric Deutsch, Feb 13 2011

Status

approved