login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A061547 Number of 132 and 213-avoiding derangements of {1,2,...,n}. 28
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

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

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

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

R. Kehinde, 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..., arXiv:math/0204005 [math.CO], 2002

Index entries for linear recurrences with constant coefficients, signature (1,4,-4).

FORMULA

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

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

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

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

EXAMPLE

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.

MAPLE

A061547:=n->(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 *)

PROG

Floretion Algebra Multiplication Program, FAMP Code: jesseq[ + 'i - .5'j + i' - .5j' + 'kk' + 'ik' + 'jk' + 'ki' + 'kj']

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

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

CROSSREFS

Cf. A020988, A020989.

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

Sequence in context: A057434 A217381 A162581 * A218791 A190034 A119459

Adjacent sequences:  A061544 A061545 A061546 * A061548 A061549 A061550

KEYWORD

nonn,easy

AUTHOR

Emeric Deutsch, May 16 2001

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified January 20 10:23 EST 2018. Contains 297960 sequences.