login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 0s,

  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, 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, 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.

Mark Dukes, 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, Aaron Williams, Combinatorial generation via permutation languages, 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, 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.

L. 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,changed

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 20 13:03 EST 2019. Contains 329336 sequences. (Running on oeis4.)