0,3

a(n) is the number of permutations on [n] that avoid the mixed consecutive/scattered pattern 1-23-4 (also number that avoid 4-32-1).

Comment from David Callan (callan(AT)stat.wisc.edu), Jul 25 2008: a(n) appears to also count vertical-marked parallelogram polyominoes of perimeter 2n+2; vertical-marked means that for each vertical line that splits the polyomino into two nonempty polyominoes one of the unit segments on the common boundary is marked.

....._

..._|.|

._|...|

|_._._|

For example, the polyomino above, with n=5, has two such vertical lines, the left line giving only one choice for marking and the right line giving two choices.

Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math., to appear.

Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns.

In the recurrence coded in Mathematica below, v[n, a] is the number of permutations on [n] that avoid the 3-letter pattern 1-23 and start with a; u[n, a, m, k] is the number of 1-23-4-avoiding permutations on [n] that start with a, have n in position k, and for which m is the minimum of the first k-1 entries. In the last sum, j is the number of entries lying strictly between a and n both in value and position.

12534 contains a scattered 1-2-3-4 pattern (1234 itself) but not

a 1-23-4 because the 2 and 3 are not adjacent in the permutation.

Clear[u, v, w]; v[n_, a_] := v[n, a] = Sum[StirlingS2[a-1, i-1]i^(n-a), {i, a}]; u[0]=u[1]=1; u[n_]/; n>=2 := u[n] = Sum[u[n, a], {a, n}]; u[1, 1]=u[2, 1]=u[2, 2]=1; u[n_, a_]/; n>=3 && a==n := u[n-1]; u[n_, a_]/; n>=3 && a<n := u[n, a] = u[n, a, a, 2] + Sum[u[n, a, m, k], {k, 3, n}, {m, Min[a, n-k+1]}]; u[n_, a_, m_, k_]/; n>=3 && k==2 && a<n && m==a := u[n-1, a]; u[n_, a_, m_, k_]/; n>=3 && k>=3 && a<n && m==a := bi[n-a-1, k-2]v[k-1, 1]u[n-k+1, a]; u[n_, a_, m_, k_]/; n>=3 && k>=3 && a<n && m<=Min[a-1, n-k+1] := Sum[bi[n-a-1, j]bi[a-m-1, k-3-j]v[k-1, k-1-j]u[n-k+1, m], {j, Max[0, k-2-(a-m)], Min[n-a-1, k-3]}]; Table[u[n], {n, 0, 15}]

Sequence in context: A137547 A137548 A080108 this_sequence A125273 A130908 A000772

Adjacent sequences: A113224 A113225 A113226 this_sequence A113228 A113229 A113230

nonn,new

David Callan (callan(AT)stat.wisc.edu), Oct 19 2005