|
%I #28 Jul 10 2023 11:47:36
%S 1,1,2,5,15,55,248,1357,8809,66323,568238,5456689,58023731,676566591,
%T 8581174564,117594655061,1731202603885,27245237545195,456412842304058,
%U 8108103076572185,152241172196748919,3012385194815011031,62647074875098987344,1366035816618537022525
%N Number of permutations in S_n avoiding {bar 1}432 (i.e., every occurrence of 432 is contained in an occurrence of a 1432).
%C From _Lara Pudwell_, Oct 23 2008: (Start)
%C 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.
%C 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.
%C 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.
%C 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)
%H Lara Pudwell, <a href="/A137533/b137533.txt">Table of n, a(n) for n = 0..30</a>
%H David Callan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Callan/callan96.html">A Combinatorial Interpretation of the Eigensequence for Composition</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4. (Erratum: The rising and falling factorials in the second displayed line on page 12 should be interchanged.)
%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/pudwell_thesis.pdf">Enumeration Schemes for Pattern-Avoiding Words and Permutations</a>, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
%H Lara Pudwell, <a href="https://doi.org/10.37236/301">Enumeration schemes for permutations avoiding barred patterns</a>, El. J. Combinat. 17 (1) (2010) R29.
%t FallingFactorial[n_, k_] := Product[n - i, {i, 0, k - 1}];
%t RisingFactorial[n_, k_] := Product[n + i, {i, 0, k - 1}];
%t 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 *)
%K nonn,easy
%O 0,3
%A _Lara Pudwell_, Apr 25 2008
%E a(0)=1 prepended by _Alois P. Heinz_, Jul 10 2023
|
