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
Keywords
Examples
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.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..450
Programs
-
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 *)
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.
Comments