A071076 Number of permutations that avoid the generalized pattern 123-4.
1, 1, 2, 6, 23, 108, 598, 3815, 27532, 221708, 1970251, 19150132, 202064380, 2300071071, 28092017668, 366425723926, 5083645400819, 74745472084176, 1160974832572274, 18995175706664735, 326531476287842760, 5883736110875887560, 110893188848753125475
Offset: 0
Keywords
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..450
- A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
- Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, arXiv preprint arXiv:1108.2642 [math.CO], 2011.
- Sergey Kitaev, Partially Ordered Generalized Patterns, preprint.
- Sergey Kitaev, Partially Ordered Generalized Patterns, Discrete Math. 298 (2005), no. 1-3, 212-229.
- Yan Wang, Qi Fang, Shishuo Fu, Sergey Kitaev, and Haijun Li, Consecutive and quasi-consecutive patterns: des-Wilf classifications and generating functions, arXiv:2502.10128 [math.CO], 2025. See p. 9.
Programs
-
Maple
b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add( `if`(t=1 and o>j, 0, b(u+j-1, o-j, t+1)), j=1..o)+ add(b(u-j, o+j-1, 0), j=1..u)) end: a:= n-> b(n, 0$2): seq(a(n), n=0..25); # Alois P. Heinz, Nov 14 2015 -
Mathematica
b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, Sum[If[t == 1 && o > j, 0, b[u + j - 1, o - j, t + 1]], {j, 1, o}] + Sum[b[u - j, o + j - 1, 0], {j, 1, u}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 01 2016, after Alois P. Heinz *)
Formula
E.g.f.: exp(int(A(y), y=0..x)), where A(y) = (sqrt(3)/2)*exp(y/2)/cos((sqrt(3)/2)*y + Pi/6).
Let b(n) = A049774(n) = number of permutations of [n] that avoid the consecutive pattern 123. Then a(n) = Sum_{i = 0..n-1} binomial(n-1,i)*b(i)*a(n-1-i) with a(0) = b(0) = 1. [See the recurrence for A_n and B_n in the proof of Theorem 13 in Kitaev's papers.] -
Extensions
More terms from Vladeta Jovovic, May 28 2002
Link added by Andrew Baxter, May 17 2011
Typos in formula corrected by Vaclav Kotesovec, Aug 23 2014