0,2

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)

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.

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

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

From Paul D. Hanna, Aug 24 2025: (Start)

The following array (A131338) illustrates a process that generates these numbers. Start with [1] in row n = 0. For n > 0, form row n by concatenating n 1's with the partial sums of the prior row. The row sums of row n equals a(n) for n >= 0; equivalently, the final term of row n+1 equals a(n). Continuing in this way generates all the terms of this sequence.

n = 0; [1];

n = 1: [1, 1];

n = 2; [1, 1, 1, 2];

n = 3: [1, 1, 1, 1, 2, 3, 5];

n = 4: [1, 1, 1, 1, 1, 2, 3, 4, 6, 9, 14];

n = 5: [1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 20, 29, 43];

n = 6: [1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 20, 27, 37, 51, 71, 100, 143];

n = 7: [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 9, 12, 16, 21, 27, 35, 46, 61, 81, 108, 145, 196, 267, 367, 510];

... (End)

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

Table[Sum[Binomial[(k+1)*(k+2)/2+n-k-1, n-k], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Apr 05 2015 *)

(PARI) a(n)=sum(k=0, n, binomial((k+1)*(k+2)/2+n-k-1, n-k))

Cf. A098568, A131338.

Sequence in context: A249562 A006789 A202060 * A137549 A014327 A173437

Adjacent sequences: A098566 A098567 A098568 * A098570 A098571 A098572

Paul D. Hanna, Sep 15 2004, Jun 29 2007

Offset changed to 0 by Georg Fischer, Oct 29 2023

approved