OFFSET
0,4
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Feb 13 2011
STATUS
approved