10
$\begingroup$

Let $F(n;i)$ be the number of labeled $i$-edge forests on $n$ vertices (A138464 on the OEIS). The first few values of $F(n;i) \pmod n$ are listed below:

$$\begin{array}{r|rrrrrrrrrrr} & i=0 & 1 & 2 & 3 & 4 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline n=2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 2 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 5 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 6 & 1 & 3 & 3 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 7 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 8 & 1 & 4 & 2 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 9 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 10 & 1 & 5 & 0 & 0 & 5 & 5 & 0 & 0 & 0 & 0 & 0 \\ 11 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array}$$

We see that if $n$ is an odd prime power and $i \geq 1$, then $n$ divides $F(n;i)$. I can prove this via group actions and induction.

Question: Is there is a published proof of this result?

(Or, alternatively, a succinct proof of this result.)

Improve this question
$\endgroup$
1
  • $\begingroup$ Actually, I suspect this is true for all odd $n$ (although, since I only need the result for odd prime powers, I haven't looked into the more general case). $\endgroup$
    – Rebecca J. Stones
    Commented Mar 14, 2014 at 22:33

1 Answer 1

Reset to default
4
$\begingroup$

The proof is now Lemma 2 here:

A. P. Mani, R. J. Stones, Congruences for the weighted number of labeled forests. Integers, 16 (2016): A17.

which is freely available from: http://www.integers-ejcnt.org/vol16.html

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .