Skip to main content
added 254 characters in body
Source Link

Even with a distinguished root and insisting that all isomorphisms respect this distinguished root, this will be a challenging enumeration.

For $k \leq 2$ the problem is straightforward: The count is the number of partitions of $d_2$ into at most $d_1$ parts. This has an upper bound of $\binom{d_2+d_1 - 1}{d_1 - 1}$, call this quantity $q(d_2,d_1)$, and the literature doubtless has more to say on the exact count. Call this number $p(d_2,d_1)$, and let such a partition be denoted by the vector $(n_1,n_2,\ldots, n_{d_1})$, where the $n_i$ are in decreasing order and sum to $d_2$. To handle $d_3$ will involve a summation over all such partitions of products of terms like $p(k_i,n_i)$, where the $k_i$ sum up to $d_3$. Except it won't be that simple, as you need $k_i$ to be 0 when $n_i$ is 0, and you need to identify certain counts when you have $n_i=n_{i+1}$, and so on. Using $\prod q(d_{i+1},d_i)$ as an upper bound will likely be a weak estimate, unless all the $d$'s are small, and even then I would compare with a computer enumeration.

Of course $n(c,d_2,d_1)$ will often be much smaller than $p(d_2,d_1)$, where this new count restricts the parts $n_i \lt c$, and there should be some literature on $n()$ as well. I still recommend computer enumeration for cases of small diameter.

Even with a distinguished root and insisting that all isomorphisms respect this distinguished root, this will be a challenging enumeration.

For $k \leq 2$ the problem is straightforward: The count is the number of partitions of $d_2$ into at most $d_1$ parts. This has an upper bound of $\binom{d_2+d_1 - 1}{d_1 - 1}$, call this quantity $q(d_2,d_1)$, and the literature doubtless has more to say on the exact count. Call this number $p(d_2,d_1)$, and let such a partition be denoted by the vector $(n_1,n_2,\ldots, n_{d_1})$, where the $n_i$ are in decreasing order and sum to $d_2$. To handle $d_3$ will involve a summation over all such partitions of products of terms like $p(k_i,n_i)$, where the $k_i$ sum up to $d_3$. Except it won't be that simple, as you need $k_i$ to be 0 when $n_i$ is 0, and you need to identify certain counts when you have $n_i=n_{i+1}$, and so on. Using $\prod q(d_{i+1},d_i)$ as an upper bound will likely be a weak estimate, unless all the $d$'s are small, and even then I would compare with a computer enumeration.

Even with a distinguished root and insisting that all isomorphisms respect this distinguished root, this will be a challenging enumeration.

For $k \leq 2$ the problem is straightforward: The count is the number of partitions of $d_2$ into at most $d_1$ parts. This has an upper bound of $\binom{d_2+d_1 - 1}{d_1 - 1}$, call this quantity $q(d_2,d_1)$, and the literature doubtless has more to say on the exact count. Call this number $p(d_2,d_1)$, and let such a partition be denoted by the vector $(n_1,n_2,\ldots, n_{d_1})$, where the $n_i$ are in decreasing order and sum to $d_2$. To handle $d_3$ will involve a summation over all such partitions of products of terms like $p(k_i,n_i)$, where the $k_i$ sum up to $d_3$. Except it won't be that simple, as you need $k_i$ to be 0 when $n_i$ is 0, and you need to identify certain counts when you have $n_i=n_{i+1}$, and so on. Using $\prod q(d_{i+1},d_i)$ as an upper bound will likely be a weak estimate, unless all the $d$'s are small, and even then I would compare with a computer enumeration.

Of course $n(c,d_2,d_1)$ will often be much smaller than $p(d_2,d_1)$, where this new count restricts the parts $n_i \lt c$, and there should be some literature on $n()$ as well. I still recommend computer enumeration for cases of small diameter.

Source Link

Even with a distinguished root and insisting that all isomorphisms respect this distinguished root, this will be a challenging enumeration.

For $k \leq 2$ the problem is straightforward: The count is the number of partitions of $d_2$ into at most $d_1$ parts. This has an upper bound of $\binom{d_2+d_1 - 1}{d_1 - 1}$, call this quantity $q(d_2,d_1)$, and the literature doubtless has more to say on the exact count. Call this number $p(d_2,d_1)$, and let such a partition be denoted by the vector $(n_1,n_2,\ldots, n_{d_1})$, where the $n_i$ are in decreasing order and sum to $d_2$. To handle $d_3$ will involve a summation over all such partitions of products of terms like $p(k_i,n_i)$, where the $k_i$ sum up to $d_3$. Except it won't be that simple, as you need $k_i$ to be 0 when $n_i$ is 0, and you need to identify certain counts when you have $n_i=n_{i+1}$, and so on. Using $\prod q(d_{i+1},d_i)$ as an upper bound will likely be a weak estimate, unless all the $d$'s are small, and even then I would compare with a computer enumeration.