A136029 a(n) is the number of central ideals of a garland of order 2n, i.e., a(n) = g(2n,n), where g(n,k) is the number of ideals of size k in a garland (or double fence) of order n (see A137278).

1, 1, 1, 3, 7, 15, 33, 75, 171, 391, 899, 2077, 4815, 11195, 26097, 60975, 142751, 334791, 786419, 1849905, 4357121, 10274313, 24252923, 57305241, 135521807, 320758587, 759757139, 1800838381, 4271267043, 10136815015, 24070870545

Offset

0,4

Comments

Also the number of one-sided n-step prudent walks, starting from (0,0) and ending on the y-axis, with east, west and north steps. - Shanzhen Gao, Apr 26 2011

References

T. S. Blyth, 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, Table of n, a(n) for n = 0..100

Aubrey Blecher and Arnold Knopfmacher, Prefixes of bargraph paths, Aequationes Math. (2023).

Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.

S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.

Emanuele Munarini, Combinatorial properties of the antichains of a garland, Integers, 9 (2009), 353-374.

Formula

Recurrence: (n+6)*a(n+6) - (2*n+11)*a(n+5) - (n+3)*a(n+4) - 4*a(n+3) - (n+4)*c_(n+2) - (2*n+3)*a(n+1) + (n+1), a(n) = 0.

G.f.: (1 - x^2)/sqrt( 1 - 2*x - x^2 - x^4 + 2*x^5 + x^6 ).

a(n) = 1+sum(k=1..floor((n-1)/2), sum(i=1..min(n-2*k,k), C(n-2*k+1,i) * C(k-1,k-i) * C(n-k-i,k) ) ). - Shanzhen Gao, May 13 2011

Example

a(4) = 7, since the central ideals of the garland G(4):
5..6..7..8
o..o..o..o
|\/|\/|\/|
|/\|/\|/\|
o..o..o..o
1..2..3..4
are: 1234, 1253, 1254, 1236, 2347, 1348, 2348.
a(4)=7, since there are 7 such walks: NNNN, NENW, NWNE, ENWN, ENNW, WNEN, WNNE. - Shanzhen Gao, May 13 2011

Crossrefs

Sequence in context: A026701 A249512 A140498 * A225338 A101892 A211279

Adjacent sequences: A136026 A136027 A136028 * A136030 A136031 A136032

Keyword

easy,nonn

Author

Emanuele Munarini, Mar 21 2008

Status

approved