login
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.
3
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
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Feb 13 2011
STATUS
approved