This site is supported by donations to The OEIS Foundation.

 Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing. Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A061547 Number of 132 and 213-avoiding derangements of {1,2,...,n}. 29

%I

%S 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

%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

%H Vincenzo Librandi, <a href="/A061547/b061547.txt">Table of n, a(n) for n = 1..1000</a>

%H F. Al-Kharousi, R. Kehinde, 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, 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, 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...</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.

%F a(n) = 4*a(n-2) + 2, a(1)=0, a(2)=1.

%F G.f: z^2*(1+z)/((1-z)(1-4*z^2).

%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

%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->(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 Floretion Algebra Multiplication Program, FAMP Code: jesseq[ + 'i - .5'j + i' - .5j' + 'kk' + 'ik' + 'jk' + 'ki' + 'kj']

%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. A020988, A020989.

%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 1,3

%A _Emeric Deutsch_, May 16 2001

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 7 22:29 EST 2019. Contains 329850 sequences. (Running on oeis4.)