Number of Branches on a Tree that spans a grid

Question

I want to count the arrows of a tree that spans a $n$-dimensional grid in a certain way.

Take a $n$-dimensional grid of equal side length $f$. I'll use $n=2$ and $f=4$ in this example, but the question is for all $n$ or $f$.

$$ \begin{array}{|c|c|c|c|} \hline \cdot & \cdot & \cdot & \cdot \\ \hline \cdot & \cdot & \cdot & \cdot \\ \hline \cdot & \cdot & \cdot & \cdot \\ \hline \cdot & \cdot & \cdot & \cdot \\ \hline \end{array} $$

Now, if instead of a grid, we 'turn' this into a tree, starting from the top left element, traversing the highest dimension (= the diagonal), then recursively the lower dimension(s), getting this:

$$\begin{array}{ccccccc} \cdot & \rightarrow & \cdot & \rightarrow & \cdot & \rightarrow & \cdot \\ \downarrow & \searrow & & & \\ \cdot & & \cdot & \rightarrow & \cdot & \rightarrow & \cdot \\ \downarrow & & \downarrow & \searrow & \\ \cdot & & \cdot & & \cdot & \rightarrow & \cdot \\ \downarrow & & \downarrow & & \downarrow& \searrow & \\ \cdot & & \cdot & & \cdot & & \cdot \end{array}$$

We count the arrows:

$$\begin{array}{c|ccc} \text{Size} & 1 & 2 & 3 \\ \hline \text{Dimension 1} & 6 & 4 & 2 \\ \text{Dimension 2} & 1 & 1 & 1 \end{array}$$

The $\text{Size}$ is the side length of the 'matrix' the arrow points to. For example, the $6$ arrows of dimension $1$ are the 'last' ones, pointing to a matrix of side length $1$ each. Similarly, the first diagonal arrow points to a matrix of side length $3$.

The arrow counts seem to follow the following formula: $$\binom{n}{Dimension}\cdot (f-Size)^{n - Dimension}$$

So, for $Dimension = 1, Size=1$, we get $$\binom{2}{1}\cdot (4-1)^{2 - 1}=6$$

I'd need an explanation why the arrows counts grow in this way, or just a pointer to a similar question. I'm not sure how to search for this, let alone appropriately tag this question.

Thanks.

Answer 1

Here is some (pseudo?)code that I think describes your recursive process:

## Double indexed array M whose elements M[d][s] are the sets of vertices 
##  that have the given dimension d and size s. Each vertex counts the
##  arrow that points to it.
dim_size_array = [[set([]) for i in range(f)] for j in range(n)]

# Takes in a list of current coordinate and active indices
function dim_size_count(C,A)

    if A == []:
        return
    if C[A[0]] == f:
        return

    # Diagonal step: traverse the diagonal in the active indices
    new_C = [C[i]+1 for i in A]
    dim_size_count(new_C,A)

    # Counting step: after returning from an arrow, count its statistics
    dim = len(A)
    size = 1+ f - new_C[A[0]]
    dim_size_array[dim][size].add(new_C)  

    # Dimension-lowering step: deactivate one index to "go down a dimension"
    for x in A:
        new_A = remove(A,x)
        dim_size_count(C,new_A)

# Now do it! Start at (1,1,...,1) with all indices active.
dim_size_count([1 for i in range(n)], range(n))

Notice that when a vertex is counted, $1\leq c_i\leq c_a\leq f$ for all active indices $a$ and all indices $i$, with equality if and only if $i$ is also an active index. The counting happens after an arrow has been traversed, using the vertex on its head; so each arrow is counted (and only once by construction: sets do not count multiplicity).

Moreover each vertex is counted with size $1+f-c_a$ and dimension equal to the number of coordinates equal to $c_a$. We may therefore consider this description in reverse: the number of vertices with size $s$ and dimension $d$ is the number of integer points in $[1,f]^n$ with $d$ many largest coordinates having value $(f-s)+1$.

To count these points, first choose the $d$ coordinates that have value $s$; there are $\binom{n}{d}$ ways to do this. Then choose the values of the other coordinates; these can be anything between $1$ and $f-s$ inclusive, and so there are $f-s$ choices for the $n-d$ remaining coordinates.

Applying the product principle yields the desired formula: $\binom{n}{d}(f-s)^{n-d}$.

(Technical note: the point $(1,\dots, 1)$ does not correspond to an arrow. However, it is the unique vertex that would have size $f$ and dimension $n$, and so it doesn't interfere with any of the other counts.)