pruef2tree :=
proc(a)
local deg, tree, u, v, p, q, n;

    n := nops(a) + 2;

    deg := [seq(1, q=1..n)];

    for q to n-2 do
        deg[a[q]] := deg[a[q]] + 1;
    od;

    tree := [];

    for q to n-2 do
        p := 1;

        while deg[p] <> 1 do
            p := p + 1;
        od;

        tree := [op(tree), {p, a[q]}];

        deg[p] := deg[p] - 1;
        deg[a[q]] := deg[a[q]] - 1;
    od;

    for u to n do
        if deg[u] = 1 then break fi;
    od;

    for v from u+1 to n do
        if deg[v] = 1 then break fi;
    od;

    [op(tree), {u, v}];
end;

trees123 :=
proc(n)
option remember;
local ind, d, a, deg, edge, q, res;

    res := 0;

    for ind from n^(n-2) to 2*n^(n-2)-1 do
        d := convert(ind, base, n);
        a := [seq(d[q]+1, q=1..n-2)];

        deg := [seq(0, q=1..n)];

        for edge in pruef2tree(a) do
            for q in edge do
                deg[q] := deg[q]+1;
            od;
        od;

        if convert(deg, `set`) subset {1, 2, 3} then
            res := res + 1;
        fi;
    od;

    res;
end;


X123 :=
proc(n)
    add(binomial(n,q)*binomial(n-q,n-2-2*q)*(n-2)!/2^q,
        q=0..floor((n-2)/2));
end;

X123A :=
proc(n)
    n!/2^(n+1)/(n-1)
    *add(binomial(n-1,q)
         *(2*binomial(2*q,n-2)-binomial(2*q, n-4)),
         q=0..n-1);
end;

X123B :=
proc(n)
    (n-2)!/2^n
    *add(binomial(n,q)*binomial(2*q, n-2), q=0..n);
end;