A249583 Number of permutations p of [n] such that p(i) > p(i+1) iff i == 2 (mod 3).

1, 1, 1, 2, 5, 9, 40, 169, 477, 3194, 19241, 74601, 666160, 5216485, 25740261, 287316122, 2769073949, 16591655817, 222237912664, 2543467934449, 17929265150637, 280180369563194, 3712914075133121, 30098784753112329, 537546603651987424, 8094884285992309261

Offset

0,4

Comments

This is the (UDU)* version of 3-alternating permutations of [n], (U=Up, D=Down).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..500

J. M. Luck, On the frequencies of patterns of rises and falls, arXiv:1309.7764, 2013

Anthony Mendes and Jeffrey Remmel, Generating functions from symmetric functions, Preliminary version of book, available from Jeffrey Remmel's home page

R. P. Stanley, A survey of alternating permutations, arXiv:0912.4240, 2009

Example

a(2) = 1: 12.
a(3) = 2: 132, 231.
a(4) = 5: 1324, 1423, 2314, 2413, 3412.
a(5) = 9: 13245, 14235, 15234, 23145, 24135, 25134, 34125, 35124, 45123.
a(6) = 40: 132465, 132564, 142365, 142563, 143562, 152364, 152463, 153462, 162354, 162453, 163452, 231465, 231564, 241365, 241563, 243561, 251364, 251463, 253461, 261354, 261453, 263451, 341265, 341562, 342561, 351264, 351462, 352461, 361254, 361452, 362451, 451263, 451362, 452361, 461253, 461352, 462351, 561243, 561342, 562341.
a(7) = 169: 1324657, 1324756, 1325647, ..., 6723514, 6724513, 6734512.

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
     `if`(t=2, add(b(u-j, o+j-1, irem(t+1, 3)), j=1..u),
               add(b(u+j-1, o-j, irem(t+1, 3)), j=1..o)))
    end:
a:= n-> b(0, n, 0):
seq(a(n), n=0..35);

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, If[t == 2, Sum[b[u - j, o + j - 1, Mod[t+1, 3]], {j, 1, u}], Sum[b[u + j - 1, o - j, Mod[t+1, 3]], {j, 1, o}]]];
a[n_] := b[0, n, 0];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)

Crossrefs

Cf. A178963 (i=0), A249402 (i=1).

Sequence in context: A161137 A229551 A247550 * A109469 A334986 A185160

Adjacent sequences: A249580 A249581 A249582 * A249584 A249585 A249586

Keyword

nonn

Author

Alois P. Heinz, Nov 01 2014

Status

approved