A152876 Number of permutations of {1,2,...,n} having no consecutive triples of the form (odd, even, odd) or (even, odd, even).
1, 1, 2, 4, 16, 60, 288, 1584, 10368, 74880, 604800, 5356800, 51840000, 544320000, 6147187200, 74579097600, 962415820800, 13241346048000, 192255565824000, 2957575348224000, 47721518530560000, 811595019755520000, 14407079038894080000, 268390402745794560000
Offset: 0
Keywords
Examples
a(3) = 4 because we have 132, 213, 231 and 312.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..460
- E. Munarini and N. Z. Salvi, Binary strings without zigzags, Séminaire Lotharingien de Combinatoire, B49h (2004), 1-15.
Crossrefs
Cf. A152877.
Programs
-
Maple
ae := proc (n) options operator, arrow: 2*(sum((n^2-3*n*j+3*j^2)*binomial(n-j, j)^2/(n-j)^2, j = 0 .. floor((1/2)*n))) end proc: ao := proc (n) options operator, arrow: sum(binomial(n+1-k, k)*binomial(n-k, k)*(2*n^2+2*n-6*k*n-3*k+6*k^2)/((n+1-k)*(n-k)), k = 0 .. floor((1/2)*n)) end proc: a := proc (n) if `mod`(n, 2) = 0 then factorial((1/2)*n)^2*ae((1/2)*n) else factorial((1/2)*n-1/2)*factorial((1/2)*n+1/2)*ao((1/2)*n-1/2) end if end proc: 1, 1, seq(a(n), n = 2 .. 22); # second Maple program: b:= proc(o, u, t) option remember; `if`(u+o=0, 1, `if`(t=4, 0, o*b(o-1, u, `if`(t=3, 5, 2)))+ `if`(t=5, 0, u*b(o, u-1, `if`(t=2, 4, 3)))) end: a:= n-> b(ceil(n/2), floor(n/2), 1): seq(a(n), n=0..30); # Alois P. Heinz, Nov 11 2013 -
Mathematica
b[o_, u_, t_] := b[o, u, t] = If[u+o == 0, 1, If[t==4, 0, o*b[o-1, u, If[t==3, 5, 2]]] + If[t==5, 0, u*b[o, u-1, If[t==2, 4, 3]]]]; a[n_] := b[Ceiling[n/2], Floor[n/2], 1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 29 2015, after Alois P. Heinz *)
Formula
a(2n) = (n!)^2*Sum_{j=0..floor(n/2)} (binomial(n-j, j))^2*(2*n^2 - 6*j*n + 6*j^2)/(n-j)^2;
a(2n+1) = n!*(n+1)!*Sum_{j=1..floor(n/2)} binomial(n+1-j, j)*binomial(n-j, j)*(2*n^2 + 2*n - 6*j*n - 3*j + 6*j^2)/((n+1-j)*(n-j)).
a(n) ~ 2 * 5^(-1/4) * ((1+sqrt(5))/4)^n * n!. - Vaclav Kotesovec, Sep 03 2014
Comments