0,3

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 (callan(AT)stat.wisc.edu), Oct 11 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 combinatorial interpretation of the eigensequence for composition

David Callan, A Wilf equivalence related to two stack sortable permutations

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 ]

This sequence is A030266 shifted left.

Sequence in context: A137534 A137535 A030266 this_sequence A137536 A137537 A137538

Adjacent sequences: A110444 A110445 A110446 this_sequence A110448 A110449 A110450

nonn,tabl

David Callan (callan(AT)stat.wisc.edu), Jul 20 2005