login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
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
Luke Nelson, A recursion on maximal chains in the Tamari lattices, Discrete Mathematics 340.4 (2017): 661-677.
Luke Nelson, A recursion on maximal chains in the Tamari lattices, arXiv:1709.02987 [math.CO], Sep 2017
Wikipedia, Tamari lattice
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)):
seq(a(n), n=0..10); # Alois P. Heinz, Mar 17 2013
CROSSREFS
Row sums of A282698.
Cf. A000108.
Sequence in context: A013057 A237929 A227258 * A360696 A357825 A187647
KEYWORD
nonn
AUTHOR
EXTENSIONS
a(9)-a(14), a(15) from Alois P. Heinz, Mar 17 2013, Mar 27 2013
STATUS
approved