

A098569


Row sums of the triangle of triangular binomial coefficients given by A098568.


4



1, 2, 5, 14, 43, 143, 510, 1936, 7775, 32869, 145665, 674338, 3251208, 16282580, 84512702, 453697993, 2514668492, 14367066833, 84489482201, 510760424832, 3170267071640, 20182121448815, 131642848217536, 878999194493046
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

From Lara Pudwell, Oct 23 2008: (Start)
A permutation p avoids a pattern q if it has no subsequence that is orderisomorphic 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 ClaessonDukesKitaev 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(js(j)) = 0,
for 1 < j <= n, if s(j) positive, then s(j1) < 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 uppertriangular 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(k1)] or equals 1 + max([d(1), d(2), ..., d(k1)]) = 1 + asc([d(1), d(2), ..., d(k1)]) where asc(.) counts the ascents of its argument. Such sequences are called "self modified ascent sequences" in BousquetMé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 downset. 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

Table of n, a(n) for n=1..24.
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], 20152017.
Mireille BousquetMélou, Anders Claesson, Mark Dukes and Sergey Kitaev, (2+2)free posets, ascent sequences and pattern avoiding permutations, arXiv:0806.0666 [math.CO], 20082009.
William Y. C. Chen, Alvin Y.L. Dai, Theodore Dokos, Tim Dwyer and Bruce E. Sagan, On 021Avoiding Ascent Sequences, The Electronic Journal of Combinatorics Volume 20, Issue 1 (2013), #P76.
CombOS  Combinatorial Object Server, Generate patternavoiding permutations
Mark Dukes and Peter R. W. McNamara, Refining the bijections among ascent sequences, (2+2)free posets, integer matrices and patternavoiding permutations, arXiv:1807.11505 [math.CO], 20182019; Journal of Combinatorial Theory (Series A), 167 (2019), 403430.
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 Nfree posets, Discrete Math. 275 (2004), no. 13, 165175.
Nate Kube and Frank Ruskey, Sequences That Satisfy a(na(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 PatternAvoiding 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 + nk1, nk).
G.f: Sum_{k>=0} x^k*y^C(k+1,2) where y = 1/(1x).  Christian Bean, Mar 25 2015
Conjecture: +5*n*(5*n+2)*(5*n1)*(5*n+1)*(5*n+3)*(55303808255589950000*n^2 166421661804018500711*n +120006713319093645177)*a(n) +2*(86412200399359296875000*n^7 4174551589017122916238944*n^6 +21725385417776314265316005*n^5 47431766021990646745350906*n^4 +54059851396175399486879390*n^3 33670127603774083168861896*n^2 +10730495677812138418771845*n 1355566046210793354796254)*a(n1) 16 *(2*n3)*(254382731949538555470968*n^6 2425106516245465759056504*n^5 +9273311253089218776731081*n^4 18087228448733735147641266*n^3 +18812619967568366483030744*n^2 9762465386200886680985595*n +1926993964799803921425162)*a(n2) 256*(2*n5)*(n2)*(2*n3) *(1695995251317186325856*n^4 5818923905729743445808*n^3 +11257757921048683615348*n^2 9769440620530244262654*n +2673232146539271638523)*a(n3) 12288*(n2)*(n3)*(2*n3)*(2*n5)*(2*n7)*(67594526602312260488*n^2 109388170912525817096*n +37502445127418682023)*a(n4)=0.  R. J. Mathar, Aug 04 2015


EXAMPLE

In reference to comment about s(1)s(2)...s(n) above, a(4) = 14 = {0000, 0001, 0002, 0003, 0010, 0020, 0100, 0012, 0013, 0023, 0101, 0103, 0120, 0123}.  Frank Ruskey, Apr 17 2011


MATHEMATICA

Table[Sum[Binomial[(k+1)*(k+2)/2+nk1, nk], {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+nk1, nk))


CROSSREFS

Cf. A098568, A131338.
Sequence in context: A249562 A006789 A202060 * A137549 A014327 A173437
Adjacent sequences: A098566 A098567 A098568 * A098570 A098571 A098572


KEYWORD

nonn


AUTHOR

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


STATUS

approved



