A110447 Number of permutations containing 3241 patterns only as part of 35241 patterns.

1, 1, 2, 6, 23, 104, 531, 2982, 18109, 117545, 808764, 5862253, 44553224, 353713232, 2924697019, 25124481690, 223768976093, 2062614190733, 19646231085928, 193102738376890, 1956191484175505, 20401540100814142, 218825717967033373, 2411606083999341827

Offset: 0

Author

David Callan, Jul 20 2005

Keywords

• nonn

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.

Crossrefs

This sequence is A030266 shifted left.

Programs

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 ]