cp's OEIS Frontend

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

%I A110447 #24 Jul 10 2023 10:28:41
%S A110447 1,1,2,6,23,104,531,2982,18109,117545,808764,5862253,44553224,
%T A110447 353713232,2924697019,25124481690,223768976093,2062614190733,
%U A110447 19646231085928,193102738376890,1956191484175505,20401540100814142,218825717967033373,2411606083999341827
%N A110447 Number of permutations containing 3241 patterns only as part of 35241 patterns.
%C A110447 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 A110447 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 A110447 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 A110447 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 A110447 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 A110447 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 A110447 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 A110447 A:= proc(n) option remember; unapply(`if`(n=0, x,
%p A110447       A(n-1)(x)+coeff(A(n-1)(A(n-1)(x)), x, n) *x^(n+1)), x)
%p A110447     end:
%p A110447 a:= n-> coeff(A(1+n)(x), x, 1+n):
%p A110447 seq(a(n), n=0..23);  # _Alois P. Heinz_, Jul 10 2023
%t A110447 (* The following recurrence for a(n) is derived in the first linked paper *)
%t A110447 a[0]=c[1]=1
%t A110447 a[n_]/;n>=1 := a[n] = Sum[a[i]c[n-i], {i, 0, n-1}]
%t A110447 c[n_]/;n>=2 := c[n] = Sum[i a[n-1, i], {i, n-1}]
%t A110447 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 A110447 a[ n_, n_ ]/;n>=1 := a[n, n] = a[n-1]
%t A110447 (* The following Mathematica code generates all the permutations counted by a(n).
%t A110447 Run the code; then Aset[n] returns the permutations counted by a(n). *)
%t A110447 Aset[0] = { { } }
%t A110447 Aset[1] = { {1} }
%t A110447 Cset[1] = { {1} }
%t A110447 Aset[n_, n_ ]/;n>=1 := Aset[n, n ] = Map[Join[{n}, # ]&, Aset[n-1 ] ]
%t A110447 processBn[n_, single_, i_] := Module[{base=Drop[Range[n], {i}]}, Join[{i}, base[[single]] ] ]
%t A110447 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 A110447 processAn[pair_, j_]:=Module[{p1=pair[[1]], p2=pair[[2]]}, Flatten[Insert[j+p2, p1, 2] ] ]
%t A110447 Aset[ n_ ]/;n>=2 := Aset[ n ] = Flatten[ Table[ Map[ processAn[ #, j ]&, CartesianProduct[ Aset[ j ], Cset[ n-j ] ] ], {j, 0, n-1} ], 1 ]
%t A110447 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 A110447 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 A110447 This sequence is A030266 shifted left.
%K A110447 nonn
%O A110447 0,3
%A A110447 _David Callan_, Jul 20 2005