|
%I #127 Jun 12 2023 17:13:03
%S 1,0,1,2,6,10,26,42,106,170,426,682,1706,2730,6826,10922,27306,43690,
%T 109226,174762,436906,699050,1747626,2796202,6990506,11184810,
%U 27962026,44739242,111848106,178956970,447392426,715827882,1789569706,2863311530,7158278826
%N Number of 132 and 213-avoiding derangements of {1,2,...,n}.
%C Or, number of permutations with no fixed points avoiding 213 and 132.
%C Number of derangements of {1,2,...,n} having ascending runs consisting of consecutive integers. Example: a(4)=6 because we have 234/1, 34/12, 34/2/1, 4/123, 4/3/12, 4/3/2/1, the ascending runs being as indicated. - _Emeric Deutsch_, Dec 08 2004
%C Let c be twice the sequence A002450 interlaced with itself (from the second term), i.e., c = 2*(0, 1, 1, 5, 5, 21, 21, 85, 85, 341, 341, ...). Let d be powers of 4 interlaced with the zero sequence: d = (1, 0, 4, 0, 16, 0, 64, 0, 256, 0, ...). Then a(n+1) = c(n) + d(n). - _Creighton Dement_, May 09 2005
%C Inverse binomial transform of A094705 (0, 1, 4, 15). - _Paul Curtz_, Jun 15 2008
%C Equals row sums of triangle A177993. - _Gary W. Adamson_, May 16 2010
%C a(n-1) is also the number of order preserving partial isometries (of an n-chain) of fix 1 (fix of alpha equals the number of fixed points of alpha). - _Abdullahi Umar_, Dec 28 2010
%C a(n+1) <= A218553(n) is also the Moore lower bound on the order of a (5,n)-cage. - _Jason Kimberley_, Oct 31 2011
%C For n > 0, a(n) is the location of the n-th new number to make a first appearance in A087230. E.g., the 17th number to make its first appearance in A087230 is 18 and this occurs at A087230(43690) and a(17)=43690. - _K D Pegrume_, Jan 26 2022
%C Position in A002487 of 2 adjacent terms of A000045. E.g., 3/5 at 10, 5/8 at 26, 8/13 at 42, ... - _Ed Pegg Jr_, Dec 27 2022
%H Vincenzo Librandi, <a href="/A061547/b061547.txt">Table of n, a(n) for n = 0..1000</a>
%H F. Al-Kharousi, R. Kehinde and A. Umar, <a href="http://ajc.maths.uq.edu.au/pdf/58/ajc_v58_p365.pdf">Combinatorial results for certain semigroups of partial isometries of a finite chain</a>, The Australasian Journal of Combinatorics, Volume 58 (3) (2014), 363-375.
%H J. Brillhart and P. Morton, <a href="http://www.maa.org/programs/maa-awards/writing-awards/a-case-study-in-mathematical-research-the-golay-rudin-shapiro-sequence">A case study in mathematical research: the Golay-Rudin-Shapiro sequence</a>, Amer. Math. Monthly, 103 (1996) 854-869 (contains the sequence of the odd-subscripted terms and that of the even-subscripted terms).
%H Emeric Deutsch, <a href="http://www.jstor.org/stable/3647760">Derangements That Don't Rise Too Fast: 10902</a>, Amer. Math. Monthly, Vol. 110, No. 7 (2003), pp. 639-640.
%H K. Dilcher and K. B. Stolarsky, <a href="https://doi.org/10.4064/aa140-2-2">Stern polynomials and double-limit continued fractions</a>, Acta Arithmetica 140 (2009), 119-134
%H R. Kehinde and A. Umar, <a href="http://arxiv.org/abs/1101.0049">On the semigroup of partial isometries of a finite chain</a>, arXiv:1101.0049 [math.GR], 2010.
%H T. Mansour and A. Robertson, <a href="http://arXiv.org/abs/math.CO/0204005">Refined restricted permutations avoiding subsets of patterns of length three</a>, arXiv:math/0204005 [math.CO], 2002
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,4,-4).
%F a(n) = (3/8)*2^n + (1/24)*(-2)^n - 2/3 for n>=1.
%F a(n) = 4*a(n-2) + 2, a(0)=1, a(1)=0, a(2)=1.
%F G.f: (5*z^3-3*z^2-z+1)/((z-1)*(4*z^2-1)).
%F a(n) = A020989((n-2)/2) for n=2, 4, 6, ... and A020988((n-3)/2) for n=3, 5, 7, ... .
%F a(n+1)-2*a(n) = A078008 signed. Differences: doubled A000302. - _Paul Curtz_, Jun 15 2008
%F a(2i+1) = 2*Sum_{j=0..i-1} 4^j = string "2"^i read in base 4.
%F a(2i+2) = 4^i + 2*Sum_{j=0..i-1} 4^j = string "1"*"2"^i read in base 4.
%F a(n+2) = Sum_{k=0..n} A144464(n,k)^2 = Sum_{k=0..n} A152716(n,k). - _Philippe Deléham_ and _Michel Marcus_, Feb 26 2014
%F a(2*n-1) = A176965(2*n), a(2*n) = A176965(2*n-1) for n>0. - _Yosu Yurramendi_, Dec 23 2016
%F a(2*n-1) = A020988(k-1), a(2*n)= A020989(n-1) for n>0. - _Yosu Yurramendi_, Jan 03 2017
%F a(n+2) = 2*A086893(n), n > 0. - _Yosu Yurramendi_, Mar 07 2017
%F E.g.f.: (15 - 8*cosh(x) + 5*cosh(2*x) - 8*sinh(x) + 4*sinh(2*x))/12. - _Stefano Spezia_, Apr 07 2022
%e a(4)=6 because the only 132 and 213-avoiding permutations of {1,2,3,4} without fixed points are: 2341, 3412, 3421, 4123, 4312 and 4321.
%p A061547:=n->ceil(abs((3/8)*2^n +(1/24)*(-2)^n - 2/3)); seq(A061547(n), n=1..30); # _Wesley Ivan Hurt_, Apr 03 2014
%t f[n_] := (9*2^(n-3) - (-2)^(n-3) - 2)/3; Array[f, 32] (* _Robert G. Wilson v_, Aug 13 2011 *)
%o (Magma) [(3/8)*2^n +(1/24)*(-2)^n - 2/3: n in [1..35]]; // _Vincenzo Librandi_, Aug 13 2011
%o (PARI) a(n)=(3/8)*2^n+(1/24)*(-2)^n-2/3 \\ _Charles R Greathouse IV_, Sep 24 2015
%Y Cf. A000166, A020988, A020989, A068018.
%Y Cf. A177993. - _Gary W. Adamson_, May 16 2010
%Y Cf. A183158, A183159. - _Abdullahi Umar_, Dec 28 2010
%Y Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), this sequence (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - _Jason Kimberley_, Oct 31 2011
%K nonn,easy
%O 0,4
%A _Emeric Deutsch_, May 16 2001
%E a(0)=1 prepended by _Alois P. Heinz_, Jan 27 2022
|
