cp's OEIS Frontend

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.

%I A184181 #16 Sep 19 2024 04:51:34
%S A184181 0,1,1,5,22,117,713,5026,40285,362799,3628584,39916243,479000017,
%T A184181 6227016356,87178277811,1307674327687,20922789759890,355687427686481,
%U A184181 6402373704361521,121645100404228662,2432902008160575953,51090942171652731287,1124000727777401441884
%N 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.
%C A184181 a(n) = A184180(n,1).
%C A184181 a(n) = n! - A180564(n).
%H A184181 Alois P. Heinz, <a href="/A184181/b184181.txt">Table of n, a(n) for n = 0..450</a>
%F A184181 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.
%e A184181 a(3)=5 because 123 is the only permutation of {1,2,3} with no block of length 1.
%e A184181 a(4)=22 because 1234 and 3412 are the only permutations of {1,2,3,4} with no blocks of length 1.
%p A184181 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);
%t A184181 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]}]]];
%t A184181 Table[a[n], {n, 0, 22}] (* _Jean-François Alcover_, Sep 19 2024 *)
%Y A184181 Cf. A184180, A180564, A000166.
%K A184181 nonn
%O A184181 0,4
%A A184181 _Emeric Deutsch_, Feb 13 2011