1
$\begingroup$

This question already has an answer here:

Consider the different bracketings of the summation $$1+2+3+4+5\,.$$ I've listed them all below: $$ 1+(2+(3+(4+5)))\,,\quad (1+((2+3)+4))+5\\ 1+(2+((3+4)+5))\,,\quad (1+(2+(3+4)))+5\\ 1+((2+(3+4))+5)\,,\quad ((1+2)+(3+4))+5\\ 1+(((2+3)+4)+5)\,,\quad (1+2)+((3+4)+5)\\ 1+((2+3)+(4+5))\,,\quad (1+2)+(3+(4+5))\\ (1+(2+3))+(4+5)\,,\quad ((1+2)+3)+(4+5)\\ ((1+(2+3))+4)+5\,,\quad (((1+2)+3)+4)+5 $$ As we go down the first column, go up to the top of the second, and down the second column, we see that each of these bracketings are connected by a single use of the associative law. These different bracketings also exhaust the possibilities for $1+2+3+4+5$.

A similar pattern can be found for $1+2+3$ trivially and for $1+2+3+4$ almost trivially. These inspire the following graph-theoretic question:

Consider the graph whose nodes consist of the various "valid bracketings" of the summation underneath $$1+2+\cdots+n.$$ (In general, the number of nodes for this graph will be the $n-1$st Catalan number).

Two nodes will be connected by an edge if we may travel between the two via one application of the associative law.

Is there a Hamiltonian path in this graph?

The graph for $1+2+3+4+5$ is a 14-node graph where every node has a degree of three.

$\endgroup$

marked as duplicate by Robert Wolfe, Eric Wofsey, Community Oct 19 '18 at 19:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ This graph is known as the 1-skeleton of the $n$th associahedron. $\endgroup$ – Eric Wofsey Oct 19 '18 at 19:31
  • $\begingroup$ With that, this is a duplicate question. I'll initiate that. $\endgroup$ – Robert Wolfe Oct 19 '18 at 19:35
  • $\begingroup$ I might mention for other readers that "valid bracketings" of a sum can be associated uniquely to a binary tree with $n$ leaves. And the associative law corresponds with a right/left rotation in a binary tree. The answer in the other question provides a paper (a lengthy though) which shows that there exists a hamiltonian path through the graph of binary trees with edges if the trees can be rotated to one-another. That does answer my question. $\endgroup$ – Robert Wolfe Oct 19 '18 at 19:55
  • $\begingroup$ Also, if you just want to prove the general associative law, it suffices to show that this graph is connected, which seems much easier. $\endgroup$ – Bob Krueger Oct 20 '18 at 7:31