|
|
A137278
|
|
Triangle read by rows: g(n,k) = number of ideals of size k in a garland (or double fence) of order n.
|
|
3
|
|
|
1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 3, 3, 3, 3, 1, 1, 4, 6, 6, 7, 6, 6, 4, 1, 1, 5, 10, 12, 14, 15, 14, 12, 10, 5, 1, 1, 6, 15, 22, 27, 32, 33, 32, 27, 22, 15, 6, 1, 1, 7, 21, 37, 50, 63, 72, 75, 72, 63, 50, 37, 21, 7, 1, 1, 8, 28, 58, 88, 118, 146, 164, 171, 164, 146, 118, 88, 58, 28, 8, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
Row n has 2n+1 terms.
Also triangle of bounded variation linear paths of length n having final height k-n (height varies from -n to n). Olivier Gérard, Aug 28 2012
Bounded variation linear paths are path formed from steps 0,1,-1 where the step successions (-1,1) or (1,-1) are not allowed.
Equivalently ternary strings of length n with subwords (0,2) and (2,0) not allowed and total sum k.
|
|
REFERENCES
|
T. S. Blyth and J. C. Varlet, Ockham Algebras, Oxford Science Pub. 1994.
E. Munarini, Enumeration of order ideals of a garland, Ars Combin. 76 (2005), 185-192.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: G(x,t) = (1-x^2*t^2)/(1-(1+x+x^2)*t+x^2*t^2+x^3*t^3).
Recurrence: g(n+3,k+3) = g(n+2,k+3) + g(n+2,k+2) + g(n+2,k+1) - g(n+1,k+1) - g(n,k).
|
|
EXAMPLE
|
In the garland
5..6..7..8
o..o..o..o
|\/|\/|\/|
|/\|/\|/\|
o..o..o..o
1..2..3..4
the ideals of size 4 are 1234, 1253, 1254, 1236, 2347, 1348, 2348.
The ternary strings of size 4 with total sum 4 are
0022, 0202, 0220, 2002, 2020, 2200,
0112, 0121, 0211,
1012, 1021, 2011,
1102, 1201, 2101,
1120, 1210, 2110,
1111
Applying the restriction gives 7 possible strings
0112, 0121, 1012, 2101, 1210, 2110, 1111
Triangle begins:
1,
1, 1, 1,
1, 2, 1, 2, 1,
1, 3, 3, 3, 3, 3, 1,
1, 4, 6, 6, 7, 6, 6, 4, 1,
1, 5, 10, 12, 14, 15, 14, 12, 10, 5, 1,
1, 6, 15, 22, 27, 32, 33, 32, 27, 22, 15, 6, 1,
...
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|