cp's OEIS Frontend

A165961 Number of circular permutations of length n without 3-sequences.

%I A165961 #39 Nov 15 2019 23:38:03
%S A165961 1,5,20,102,627,4461,36155,328849,3317272,36757822,443846693,
%T A165961 5800991345,81593004021,1228906816941,19733699436636,336554404751966,
%U A165961 6075478765948135,115734570482611885,2320148441078578447,48827637296350480457,1076313671861962141616
%N A165961 Number of circular permutations of length n without 3-sequences.
%C A165961 Circular permutations are permutations whose indices are from the ring of integers modulo n. 3-sequences are of the form i,i+1,i+2. Sequence gives number of permutations of [n] starting with 1 and having no 3-sequences.
%C A165961 a(n) is also the number of permutations of length n-1 without consecutive fixed points (cf. A180187). - _David Scambler_, Mar 27 2011
%D A165961 Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012. - From _N. J. A. Sloane_, Sep 15 2012 [broken link]
%H A165961 Michael De Vlieger, <a href="/A165961/b165961.txt">Table of n, a(n) for n = 3..450</a>
%H A165961 Wayne M. Dymacek and Isaac Lambert, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Dymacek/dymacek5.html">Permutations Avoiding Runs of i, i+1, i+2 or i, i-1, i-2</a>, Journal of Integer Sequences, Vol. 14 (2011), Article 11.1.6.
%H A165961 Kyle Parsons, <a href="http://hdl.handle.net/11021/23093">Arithmetic progressions in permutations</a>, Thesis, 2011.
%F A165961 Let b(n) be the sequence A002628. Then for n > 5, this sequence satisfies a(n) = b(n-1) - b(n-3) + a(n-3).
%F A165961 a(n) = Sum_{k=0..n/2} binomial(n-k,k)*d(n-k-1), where d(j)=A000166(j) are the derangement numbers. - _Emeric Deutsch_, Sep 07 2010
%e A165961 For n=4 the a(4)=5 solutions are (0,1,3,2), (0,2,1,3), (0,2,3,1), (0,3,1,2) and (0,3,2,1).
%p A165961 d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: sum(binomial(n-k, k)*d[n-k-1], k = 0 .. floor((1/2)*n)) end proc: seq(a(n), n = 3 .. 23); # _Emeric Deutsch_, Sep 07 2010
%t A165961 a[n_] := Sum[Binomial[n-k, k] Subfactorial[n-k-1], {k, 0, n/2}];
%t A165961 a /@ Range[3, 21] (* _Jean-François Alcover_, Oct 29 2019 *)
%Y A165961 Cf. A002628, A165960, A165962.
%Y A165961 Cf. A000166, A180186, - _Emeric Deutsch_, Sep 07 2010
%Y A165961 A column of A216718. - _N. J. A. Sloane_, Sep 15 2012
%K A165961 nonn
%O A165961 3,2
%A A165961 _Isaac Lambert_, Oct 01 2009
%E A165961 More terms from _Emeric Deutsch_, Sep 07 2010
%E A165961 Edited by _N. J. A. Sloane_, Apr 04 2011