|
%I M1536 N0600 #40 Apr 20 2021 12:58:35
%S 1,1,2,5,21,106,643,4547,36696,332769,3349507,37054436,446867351,
%T 5834728509,82003113550,1234297698757,19809901558841,337707109446702,
%U 6094059760690035,116052543892621951,2325905946434516516,48937614361477154273,1078523843237914046247
%N Number of permutations of length n without 3-sequences.
%C a(n) = sum of row n of A180185. - _Emeric Deutsch_, Sep 06 2010
%D Jackson, D. M.; Reilly, J. W. Permutations with a prescribed number of p-runs. Ars Combinatoria 1 (1976), number 1, 297-305.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A002628/b002628.txt">Table of n, a(n) for n = 0..450</a>
%H D. M. Jackson and R. C. Read, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002031183">A note on permutations without runs of given length</a>, Aequationes Math. 17 (1978), no. 2-3, 336-343.
%H J. Riordan, <a href="http://projecteuclid.org/euclid.bams/1183507357">Permutations without 3-sequences</a>, Bull. Amer. Math. Soc., 51 (1945), 745-748.
%F a(n) = Sum_{k=0..floor(n/2)} binomial(n-k,k)*(d(n-k) + d(n-k-1)) for n>0, where d(j) = A000166(j) are the derangement numbers. - _Emeric Deutsch_, Sep 06 2010
%e a(4) = 21 because only 1234, 2341, and 4123 contain 3-sequences. - _Emeric Deutsch_, Sep 06 2010
%p seq(coeff(convert(series(add(m!*((t-t^3)/(1-t^3))^m,m=0..50),t,50), polynom), t,n),n=0..25); # Pab Ter, Nov 06 2005
%p d[-1]:= 0: for n from 0 to 51 do d[n] := n*d[n-1]+(-1)^n end do: a:= proc(n) add(binomial(n-k, k)*(d[n-k]+d[n-k-1]), k = 0..floor((1/2)*n)) end proc: seq(a(n), n = 0..25); # _Emeric Deutsch_, Sep 06 2010
%p # third Maple program:
%p a:= proc(n) option remember; `if`(n<5,
%p [1$2, 2, 5, 21][n+1], (n-3)*a(n-1)+(3*n-6)*a(n-2)+
%p (4*n-12)*a(n-3)+(3*n-12)*a(n-4)+(n-5)*a(n-5))
%p end:
%p seq(a(n), n=0..25); # _Alois P. Heinz_, Jul 21 2019
%t d[0] = 1; d[n_] := d[n] = n d[n - 1] + (-1)^n;
%t T[n_, k_] := If[n == 0 && k == 0, 1, If[k <= n/2, Binomial[n - k, k] d[n + 1 - k]/(n - k), 0]];
%t a[n_] := Sum[T[n, k], {k, 0, Quotient[n, 2]}];
%t a /@ Range[0, 25] (* _Jean-François Alcover_, May 23 2020 *)
%Y Column k=0 of A047921.
%Y Cf. A165960, A165961, A165962. - _Isaac Lambert_, Oct 07 2009
%Y Cf. A000166, A180185. - _Emeric Deutsch_, Sep 06 2010
%K nonn
%O 0,3
%A _N. J. A. Sloane_
%E More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 06 2005
%E a(0)=1 prepended by _Alois P. Heinz_, Jul 21 2019
|
