Constructive proof of how many trees on $[n]$ have exactly $3$ vertices with degree $3$ and all other vertices with degree $\leq 2$

Question

How many trees on $[n]$ have exactly $3$ vertices with degree $3$ and all other vertices degree $\leq 2$?

I argued from prufer codes and got that there must be $\displaystyle \frac{(n-3)!}{5!}\binom{n-2}{2}\binom{n-4}{2}\binom{n-6}{2}$. I am unsure whether this result is correct (would err on the side of saying not) - however I am interested in seeing a constructive approach to this problem (i.e. by constructing trees). Can't get very far with my attempt but I think I can picture the solution.

Answer 1

With Pruefer codes being mentioned it appears we are counting labeled trees. Using these codes we get from first principles

$${n\choose 3} \times {n-2\choose 2} {n-4\choose 2} {n-6\choose 2} \times {n-3\choose n-8} \times (n-8)!.$$

This simplifies to

$${n\choose 3} \times \frac{(n-2)!}{8} \times {n-3\choose n-8} \\ = \frac{1}{8} \frac{n!}{n(n-1)} \frac{n(n-1)(n-2)}{6} {n-3\choose n-8} = \frac{1}{8} n! {n-2\choose n-8}.$$

Counting by constructing trees we have the following structure which has eight automorphisms (Tour Eiffel):

          o
          |
          |
          |
          |
          o
         / \
        /   \
       o     o
      / \   / \
     o   o o   o

Here we distribute zero or more nodes on the edges. This gives the generating function (leading coefficient, automorphisms, first term, structure nodes, second term, nodes on top edge, third term, nodes on second level edges, fourth term, nodes on third level edges)

$$\frac{1}{8} \times z^8 \times \frac{1}{1-z} \times \frac{1}{(1-z)^2} \times \frac{1}{(1-z)^4} = \frac{1}{8} \frac{z^8}{(1-z)^7}.$$

Extracting the coefficient on $[z^n]$ we find (these are EGFs)

$$\frac{1}{8} n! [z^{n-8}] \frac{1}{(1-z)^7} = \frac{1}{8} n! {n-2\choose n-8}.$$

This is the same as what the Pruefer codes produced. Here we have repeatedly used the combinatorial class for sequences namely

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SEQ}_{=8}(\mathcal{Z}) \quad\text{and}\quad \textsc{SEQ}_{\ge 0}(\mathcal{Z}) \quad\text{which has EGF} \quad z^8 \quad\text{and}\quad \frac{1}{1-z}.$$

Addendum. We can also solve the corresponding unlabeled problem. This requires the cycle index of the edges under the automorphism group of the structure graph. We get from first principles that

$$Z(E) = \frac{1}{8} (a_1^7 + 2 a_1^5 a_2 + a_1^3 a_2^2 + 2 a_1 a_2^3 + 2 a_1 a_2 a_4).$$

We thus obtain for $n\ge 8$

$$\frac{1}{8} [z^n] z^8 \left(\frac{1}{(1-z)^7} + 2 \frac{1}{(1-z)^5} \frac{1}{1-z^2} + \frac{1}{(1-z)^3} \frac{1}{(1-z^2)^2} \\ + 2 \frac{1}{1-z} \frac{1}{(1-z^2)^3} + 2 \frac{1}{1-z} \frac{1}{1-z^2} \frac{1}{1-z^4}\right).$$

This simplifies to

$$z^8 \frac{1 - z + 2z^2}{(1 - z)^7(1 + z)^3(1 + z^2)}.$$

This gives the following sequence starting at $n=8:$

$$1, 3, 10, 24, 55, 109, 206, 360, 606, 970, 1508, 2264, 3322, \ldots$$

These may be verified with the following NAUTY / Perl script:

#! /usr/bin/perl -w
#

sub decode_graph {
    my ($str) = @_;

    sub R {
        my (@args) = map {
            sprintf "%06b", $_;
        } @_;
        join '', @args;
    }

    my (@ents) = map {
        ord($_) - 63 
    } split //, $str;

    my $n = shift @ents;
    my @adj_data = split //, R(@ents);

    my $adj = []; my $pos = 0;
    for(my $ind2 = 1; $ind2 < $n; $ind2++){
        for(my $ind1 = 0; $ind1 < $ind2; $ind1++){
            $adj->[$ind1]->[$ind2] = $adj_data[$pos];
            $adj->[$ind2]->[$ind1] = $adj_data[$pos];

            $pos++;
        }
    }

    return $adj;
}

MAIN: {
    my $mx = shift || 2;
    die "out of range for GENG: $mx" 
        if $mx < 2 || $mx > 32;

    for(my $n=2; $n <= $mx; $n++){
        my $cmd = sprintf "../nauty26r7/geng -c %d %d",
        $n, $n-1;

        my $count = 0;

        open GENG, "$cmd 2>/dev/null|";
        while(my $tree = <GENG>){
            chomp $tree; my $adj = decode_graph $tree;

            my $vd3 = 0;
            
            my $v;
            for($v = 0; $v < $n; $v++){
                my $deg = 0;
                for(my $w = 0; $w < $n; $w++){
                    my $ent = $adj->[$v]->[$w];
                    $deg++ if defined($ent) && $ent == 1;
                }

                last if $deg > 3;
                if($deg == 3){
                    $vd3++;
                    last if $vd3 > 3;
                }
            }

            $count++ if $v == $n && $vd3 == 3;
        }
        close GENG;

        print "$count\n";
    }
}