|
%I #129 Oct 30 2023 11:04:44
%S 1,2,5,14,43,143,510,1936,7775,32869,145665,674338,3251208,16282580,
%T 84512702,453697993,2514668492,14367066833,84489482201,510760424832,
%U 3170267071640,20182121448815,131642848217536,878999194493046,6003048930287115,41899203336942661
%N Row sums of the triangle of triangular binomial coefficients given by A098568.
%C From _Lara Pudwell_, Oct 23 2008: (Start)
%C 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 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 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 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 (End)
%C 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 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 From _Frank Ruskey_, Apr 17 2011: (Start)
%C Number of sequences S = s(1)s(2)...s(n) such that
%C S contains m 0's,
%C for 1 <= j <= n, s(j) < j and s(j-s(j)) = 0,
%C for 1 < j <= n, if s(j) positive, then s(j-1) < s(j).
%C (End)
%C 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 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 From _Peter R. W. McNamara_, Jun 22 2019: (Start)
%C 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 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 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 (End)
%H Andrew Howroyd, <a href="/A098569/b098569.txt">Table of n, a(n) for n = 0..500</a>
%H 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 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 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 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 CombOS - Combinatorial Object Server, <a href="http://combos.org/jump">Generate pattern-avoiding permutations</a>
%H 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 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 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 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 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 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 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 a(n) = Sum_{k=0..n} C( (k+1)*(k+2)/2 + n-k-1, n-k).
%F G.f: Sum_{k>=0} x^k*y^C(k+1,2) where y = 1/(1-x). - _Christian Bean_, Mar 25 2015
%F 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 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
%p A098569 := proc(n)
%p add( binomial((k+1)*(k+2)/2+n-k-1,n-k),k=0..n) ;
%p end proc:
%p seq(A098569(n),n=0..40) ; # _Georg Fischer_, Oct 29 2023
%t 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 (PARI) a(n)=sum(k=0,n,binomial((k+1)*(k+2)/2+n-k-1,n-k))
%Y Cf. A098568, A131338.
%K nonn
%O 0,2
%A _Paul D. Hanna_, Sep 15 2004, Jun 29 2007
%E Offset changed to 0 by _Georg Fischer_, Oct 29 2023
|
