|
|
A061552
|
|
Number of 1324-avoiding permutations of length n.
|
|
14
|
|
|
1, 1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, 3824112, 25431452, 173453058, 1209639642, 8604450011, 62300851632, 458374397312, 3421888118907, 25887131596018, 198244731603623, 1535346218316422, 12015325816028313, 94944352095728825, 757046484552152932, 6087537591051072864
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
REFERENCES
|
Miklós Bóna, Combinatorics of Permutations. Discrete Mathematics and its Applications (Boca Raton), 2nd edn. CRC Press, Boca Raton (2012).
|
|
LINKS
|
David Bevan, Table of n, a(n) for n = 0..50 (from the Conway/Guttmann reference; terms 0..31 by Joerg Arndt, taken from the Johansson/Nakamura reference; terms 37..50 by Bjarki Ágúst Guðmundsson, taken from the Conway/Guttmann/Zinn-Justin reference).
|
|
EXAMPLE
|
a(4)=23 because all 24 permutations of length 4, except 1324 itself, avoid the pattern 1324.
|
|
MAPLE
|
count1324 := proc(n::nonnegint) if (n<4) then return n!; fi; if (n=4) then return 23; fi; return nodes([5, 5, 5, 5], n-5) + nodes([5, 3, 5, 5], n-5) + nodes([5, 4, 4, 5], n-5) + nodes([5, 5, 4, 5], n-5) + nodes([4, 3, 4], n-5) + nodes([5, 3, 4, 5], n-5); end:
nodes := proc(p, h) option remember; local i, j, s, l; if (h=0) then return convert(p, `+`); fi; s := 0; for j to nops(p) do l := p[j]+1; for i from 2 to j do l := l, `min`(j+1, p[i]); od; for i from j+1 to p[j] do l := l, p[i-1]+1; od; s := s+nodes([l], h-1); od; return s; end:
|
|
MATHEMATICA
|
a[n_] := n!/; n<4; a[4]=23; a[n_] := Total[nodes[#, n-5]&/@{{4, 3, 4}, {5, 3, 4, 5}, {5, 3, 5, 5}, {5, 4, 4, 5}, {5, 5, 4, 5}, {5, 5, 5, 5}}]; nodes[p_, 0]:=Total[p]; nodes[p_, h_] := nodes[p, h] = Sum[nodes[Join[{p[[j]]+1}, Min[j+1, #]&/@p[[2;; j]], p[[j;; p[[j]]-1]]+1], h-1], {j, Length[p]}]; Array[a, 12] (* David Bevan, May 25 2012 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Darko Marinov (marinov(AT)lcs.mit.edu), May 17 2001
|
|
EXTENSIONS
|
a(23)-a(25) added from the Albert et al. paper by N. J. A. Sloane, Mar 29 2013
|
|
STATUS
|
approved
|
|
|
|