|
| |
|
|
A098569
|
|
Row sums of the triangle of triangular binomial coefficients given by A098568.
|
|
3
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| Comment from Lara Pudwell (Lara.Pudwell(AT)valpo.edu), 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 (Lara.Pudwell(AT)valpo.edu), Apr 25 2008 (see the Claesson-Dukes-Kitaev article)
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). [Frank Ruskey, Apr 17 2011]
|
|
|
REFERENCES
| Mireille Bousquet-Melou, Anders Claesson, Mark Dukes, Sergey Kitaev, (2+2)-free posets, ascent sequences and pattern avoiding permutations, arXiv:0806.0666
Khamis, Soheir M., 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.
|
|
|
LINKS
| Anders Claesson, Mark Dukes and Sergey Kitaev, Unlabeled (2+2)-free posets, ascent sequences and pattern avoiding permutations
Lara Pudwell, Enumeration Schemes for Pattern-Avoiding Words and Permutations, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
|
|
|
FORMULA
| a(n) = Sum_{k=0..n} C( (k+1)*(k+2)/2 + n-k-1, n-k).
|
|
|
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]
|
|
|
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: A155888 A006789 A202060 * A137549 A014327 A173437
Adjacent sequences: A098566 A098567 A098568 * A098570 A098571 A098572
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Paul D. Hanna (pauldhanna(AT)juno.com), Sep 15 2004, Jun 29 2007
|
| |
|
|
