OFFSET
0,2
COMMENTS
From Lara Pudwell, Oct 23 2008: (Start)
A permutation p avoids a pattern q if it has no subsequence that is order-isomorphic to q. For example, p avoids the pattern 132 if it has no subsequence abc with a < c < b.
Barred pattern avoidance considers permutations that avoid a pattern except in a special case. Given a barred pattern q, we may form two patterns, q1 = the sequence of unbarred letters of q and q2 = the sequence of all letters of q.
A permutation p avoids barred pattern q if every instance of q1 in p is embedded in a copy of q2 in p. In other words, p avoids q1, except in the special case that a copy of q1 is a subsequence of a copy of q2.
For example, if q=5{bar 1}32{bar 4}, then q1=532 and q2 = 51324. p avoids q if every for decreasing subsequence acd of length 3 in p, one can find letters b and e so that the subsequence abcde of p has b < d < c < e < a.
(End)
Also equals the row sums of triangle A131338, which starts with a '1' in row 0 and then for n > 0 row n consists of n '1's followed by the partial sums of the prior row.
Also the number of permutations in S_n avoiding {bar 4}25{bar 1}3 (i.e., every occurrence of 253 is contained in an occurrence of a 42513). - Lara Pudwell, Apr 25 2008 (see the Claesson-Dukes-Kitaev article)
From Frank Ruskey, Apr 17 2011: (Start)
Number of sequences S = s(1)s(2)...s(n) such that
S contains m 0's,
for 1 <= j <= n, s(j) < j and s(j-s(j)) = 0,
for 1 < j <= n, if s(j) positive, then s(j-1) < s(j).
(End)
a(n) is also the number of length n permutations that simultaneously avoid the bivincular patterns (132,{2},{}) and (132,{},{2}). - Christian Bean, Mar 25 2015
a(n) is also the number of length n permutations that simultaneously avoid the bivincular patterns (123,{2},{}) and (123,{},{2}). These are the same as the permutations avoiding {bar 4}23{bar 1}5. - Christian Bean, Jun 03 2015
From Peter R. W. McNamara, Jun 22 2019: (Start)
a(n) is the number of upper-triangular matrices with nonnegative integer entries whose entries sum to n, and whose diagonal entries are all positive.
a(n) is the number of ascent sequences [d(1), d(2), ..., d(n)] A022493 for which d(k) comes from the interval [0, d(k-1)] or equals 1 + max([d(1), d(2), ..., d(k-1)]) = 1 + asc([d(1), d(2), ..., d(k-1)]) where asc(.) counts the ascents of its argument. Such sequences are called "self modified ascent sequences" in Bousquet-Mélou et al.
The elements of a (2+2)-free poset can be partitioned into levels, where all elements at the same level have the same strict down-set. Then a(n) is the number of unlabeled (2+2)-free posets with n elements that contain a chain with exactly one element at each level.
(End)
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..500
Christian Bean, A. Claesson and H. Ulfarsson, Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3, arXiv preprint arXiv:1512.03226 [math.CO], 2015-2017.
Beáta Bényi, Toufik Mansour, and José L. Ramírez, Pattern Avoidance in Weak Ascent Sequences, arXiv:2309.06518 [math.CO], 2023.
Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes and Sergey Kitaev, (2+2)-free posets, ascent sequences and pattern avoiding permutations, arXiv:0806.0666 [math.CO], 2008-2009.
William Y. C. Chen, Alvin Y.L. Dai, Theodore Dokos, Tim Dwyer and Bruce E. Sagan, On 021-Avoiding Ascent Sequences, The Electronic Journal of Combinatorics Volume 20, Issue 1 (2013), #P76.
CombOS - Combinatorial Object Server, Generate pattern-avoiding permutations
Mark Dukes and Peter R. W. McNamara, Refining the bijections among ascent sequences, (2+2)-free posets, integer matrices and pattern-avoiding permutations, arXiv:1807.11505 [math.CO], 2018-2019; Journal of Combinatorial Theory (Series A), 167 (2019), 403-430.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
Soheir M. Khamis, Height counting of unlabeled interval and N-free posets, Discrete Math. 275 (2004), no. 1-3, 165-175.
Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
Zhicong Lin and Sherry H. F. Yan, Vincular patterns in inversion sequences, Applied Mathematics and Computation (2020), Vol. 364, 124672.
Lara Pudwell, Enumeration Schemes for Pattern-Avoiding Words and Permutations, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
Lara Pudwell, Enumeration schemes for permutations avoiding barred patterns, El. J. Combinat. 17 (1) (2010) R29.
FORMULA
a(n) = Sum_{k=0..n} C( (k+1)*(k+2)/2 + n-k-1, n-k).
G.f: Sum_{k>=0} x^k*y^C(k+1,2) where y = 1/(1-x). - Christian Bean, Mar 25 2015
log(a(n)) ~ n*(log(n) - 2*log(log(n)) + log(2) - 1 + 4*log(log(n))/log(n) - 2*log(2)/log(n) - 2/log(n)^2). - Vaclav Kotesovec, Oct 30 2023
EXAMPLE
In reference to comment about s(1)s(2)...s(n) above, a(3) = 14 = |{0000, 0001, 0002, 0003, 0010, 0020, 0100, 0012, 0013, 0023, 0101, 0103, 0120, 0123}|. - Frank Ruskey, Apr 17 2011
MAPLE
A098569 := proc(n)
add( binomial((k+1)*(k+2)/2+n-k-1, n-k), k=0..n) ;
end proc:
seq(A098569(n), n=0..40) ; # Georg Fischer, Oct 29 2023
MATHEMATICA
Table[Sum[Binomial[(k+1)*(k+2)/2+n-k-1, n-k], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Apr 05 2015 *)
PROG
(PARI) a(n)=sum(k=0, n, binomial((k+1)*(k+2)/2+n-k-1, n-k))
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Sep 15 2004, Jun 29 2007
EXTENSIONS
Offset changed to 0 by Georg Fischer, Oct 29 2023
STATUS
approved