cp's OEIS Frontend

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

%I A098569 #138 Aug 26 2025 08:47:59
%S A098569 1,2,5,14,43,143,510,1936,7775,32869,145665,674338,3251208,16282580,
%T A098569 84512702,453697993,2514668492,14367066833,84489482201,510760424832,
%U A098569 3170267071640,20182121448815,131642848217536,878999194493046,6003048930287115,41899203336942661
%N A098569 Row sums of the triangle of triangular binomial coefficients given by A098568.
%C A098569 From _Lara Pudwell_, Oct 23 2008: (Start)
%C A098569 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.
%C A098569 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.
%C A098569 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.
%C A098569 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.
%C A098569 (End)
%C A098569 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.
%C A098569 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)
%C A098569 From _Frank Ruskey_, Apr 17 2011: (Start)
%C A098569 Number of sequences S = s(1)s(2)...s(n) such that
%C A098569   S contains m 0's,
%C A098569   for 1 <= j <= n, s(j) < j and s(j-s(j)) = 0,
%C A098569   for 1 < j <= n, if s(j) positive, then s(j-1) < s(j).
%C A098569 (End)
%C A098569 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
%C A098569 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
%C A098569 From _Peter R. W. McNamara_, Jun 22 2019: (Start)
%C A098569 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.
%C A098569 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.
%C A098569 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.
%C A098569 (End)
%H A098569 Andrew Howroyd, <a href="/A098569/b098569.txt">Table of n, a(n) for n = 0..500</a>
%H A098569 Christian Bean, A. Claesson and H. Ulfarsson, <a href="http://arxiv.org/abs/1512.03226">Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3</a>, arXiv preprint arXiv:1512.03226 [math.CO], 2015-2017.
%H A098569 Beáta Bényi, Toufik Mansour, and José L. Ramírez, <a href="https://arxiv.org/abs/2309.06518">Pattern Avoidance in Weak Ascent Sequences</a>, arXiv:2309.06518 [math.CO], 2023.
%H A098569 Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes and Sergey Kitaev, <a href="http://arxiv.org/abs/0806.0666">(2+2)-free posets, ascent sequences and pattern avoiding permutations</a>, arXiv:0806.0666 [math.CO], 2008-2009.
%H A098569 William Y. C. Chen, Alvin Y.L. Dai, Theodore Dokos, Tim Dwyer and Bruce E. Sagan, <a href="https://doi.org/10.37236/2472">On 021-Avoiding Ascent Sequences, The Electronic Journal of Combinatorics</a> Volume 20, Issue 1 (2013), #P76.
%H A098569 CombOS - Combinatorial Object Server, <a href="http://combos.org/jump">Generate pattern-avoiding permutations</a>
%H A098569 Mark Dukes and Peter R. W. McNamara, <a href="https://arxiv.org/abs/1807.11505">Refining the bijections among ascent sequences, (2+2)-free posets, integer matrices and pattern-avoiding permutations</a>, arXiv:1807.11505 [math.CO], 2018-2019; Journal of Combinatorial Theory (Series A), 167 (2019), 403-430.
%H A098569 Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze and Aaron Williams, <a href="https://arxiv.org/abs/1906.06069">Combinatorial generation via permutation languages. I. Fundamentals</a>, arXiv:1906.06069 [cs.DM], 2019.
%H A098569 Soheir M. Khamis, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00106-7">Height counting of unlabeled interval and N-free posets</a>, Discrete Math. 275 (2004), no. 1-3, 165-175.
%H A098569 Nate Kube and Frank Ruskey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Ruskey/ruskey99.html">Sequences That Satisfy a(n-a(n))=0</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
%H A098569 Zhicong Lin and Sherry H. F. Yan, <a href="https://doi.org/10.1016/j.amc.2019.124672">Vincular patterns in inversion sequences</a>, Applied Mathematics and Computation (2020), Vol. 364, 124672.
%H A098569 Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/pudwell_thesis.pdf">Enumeration Schemes for Pattern-Avoiding Words and Permutations</a>, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
%H A098569 Lara Pudwell, <a href="https://doi.org/10.37236/301">Enumeration schemes for permutations avoiding barred patterns</a>, El. J. Combinat. 17 (1) (2010) R29.
%F A098569 a(n) = Sum_{k=0..n} C( (k+1)*(k+2)/2 + n-k-1, n-k).
%F A098569 G.f: Sum_{k>=0} x^k*y^C(k+1,2) where y = 1/(1-x). - _Christian Bean_, Mar 25 2015
%F A098569 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
%e A098569 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
%e A098569 From _Paul D. Hanna_, Aug 24 2025: (Start)
%e A098569 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.
%e A098569   n = 0; [1];
%e A098569   n = 1: [1, 1];
%e A098569   n = 2; [1, 1, 1, 2];
%e A098569   n = 3: [1, 1, 1, 1, 2, 3, 5];
%e A098569   n = 4: [1, 1, 1, 1, 1, 2, 3, 4, 6, 9, 14];
%e A098569   n = 5: [1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 20, 29, 43];
%e A098569   n = 6: [1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 20, 27, 37, 51, 71, 100, 143];
%e A098569   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];
%e A098569   ... (End)
%p A098569 A098569 := proc(n)
%p A098569     add( binomial((k+1)*(k+2)/2+n-k-1,n-k),k=0..n) ;
%p A098569 end proc:
%p A098569 seq(A098569(n),n=0..40) ; # _Georg Fischer_, Oct 29 2023
%t A098569 Table[Sum[Binomial[(k+1)*(k+2)/2+n-k-1, n-k],{k,0,n}],{n,0,20}] (* _Vaclav Kotesovec_, Apr 05 2015 *)
%o A098569 (PARI) a(n)=sum(k=0,n,binomial((k+1)*(k+2)/2+n-k-1,n-k))
%Y A098569 Cf. A098568, A131338.
%K A098569 nonn,changed
%O A098569 0,2
%A A098569 _Paul D. Hanna_, Sep 15 2004, Jun 29 2007
%E A098569 Offset changed to 0 by _Georg Fischer_, Oct 29 2023