A061547 Number of 132 and 213-avoiding derangements of {1,2,...,n}.

1, 0, 1, 2, 6, 10, 26, 42, 106, 170, 426, 682, 1706, 2730, 6826, 10922, 27306, 43690, 109226, 174762, 436906, 699050, 1747626, 2796202, 6990506, 11184810, 27962026, 44739242, 111848106, 178956970, 447392426, 715827882, 1789569706, 2863311530, 7158278826

Offset: 0

Author

Emeric Deutsch, May 16 2001

Keywords

• nonn
• easy

Comments

Or, number of permutations with no fixed points avoiding 213 and 132.

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

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

Inverse binomial transform of A094705 (0, 1, 4, 15). - Paul Curtz, Jun 15 2008

Equals row sums of triangle A177993. - Gary W. Adamson, May 16 2010

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

a(n+1) <= A218553(n) is also the Moore lower bound on the order of a (5,n)-cage. - Jason Kimberley, Oct 31 2011

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

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

Examples

			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.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• F. Al-Kharousi, R. Kehinde and A. Umar, Combinatorial results for certain semigroups of partial isometries of a finite chain, The Australasian Journal of Combinatorics, Volume 58 (3) (2014), 363-375.
• J. Brillhart and P. Morton, A case study in mathematical research: the Golay-Rudin-Shapiro sequence, Amer. Math. Monthly, 103 (1996) 854-869 (contains the sequence of the odd-subscripted terms and that of the even-subscripted terms).
• Emeric Deutsch, Derangements That Don't Rise Too Fast: 10902, Amer. Math. Monthly, Vol. 110, No. 7 (2003), pp. 639-640.
• K. Dilcher and K. B. Stolarsky, Stern polynomials and double-limit continued fractions, Acta Arithmetica 140 (2009), 119-134
• R. Kehinde and A. Umar, On the semigroup of partial isometries of a finite chain, arXiv:1101.0049 [math.GR], 2010.
• T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002
• Index entries for linear recurrences with constant coefficients, signature (1,4,-4).

Crossrefs

Cf. A000166, A020988, A020989, A068018.

Cf. A177993. - Gary W. Adamson, May 16 2010

Cf. A183158, A183159. - Abdullahi Umar, Dec 28 2010

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

Programs

Magma

[(3/8)*2^n +(1/24)*(-2)^n - 2/3: n in [1..35]]; // Vincenzo Librandi, Aug 13 2011

Maple

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

Mathematica

f[n_] := (9*2^(n-3) - (-2)^(n-3) - 2)/3; Array[f, 32] (* Robert G. Wilson v, Aug 13 2011 *)

PARI

a(n)=(3/8)*2^n+(1/24)*(-2)^n-2/3 \\ Charles R Greathouse IV, Sep 24 2015

Formula

a(n) = (3/8)*2^n + (1/24)*(-2)^n - 2/3 for n>=1.

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

G.f: (5*z^3-3*z^2-z+1)/((z-1)*(4*z^2-1)).

a(n) = A020989((n-2)/2) for n=2, 4, 6, ... and A020988((n-3)/2) for n=3, 5, 7, ... .

a(n+1)-2*a(n) = A078008 signed. Differences: doubled A000302. - Paul Curtz, Jun 15 2008

a(2i+1) = 2*Sum_{j=0..i-1} 4^j = string "2"^i read in base 4.

a(2i+2) = 4^i + 2*Sum_{j=0..i-1} 4^j = string "1"*"2"^i read in base 4.

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

a(2*n-1) = A176965(2*n), a(2*n) = A176965(2*n-1) for n>0. - Yosu Yurramendi, Dec 23 2016

a(2*n-1) = A020988(k-1), a(2*n)= A020989(n-1) for n>0. - Yosu Yurramendi, Jan 03 2017

a(n+2) = 2*A086893(n), n > 0. - Yosu Yurramendi, Mar 07 2017

E.g.f.: (15 - 8*cosh(x) + 5*cosh(2*x) - 8*sinh(x) + 4*sinh(2*x))/12. - Stefano Spezia, Apr 07 2022

Extensions

a(0)=1 prepended by Alois P. Heinz, Jan 27 2022