OFFSET
0,3
COMMENTS
a(n) = # permutations on [n] in which the (scattered) pattern 3241 only occurs as part of a 35241 pattern. For example, a(5) counts all 24 permutations on [4] except 3241 and the permutation p = 42531 is not counted by a(6) because the entries 4251 form a 3241 pattern but p fails to contain an entry larger than 5 between its entries 4 and 2.
a(n) = # (31-4-2)-avoiding perms on [n]. (31-4-2)-avoiding means the "3" and "1" must be consecutive in the permutation while the "4" and "2' may be scattered. For example, 35142 contains the (scattered) pattern 3-1-4-2 but avoids 31-4-2. - David Callan, Oct 11 2005
LINKS
David Callan, A combinatorial interpretation of the eigensequence for composition, arXiv:math/0507169 [math.CO], 2005.
David Callan, A Combinatorial Interpretation of the Eigensequence for Composition, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4.
David Callan, A Wilf equivalence related to two stack sortable permutations, arXiv:math/0510211 [math.CO], 2005.
David Callan, Lagrange Inversion Counts 3bar-5241-Avoiding Permutations, J. Int. Seq. 14 (2011) # 11.9.4
Lara Pudwell, Enumeration schemes for permutations avoiding barred patterns, El. J. Combinat. 17 (1) (2010) R29.
MAPLE
A:= proc(n) option remember; unapply(`if`(n=0, x,
A(n-1)(x)+coeff(A(n-1)(A(n-1)(x)), x, n) *x^(n+1)), x)
end:
a:= n-> coeff(A(1+n)(x), x, 1+n):
seq(a(n), n=0..23); # Alois P. Heinz, Jul 10 2023
MATHEMATICA
(* The following recurrence for a(n) is derived in the first linked paper *)
a[0]=c[1]=1
a[n_]/; n>=1 := a[n] = Sum[a[i]c[n-i], {i, 0, n-1}]
c[n_]/; n>=2 := c[n] = Sum[i a[n-1, i], {i, n-1}]
a[n_, k_]/; 1<=k<=n-1 := a[n, k] = Sum[a[i]a[n-1-i, j], {i, 0, k-1}, {j, k-i, n-1-i}]
a[ n_, n_ ]/; n>=1 := a[n, n] = a[n-1]
(* The following Mathematica code generates all the permutations counted by a(n).
Run the code; then Aset[n] returns the permutations counted by a(n). *)
Aset[0] = { { } }
Aset[1] = { {1} }
Cset[1] = { {1} }
Aset[n_, n_ ]/; n>=1 := Aset[n, n ] = Map[Join[{n}, # ]&, Aset[n-1 ] ]
processBn[n_, single_, i_] := Module[{base=Drop[Range[n], {i}]}, Join[{i}, base[[single]] ] ]
Cset[n_]/; n>=2 := Cset[n] = Flatten[Table[Map[processBn[n, #, i]&, Aset[n-1, j-1]], {j, 2, n}, {i, j-1}], 2]
processAn[pair_, j_]:=Module[{p1=pair[[1]], p2=pair[[2]]}, Flatten[Insert[j+p2, p1, 2] ] ]
Aset[ n_ ]/; n>=2 := Aset[ n ] = Flatten[ Table[ Map[ processAn[ #, j ]&, CartesianProduct[ Aset[ j ], Cset[ n-j ] ] ], {j, 0, n-1} ], 1 ]
processAnk[n_, k_, pair_, j_]:=Module[{p1=pair[[1]], p2=pair[[2]], base}, base=Complement[Range[j+1, n], {k}]; Join[{k}, p1, base[[p2]]] ]
Aset[ n_, k_ ]/; 1<=k<=n-1 := Aset[ n, k ] = Flatten[ Table[ Map[ processAnk[ n, k, #, j ]&, CartesianProduct[ Aset[ j ], Aset[ n-1-j, r ] ] ], {j, 0, k-1}, {r, k-j, n-1-j} ], 2 ]
CROSSREFS
KEYWORD
nonn
AUTHOR
David Callan, Jul 20 2005
STATUS
approved