3
$\begingroup$

Let $T=(V,E)$ be a tree of $10$ labeled nodes numbered $1,2,3,\dots,10$ such that there're $4$ labeled leaves $1,2,3,4$ (there may be more leaves in addition to $1,2,3,4$). How many such trees are there and how many trees are there where the leaves are only $1,2,3,4$?

I'll start with the second part. If there're exactly $4$ leaves then for every node except for nodes $1,2,3,4$ we have: $$2\le \deg(v)\le 4$$ because if $\deg(v)=1$ then it's an additional leave and if $\deg(v)>4$ then there're more than $4$ leaves.

According to the handshaking lemma: $$ \sum_{v\in V}\deg(v)=2|E|=2(|V|-1)=18 $$ We now need to find all possible combinations with repetitions of integers $2,3,4$ over $6$ bins ($6$ nodes remain after removal of $4$ leaves) such that their sum is $18-4=14$: $$ x_1+x_2+x_3+x_4+x_5+x_6=14,\quad 2\le x_i\le 4 $$ which can be solved using generating functions: $$ (x^2+x^3+x^4)^6=14\\x^{12}(1+x+x^2)=14 $$ so we need to find the coefficient of $x^{2}$ in: $$ \bigg(\frac{1-x^3}{1-x}\bigg)^6=\sum_{k=0}^6{6\choose k}(-1)^kx^{3k}\cdot \sum_{i=0}^{\infty}{i+5\choose i}x^6 $$ but it's impossible to find the coefficient from this because the powers of $x$ are too high.

I would've multiplied the result by $6!$ to account for order but I'm obviously doing something wrong.

And regarding the first part I would've found the number of labeled trees with at least the leaves $1,2,3,4$ by first choosing some ${6\choose 3}$ from $6$ nodes that are not $1,2,3,4$ and then using the same approach as above to count all combinations with repetitions and then subtract all that from the total $n^{n-2}$ possible labeled trees.

$\endgroup$
  • $\begingroup$ I now understand that it's incorrect to use my generating function because there're cases which are against conditions like having two 4-degree nodes, 4 3-degree nodes. But the trees can either contain a) one 4-degree node or b)2 nodes of degree 3. Then in case a) we have 10 degrees to distribute to 5 nodes of degree so would it be ${10+5-1\choose 10}$ and in case b)we need to distribute 8 degrees to 4 nodes so would it be ${4+8-1\choose 8}$? $\endgroup$ – Yos May 23 '18 at 11:18
1
+100
$\begingroup$

For a labeled tree on $n$ vertices the count of those where the first $m$ are leaves is obtained using Pruefer codes, which have the property that the degree of a vertex in the tree resulting from the code is one more than the number of times it appears in the code. Thus the fact that the $m$ nodes are leaves means they do not appear in the Pruefer code. Hence there remain

$$(n-m)^{n-2}$$

possible codes. If these $m$ leaves are the only ones all the other nodes must appear in the Pruefer code. We get using Stirling numbers

$$(n-m)! \times {n-2\brace n-m}.$$

Remark. I noticed the link to the OEIS only now where OP says they are not familiar with Stirling numbers. I trust the Wikipedia entry on Pruefer codes is sufficient. With the Stirling numbers we partition the $n-2$ slots in the Pruefer code into sets for the $n-m$ values, which correspond to the nodes and are then guaranteed to appear at least once. Here we have ordered set partitions however and hence the multiplier of $(n-m)!.$ E.g. when we fill four slots with two values $1$ and $2$ and have a set partition into two sets namely $\{1,3\}$ and $\{2,4\}$ then placing $1$ in the former and $2$ in the latter slots is not the same as $2$ in the former and $1$ in the latter. The fact that Stirling numbers count unordered set partitions into into non-empty sets is all we need to know here.

Addendum. OP asks for clarification of closed form at OEIS A055316. Explanation is simply that OEIS lists the formula for the number of trees having exactly $m$ leaves, as opposed to trees where nodes $1$ to $m$ are the set of leaves. This means we need to choose the $m$ leaves from the $n$ nodes first, getting

$${n\choose m} \times (n-m)! \times {n-2\brace n-m} = \frac{n!}{m!} \times {n-2\brace n-m}.$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In the oeis.org link the formula for the problem is $\frac{n!}{4!}\cdot S(n-2, n-4)$ but why in the formula you wrote is the fraction part missing? Also if I develop the Stirling formula I see that there're inclusion/exclusion logic behind it: $6^8-{6\choose 5}5^8+{6\choose 4}4^8-\dots$. Can you please explain the intuition behind it? What it looks like to me is: in the beginning there're 8 cells and each cell may have each of the 6 value, then we choose 5 values and each of those 5 values may be in 8 cells, etc. $\endgroup$ – Yos May 25 '18 at 7:34
  • $\begingroup$ So do the values represent the nodes we select while there're always 8 cells in Prufer sequence? But how does this relate to our problem? $\endgroup$ – Yos May 25 '18 at 7:34
  • $\begingroup$ Stirling numbers of the second kind may indeed by computed by inclusion-exclusion. This is done by counting ordered set partitions where we distribute $n$ labelled items into $k$ distinguishable cells, none of which may be empty. The nodes of the poset for use with PIE represent subsets $P$ of $q$ elements of $[k]$ where these cells remain empty, plus possibly more empty cells and having weight $(-1)^{|P|}$ This yields $$k!\times {n\brace k} = \sum_{q=0}^k {k\choose q} (-1)^{q} (k-q)^n.$$ and it is a useful fact but not applicable to answer the question posed here. $\endgroup$ – Marko Riedel May 25 '18 at 23:51
0
$\begingroup$

The generating functions are overkill for finding out how 6 numbers which are all 2, 3, or 4 can add up to 14. At minimum, six such numbers sum to 12, so you have 2 excess: either one 4 and five 2s, or two 3s and four 2s.

In the first case, you have four arms from a single vertex of degree 4, and you can vary the lengths of the arms for a total of 10 vertices. In the second case, you have two vertices of degree three connected by a path with zero to four vertices of degree 2, and the remaining two neighbors of each of the degree-3 vertices begin four arms to the leaves.

As far as the generating functions go, there seems to be a missing power of 6 in this line:

$$x^{12}(1+x+x^2)=14$$

but I think that was corrected in the following lines.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think the problem is that using generating functions there're cases which are against conditions like having two 4-degree nodes, 4 3-degree nodes. But there're lots of cases to count manually so I believe a formula can be derived for this case $\endgroup$ – Yos May 23 '18 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.