A110447 - OEIS

%I #24 Jul 10 2023 10:28:41

%S 1,1,2,6,23,104,531,2982,18109,117545,808764,5862253,44553224,

%T 353713232,2924697019,25124481690,223768976093,2062614190733,

%U 19646231085928,193102738376890,1956191484175505,20401540100814142,218825717967033373,2411606083999341827

%N Number of permutations containing 3241 patterns only as part of 35241 patterns.

%C 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.

%C 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

%H David Callan, <a href="http://arxiv.org/abs/math/0507169">A combinatorial interpretation of the eigensequence for composition</a>, arXiv:math/0507169 [math.CO], 2005.

%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.

%H David Callan, <a href="http://arxiv.org/abs/math/0510211">A Wilf equivalence related to two stack sortable permutations</a>, arXiv:math/0510211 [math.CO], 2005.

%H David Callan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Callan/callan2.html">Lagrange Inversion Counts 3bar-5241-Avoiding Permutations</a>, J. Int. Seq. 14 (2011) # 11.9.4

%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.

%p A:= proc(n) option remember; unapply(`if`(n=0, x,

%p       A(n-1)(x)+coeff(A(n-1)(A(n-1)(x)), x, n) *x^(n+1)), x)

%p     end:

%p a:= n-> coeff(A(1+n)(x), x, 1+n):

%p seq(a(n), n=0..23);  # _Alois P. Heinz_, Jul 10 2023

%t (* The following recurrence for a(n) is derived in the first linked paper *)

%t a[0]=c[1]=1

%t a[n_]/;n>=1 := a[n] = Sum[a[i]c[n-i], {i, 0, n-1}]

%t c[n_]/;n>=2 := c[n] = Sum[i a[n-1, i], {i, n-1}]

%t 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}]

%t a[ n_, n_ ]/;n>=1 := a[n, n] = a[n-1]

%t (* The following Mathematica code generates all the permutations counted by a(n).

%t Run the code; then Aset[n] returns the permutations counted by a(n). *)

%t Aset[0] = { { } }

%t Aset[1] = { {1} }

%t Cset[1] = { {1} }

%t Aset[n_, n_ ]/;n>=1 := Aset[n, n ] = Map[Join[{n}, # ]&, Aset[n-1 ] ]

%t processBn[n_, single_, i_] := Module[{base=Drop[Range[n], {i}]}, Join[{i}, base[[single]] ] ]

%t Cset[n_]/;n>=2 := Cset[n] = Flatten[Table[Map[processBn[n, #, i]&, Aset[n-1, j-1]], {j, 2, n}, {i, j-1}], 2]

%t processAn[pair_, j_]:=Module[{p1=pair[[1]], p2=pair[[2]]}, Flatten[Insert[j+p2, p1, 2] ] ]

%t Aset[ n_ ]/;n>=2 := Aset[ n ] = Flatten[ Table[ Map[ processAn[ #, j ]&, CartesianProduct[ Aset[ j ], Cset[ n-j ] ] ], {j, 0, n-1} ], 1 ]

%t 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]]] ]

%t 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 ]

%Y This sequence is A030266 shifted left.

%K nonn

%O 0,3

%A _David Callan_, Jul 20 2005