|
| |
|
|
A113227
|
|
Number of permutations avoiding the pattern 1-23-4.
|
|
1
| |
|
|
1, 1, 2, 6, 23, 105, 549, 3207, 20577, 143239, 1071704, 8555388, 72442465, 647479819, 6083742438, 59885558106, 615718710929, 6595077685263, 73424063891526, 847916751131054, 10138485386085013, 125310003360265231
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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.
|
|
|
REFERENCES
| Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, Arxiv preprint arXiv:1108.2642, 2011
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math., to appear.
|
|
|
LINKS
| A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns.
|
|
|
FORMULA
| 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.
a(n) = the upper left term in M^n, M = the production matrix:
1, 1
1, 2, 1
1, 2, 3, 1
1, 2, 3, 4, 1
1, 2, 3, 4, 5, 1
...
- Gary W. Adamson, Jul 08 2011
|
|
|
EXAMPLE
| 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.
|
|
|
MATHEMATICA
| 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}]
|
|
|
CROSSREFS
| Sequence in context: A137547 A137548 A080108 * A200406 A165489 A192315
Adjacent sequences: A113224 A113225 A113226 * A113228 A113229 A113230
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| David Callan (callan(AT)stat.wisc.edu), Oct 19 2005
|
| |
|
|
