# Counting trees

Theorem [Cayley, 1889] The number of trees on $n$ labeled vertices is $n^{n-2}$.

Theorem [Cayley, 1889] The number $T_{n,k}$ of rooted forests on $n$ labeled vertices with $k$ trees is $\binom{n-1}{k-1} n^{n-k}$.

Borchardt (1860), Sylvester (1857) $\sum_{k=1}^n T_{n,k} = (n + 1)^{n-1}$.

The number of rooted forests on $n$ labeled vertices with $k$ trees using only the first $k$ labels as roots is $\frac{\binom{n-1}{k-1} n^{n-k}}{\binom{n}{k}}$ and $\sum_{k=1}^n \frac{\binom{n-1}{k-1} n^{n-k}}{\binom{n}{k}} = \frac{n^n-n}{(n-1)^2}$.

Problem list:

# Extend to Palindrome

Problem Statement

Solution:

We need to find the longest palindrome suffix of S.

1. compute the Z function for reverse(S)\$S
2. find the smallest i<n such that i+Z[i] = n
3. append reverse(S[1,…,i-1]) to the end of S.

# Period

Problem Statement

Solution:

1. compute KMP function f for the input string
2. for each i<n, if $i \mod i-f(i) = 0$ and $f(i)\neq 0$ print $i$ with $k=i/(i-f(i))$

The hardest thing here is to prove that this procedure is correct.

# Nonnegative Partial Sums

Problem Statement

Solution:

1. compute partial sums array S of A (original array), i.e. S[i]=S[i-1]+A[i-1]. ($O(n)$)
2. compute B[i]=min{ S[j] : j<i} for each i<n. ($O(n)$)
3. compute C[i]=min{ S[j] : j>=i} for each i<n. ($O(n)$)
4. execute the loop below. ($O(n)$)
int res = 0;
for(int i=0; i&lt;n; i++)
if(C[i]-S[i] &lt;= 0 &amp;&amp; B[i]+(S[n]-S[i]) &lt;= 0)
res++;
return res;