login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)). 4
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

Alois P. Heinz, Table of n, a(n) for n = 0..18

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 * A187647 A322645 A277180

Adjacent sequences:  A027683 A027684 A027685 * A027687 A027688 A027689

KEYWORD

nonn

AUTHOR

Don Knuth

EXTENSIONS

a(9)-a(14), a(15) from Alois P. Heinz, Mar 17 2013, Mar 27 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 27 21:47 EST 2020. Contains 332310 sequences. (Running on oeis4.)