A269042 Number of permutations of [2n] avoiding the pattern 12...n.

0, 0, 1, 132, 15767, 2190688, 370531683, 77182248916, 19835792076675, 6266271456118776, 2413632612087046844, 1120958514818713738544, 619918692943471064695593, 403190647991638511052901232, 304867528413299672718870216538, 265248225675908889875489731636920

Offset

0,4

Links

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

Formula

a(n) = (2n)! - A269021(n).

a(n) = A214015(2n,n-1) for n>0.

a(n) ~ (2*n)!. - Vaclav Kotesovec, Mar 26 2016

Example

a(2) = 1: 4321.
a(3) = 132: 165432, 216543, 261543, 265143, 265413, 265431, 316542, ..., 653412, 653421, 654132, 654213, 654231, 654312, 654321.

Maple

h:= proc(l) (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(
      l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n))(nops(l))
    end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
                 add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
a:= n-> `if`(n=0, 0, g(2*n, n-1, [])):
seq(a(n), n=0..15);

Mathematica

h[l_] := Function[n, Total[l]!/Product[Product[1+l[[i]]-j+Sum[If[l[[k]] >= j, 1, 0], { k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]][Length[l]];
g[n_, i_, l_] := If[n == 0 || i == 1, h[Join[l, Table[1, {n}]]]^2, If[i < 1, 0, Sum[g[n - i*j, i-1, Join[l, Table[i, {j}]]], {j, 0, n/i}]]];
a[n_] := If[n == 0, 0, g[2n, n-1, {}]];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Apr 01 2017, translated from Maple *)

Crossrefs

Cf. A010050, A214015, A267532, A269021.

Sequence in context: A035818 A258394 A215546 * A216787 A239817 A175410

Adjacent sequences: A269039 A269040 A269041 * A269043 A269044 A269045

Keyword

nonn

Author

Alois P. Heinz, Feb 18 2016

Status

approved