Integer Coordinates for Associahedra

Description of the problem

The number of different parenthesizations of $n+1$ terms is given by the $n$-th Catalan number. There is also a convex polytope $K_n$ called Associahedron whose extremal points are decorated by distinct parenthesizations of $n+1$-terms. Associahedra are originally defined by Stasheff as CW-complexes to parametrize $n+1$-fold compositions in the fundamental group of a space, but they were later realized as convex polytopes embedded in an affine space with integer coordinates by Loday. Today, I am going to describe the way Loday did this using scala code.

Implementation

Let us start with implementing binary trees.

sealed trait Expr
case class Leaf(label: Int) extends Expr
case class Node(left: Expr, right: Expr) extends Expr

defined trait Expr
defined class Leaf
defined class Node

Nex, we generate all full binary trees, as fully parenthesized expressions.

def generateParenthesizations(n: Int): List[Expr] = {
  if (n == 1)
    return List(Leaf(0))  // dummy leaf
    (1 until n).flatMap { i =>
      val lefts = generateParenthesizations(i)
      val rights = generateParenthesizations(n - i)
      for (l <- lefts; r <- rights) yield Node(l, r)
    }.toList
}

generateParenthesizations: (n: Int)List[Expr]

Let us test

generateParenthesizations(4).foreach(println)

Node(Leaf(0),Node(Leaf(0),Node(Leaf(0),Leaf(0))))
Node(Leaf(0),Node(Node(Leaf(0),Leaf(0)),Leaf(0)))
Node(Node(Leaf(0),Leaf(0)),Node(Leaf(0),Leaf(0)))
Node(Node(Leaf(0),Node(Leaf(0),Leaf(0))),Leaf(0))
Node(Node(Node(Leaf(0),Leaf(0)),Leaf(0)),Leaf(0))

Next, we need a function that relabels the leaves and another function that flattens a tree into a list of leaves.

def labelLeaves(expr: Expr, counter: Iterator[Int]): Expr = expr match {
  case Leaf(_) => Leaf(counter.next())
  case Node(l, r) => Node(labelLeaves(l, counter), labelLeaves(r, counter))
}

labelLeaves: (expr: Expr, counter: Iterator[Int])Expr

def flattenTree(expr: Expr): Set[Leaf] = expr match {
  case Leaf(x) => Set(Leaf(x))
  case Node(l,r) => flattenTree(l).union(flattenTree(r))
}

flattenTree: (expr: Expr)Set[Leaf]

generateParenthesizations(4).map(x=>labelLeaves(x, Iterator.from(1))).foreach(println)

Node(Leaf(1),Node(Leaf(2),Node(Leaf(3),Leaf(4))))
Node(Leaf(1),Node(Node(Leaf(2),Leaf(3)),Leaf(4)))
Node(Node(Leaf(1),Leaf(2)),Node(Leaf(3),Leaf(4)))
Node(Node(Leaf(1),Node(Leaf(2),Leaf(3))),Leaf(4))
Node(Node(Node(Leaf(1),Leaf(2)),Leaf(3)),Leaf(4))

flattenTree(Node(Node(Leaf(1),Leaf(2)),Leaf(3)))

res2: Set[Leaf] = Set(Leaf(1), Leaf(2), Leaf(3))

In Loday’s algorithm, each binary tree is represented by a sequence of positive integers. I am going to tweak that: The $i$-th term in the sequence is the size of the minimal subtree containing both $i$ and $i+1$ minus 1.

def minSubTreeSize(expr: Expr, elts: Set[Leaf]): Int = expr match {
  case Leaf(label) => Int.MaxValue
  case Node(left, right) => {
    val flat = flattenTree(expr)
    var local = math.min(minSubTreeSize(left,elts), minSubTreeSize(right,elts))
    if(elts.subsetOf(flat)) {
      local = math.min(local, flat.size-1)
    } 
    local
  }
}

minSubTreeSize: (expr: Expr, elts: Set[Leaf])Int

minSubTreeSize(Node(Node(Leaf(1),Leaf(2)),Node(Leaf(3),Leaf(4))), Set(Leaf(2), Leaf(3)))

res3: Int = 3

Now, a function that calculates modified Loday coordinates of a parenthesization

def lodayCoordinates(expr: Expr, n: Int): List[Int] = {
  (1 until n).map(i => minSubTreeSize(expr, Set(Leaf(i), Leaf(i+1)))).toList
}

lodayCoordinates: (expr: Expr, n: Int)List[Int]

lodayCoordinates(Node(Node(Leaf(1),Leaf(2)),Node(Leaf(3),Leaf(4))), 4)

res4: List[Int] = List(1, 3, 1)

And, finally we tie everthing together:

def associahedronCoordinates(n: Int): List[List[Int]] = {
  generateParenthesizations(n).map(x => lodayCoordinates(labelLeaves(x, Iterator.from(1)), n))
}

associahedronCoordinates: (n: Int)List[List[Int]]

associahedronCoordinates(5).foreach(println)

List(4, 3, 2, 1)
List(4, 3, 1, 2)
List(4, 1, 3, 1)
List(4, 2, 1, 3)
List(4, 1, 2, 3)
List(1, 4, 2, 1)
List(1, 4, 1, 2)
List(2, 1, 4, 1)
List(1, 2, 4, 1)
List(3, 2, 1, 4)
List(3, 1, 2, 4)
List(1, 3, 1, 4)
List(2, 1, 3, 4)
List(1, 2, 3, 4)