|
|
A027686
|
|
Number of ways to transform say (((((((ab)c)d)e)f)g)h) to (a(b(c(d(e(f(gh))))))) where there are n multiplications (hence n+1 variables) by repeatedly applying the one-way associative law ((xy)z) -> (x(yz)).
|
|
5
|
|
|
1, 1, 1, 2, 9, 98, 2981, 340549, 216569887, 994441978397, 36812710172987995, 12001387004225881846755, 37783429241635794906272195147, 1255674108542254217846031366276646429, 478743486470659944952229546087586449114251007, 2262324605850021060149051111359520226936424091385392945
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Number of maximal chains in the Tamari lattice T_n. For n=3 there are 2 maximal chains in the Tamari lattice T3, whose Hasse diagram is a pentagon. - F. Chapoton, Mar 15 2013
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.2.1.6, see solution to Exercise 34.
|
|
LINKS
|
|
|
MAPLE
|
s:= proc(n) s(n):=`if`(n=0, [], [s(n-1), []]) end:
f:= l-> l=[] or l[1]=[] and f(l[2]):
v:= proc(l) v(l):=`if`(f(l), [], [`if`(l[1]<>[],
[l[1][1], [l[1][2], l[2]]], [][]),
seq([w, l[2]], w=v(l[1])), seq([l[1], w], w=v(l[2]))])
end:
p:= proc(l) p(l):=`if`(f(l), 1, add(p(w), w=v(l))) end:
a:= n-> p(s(n)):
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|