|
| |
|
|
A061547
|
|
Number of 132- and 213-avoiding derangements of {1,2,...,n}.
|
|
22
| |
|
|
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; 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 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 interlace 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 (creighton.k.dement(AT)uni-oldenburg.de), May 09 2005
Inverse binomial transform of A094705 (0, 1, 4, 15). - Paul Curtz (bpcrtz(AT)free.fr), Jun 15 2008
Equals row sums of triangle A177993 [From 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) is also the Moore lower bound on the order of a (5,n)-cage. - Jason Kimberley, Oct 31 2011
|
|
|
REFERENCES
| 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).
E. Deutsch, Problem 10902, Amer. Math. Monthly, 110 (2003), 639.
|
|
|
LINKS
| Vincenzo Librandi, Table of n, a(n) for n = 0..1000
T. Mansour and A. Robertson, Refined restricted permutations....
R. Kehinde, A. Umar, On the semigroup of partial isometries of a finite chain, arXiv:1101.0049
Index to sequences with 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.
|
|
|
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.
|
|
|
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
|
|
|
CROSSREFS
| Cf. A020988, A020989.
A177993 [From 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: A055237 A057434 A162581 * A190034 A119459 A192616
Adjacent sequences: A061544 A061545 A061546 * A061548 A061549 A061550
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), May 16 2001
|
| |
|
|
