OFFSET
1,2
COMMENTS
For each increasing rooted tree with nodes 0,1,...,n-1 (where node 0 is the root and each node i>0 has a parent < i), the maximum depth is computed, and a(n) is the sum of these maximum depths over all such trees. The total number of such trees is (n-1)!.
FORMULA
a(n) = Sum_{k=1..n-1} (k+1)*A179454(n-1, k) for n >= 2. - Jason Yuen, Nov 25 2025
EXAMPLE
For n=3, there are 2 trees:
Tree 1: 0->1, 0->2 (depths: 1,2,2; max depth=2)
Tree 2: 0->1, 1->2 (depths: 1,2,3; max depth=3)
Sum = 2 + 3 = 5, so a(3)=5.
PROG
(C++) // DFS enumeration:
#include <iostream>
using u32 = unsigned;
using u64 = unsigned long long;
u32 n, dep[30] = {1}, pa[30];
u64 ans;
void dfs(u32 i) {
if (i == n) {
u32 cur = 0;
for (u32 i = 0; i < n; ++i)
if (cur < dep[i])
cur = dep[i];
ans += cur;
return;
}
for (u32 p = 0; p < i; ++p) pa[i] = p, dep[i] = dep[p] + 1, dfs(i + 1);
}
int main() {
for (n = 1; n < 14; ++n) {
ans = 0;
dfs(1);
std::cout << ans << '\n';
}
}
(Python) # Dynamic Programming:
import math
from fractions import Fraction
def A390861_first(N):
C = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
C[i][0] = 1
for j in range(1, i + 1):
C[i][j] = C[i - 1][j] + C[i - 1][j - 1]
g = [[Fraction(0) for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(N + 1):
g[0][i] = Fraction(1)
for i in range(1, N + 1):
for k in range(1, N + 1):
total = Fraction(0)
for j in range(1, i + 1):
total += g[j - 1][k - 1] * g[i - j][k]
if i > 0:
g[i][k] = total / i
else:
g[i][k] = total
results = []
for n in range(1, N + 1):
ans = Fraction(0)
for d in range(1, n + 1):
term = g[n - 1][d - 1]
if d >= 2:
term -= g[n - 1][d - 2]
ans += term * d
ans *= math.factorial(n - 1)
results.append(int(ans))
return results
print(A390861_first(120))
CROSSREFS
KEYWORD
nonn
AUTHOR
Jiang Chenyang, Nov 22 2025
STATUS
approved