A137278 Triangle read by rows: g(n,k) = number of ideals of size k in a garland (or double fence) of order n.

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

Offset: 0

Author

Emanuele Munarini, Mar 13 2008

Keywords

• easy
• nonn
• tabf

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.

Examples

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

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

• Emanuele Munarini, Mar 13 2008, Table of n, a(n) for n = 0..440 [Rows 0 through 20, flattened]

Crossrefs

Sequence of row sums is A001333 / A078057.

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