Counting Closed Walks and Determining Eigenvalues in Complete \( p \)-Partite Graphs \( K(n,p) \)
Taken from: [1, Exercise 1.6].
Exercise 1.6
Let $n \geq 1$. The complete $p$-partite graph $K(n,p)$ has vertex set $V = V_1 \mathbin{\unicode{x228D}} \cdots \mathbin{\unicode{x228D}} V_p$ (disjoint union), where each $\lvert V_i\rvert = n$, and an edge from every element of $V_i$ to every element of $V_j$ when $i \neq j$. (If $u, v \in V_i$, th...
Number of Closed Walks in the Complete Graph $K_p$
Taken from: [1, Exercise 1.1].
Exercise 1.1
Find a combinatorial proof of Corollary 1.6, i.e., the number of closed walks of length $\ell$ in $ K_p $ from some vertex to itself is given by
\[\frac{1}{p}\left( (p - 1)^\ell + (p - 1)(-1)^\ell \right).\]
Proof
Let $c(p, \ell)$ the number of closed walks of length $\ell$ in $K_p$ from some verte...
Number of Permutations on $n$ Letters That Have Only Cycles of Length $3$ or Less (Hayman's Method)
Taken from: [1, Exercise 5.8].
Introduction
We will asymptotically analyze the sequence $a_n$ derived from the exponential generating function $\exp\left(z + z^2/2 + z^3/3 \right)=\sum_{n \geq 0} \frac{a_n}{n!} z^n$, which corresponds to the number of permutations on $n$ letters that have only cycles of length $3$ or less (OEIS A057693). We em...