|
| |
|
|
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 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
|
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], 2015-2017.
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
Conjecture: +5*n*(5*n+2)*(5*n-1)*(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(n-1) -16 *(2*n-3)*(254382731949538555470968*n^6 -2425106516245465759056504*n^5 +9273311253089218776731081*n^4 -18087228448733735147641266*n^3 +18812619967568366483030744*n^2 -9762465386200886680985595*n +1926993964799803921425162)*a(n-2) -256*(2*n-5)*(n-2)*(2*n-3) *(1695995251317186325856*n^4 -5818923905729743445808*n^3 +11257757921048683615348*n^2 -9769440620530244262654*n +2673232146539271638523)*a(n-3) -12288*(n-2)*(n-3)*(2*n-3)*(2*n-5)*(2*n-7)*(67594526602312260488*n^2 -109388170912525817096*n +37502445127418682023)*a(n-4)=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+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
|
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
|
| |
|
|
