I apologize in advance that this question must sound highly amateurish, but I am wondering if there is any connection between the formula https://oeis.org/A127670 , which counts the number of fixed $n$-cell polycubes that are proper in $n-1$ dimensions, and Cayley's tree formula. The expression for the former is $$a_n = 2^n(n+1)^{n-2}$$ and the latter is $$b_n = n^{n-2},$$ which means that $$a_n = \frac{2^n}{n+1} b_{n+1}.$$ Is there any significance to this at all? The reason I ask is that I'm working on a Cayley-type tree enumeration problem that yields the sequence $a_n$ according to numerical computations, and I am struggling to see the connection.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Yes there is a connection. While $n^{n-2}$ counts the number of vertex labeled trees on $n$ vertices, the expression $2^n(n+1)^{n-2}$ counts the number of edge labeled trees on $n$ edges. There is a bijection between edge labeled trees on $n$ vertices and proper $(n-1)$-dimensional polycubes of size $n$. See lemma 2 (which combinatorially proves the relation $a_n=\frac{2^n}{n+1}b_{n+1}$) and theorem 1 in Formulae and growth rates of high-dimensional polycubes by R. Barequet, G. Barequet, G Rote.
answered May 15, 2018 at 2:14
-
$\begingroup$ That has to be the fastest answer I've ever seen on this site...exactly what I was looking for! $\endgroup$ Commented May 15, 2018 at 2:26
-
1$\begingroup$ @TomSolberg The paper is cited in the OEIS entry. $\endgroup$ Commented May 15, 2018 at 3:45
-
1$\begingroup$ worth mentioning: directed edge-labelled trees. The thing causing the extra factor of $2^n$ to appear compared to Cayley's formula is really the move from undirected to directed trees, not particularly the move from vertex-labelled to edge-labelled. $\endgroup$ Commented May 15, 2018 at 10:51