|
|
A137533
|
|
Number of permutations in S_n avoiding {bar 1}432 (i.e., every occurrence of 432 is contained in an occurrence of a 1432).
|
|
1
|
|
|
1, 1, 2, 5, 15, 55, 248, 1357, 8809, 66323, 568238, 5456689, 58023731, 676566591, 8581174564, 117594655061, 1731202603885, 27245237545195, 456412842304058, 8108103076572185, 152241172196748919, 3012385194815011031, 62647074875098987344, 1366035816618537022525
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A permutation p avoids a pattern q if it has no subsequence that is order-isomorphic to q. For example, p avoids the pattern 132 if it has no subsequence abc with a < c < b.
Barred pattern avoidance considers permutations that avoid a pattern except in a special case. Given a barred pattern q, we may form two patterns, q1 = the sequence of unbarred letters of q and q2 = the sequence of all letters of q.
A permutation p avoids barred pattern q if every instance of q1 in p is embedded in a copy of q2 in p. In other words, p avoids q1, except in the special case that a copy of q1 is a subsequence of a copy of q2.
For example, if q = 5{bar 1}32{bar 4}, then q1 = 532 and q2 = 51324. p avoids q if every for decreasing subsequence acd of length 3 in p, one can find letters b and e so that the subsequence abcde of p has b < d < c < e < a. (End)
|
|
LINKS
|
|
|
MATHEMATICA
|
FallingFactorial[n_, k_] := Product[n - i, {i, 0, k - 1}];
RisingFactorial[n_, k_] := Product[n + i, {i, 0, k - 1}];
Table[(n - 1)! + Sum[FallingFactorial[k, i] RisingFactorial[n - 2 - k, j], {k, 0, n - 2}, {i, 0, k}, {j, 0, k - i}], {n, 15}] (* David Callan, Nov 21 2011 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|