I am trying to understand the theory "On the number of permutations on $n$ objects with the greatest cycle length of $k$" by Solomon W Golomb and Peter Gaal.
Let $L_{k,n}$ denotes the number of permutation on $n$ letters having a greatest cycle of length $k$ . I want to understand the formula
$$L_{k,n}=\sum_{j=1}^{\lfloor n/k \rfloor}\frac{1}{j!k^j}\frac{n!}{(n-kj)!}\sum_{t=1}^{min(k-1,n-kj)}L_{t,n-kj} \quad \quad (1 <k\le n)$$
I am considering the case $\frac n4<k \le \frac n3$ . Then
$$L_{k,n}=\frac {n!}{k} \left \{ 1-\sum_{j=1}^{n-2k}\frac{1}{k+j}+\sum_{j=1}^{n-3k-1}\sum_{l=1}^{n-3k-j} \frac{1}{2(k+j)(k+l)} -\frac {1}{2k} \bigg[ 1-\sum_{j=1}^{n-3k}\frac{1}{k+j} -\frac{1}{3k}\bigg] \right \}$$
By the given restriction on $n$ there can be at most three cycles of lentgth $k$
I think the authors considered the following types of permutations along with different categories of greatest cycle length .
$(a)$ Permutations having one cycle of lenth $k$.
$(b)$ Permutations having one cycle of lenth $k$ and two cycles of length greater than $k$
$(c)$ Permutations having one cycle of length $k$ and one cycle of length greater than $k$
$(d)$ Permutations having two cycle of length $k$ and one cycle of length greater than $k$
$(e)$ Permutations having two cycle of length $k$
$(f)$ Permutations having three cycles of lenth $k$
The number of permutations in category $(a)$ are ${n \choose k }(k-1)!(n-k)!=\frac{n!}{k}$
In category $(b)$ , let the two cycles of length greater than $k$ be of length $k+j$ and $k+l$
We want to find the bounds on $j$ and $l$. Clearly $j,l\ge 1$.
Now, $k+(k+1)+(k+j)\le n$
$\implies j\le n-3k-1$
And , $k+(k+j)+(k+l)\le n$
$\implies l\le n-3k-j$
Then the number of permutations having a cycle of length $k$ and cycles of length $(k+j)$ and $(k+l)$ is given by
$$\frac 12 {n \choose k}{n-k \choose k+j}{n-2k-j \choose k+l}(k-1)!(k+j-1)!(k+l-1)!(n-3k-j-l)!$$
$$=\frac 12\frac{n!}{k}\frac{1}{(k+j)(k+l)}$$
Not sure why is the factor $\frac 12$ present. I think its because exactly after $j$ covers half the way between $1$ and $(n-3k-1)$ , the pairs of values of $k+j$ and $k+l$ interchange with respect to the first half. (Generally we are dividing by $k!$ when we are selecting $k$ groups of equals size from a given number of objects (say) $n$)
In category $(c)$, let the cycles of length greater than $k$ be $(k+j)$ . Then $j\ge1$ and
$k+(k+j)\le n$
$\implies j\le n-2k$
So , number of permutations having a cycle of length $k$ and a cycle of length greater than $(k+j)$ is given by
$${n \choose k}{n-k \choose k+j}(k-1)!(k+j-1)!(n-2k-j)!$$
$$=\frac {n!}{k}\frac {1}{k+j}$$
Similarly the other terms in the expression,
I understand that the overall aim here is to eliminate from the set of all permutations having a cycle of length $k$ , other unnecessary permutations having two cycles of length $k$ (because of overcounting) or cycles of length greater than $k$.
But I don't understand the actual interplay between the plus and minuses signs between the different terms in the expression and how does that help in leading to the general formula.
I am self studying and apologise for my seemingly confused way of writing.Thanks in advance .
$UPDATE :$ Here's one idea I have got after revisiting the theory today ..
Let $P(\underbrace{k,k,\ldots,k}_{t\text{-times}},k+j,k+l,...k+p) $ denote the set of permutations having some $t$ cycles of length $k$ and other cycles of length greater than $k$
Then if $\frac n4<k \le \frac n3$ , we have
$L_{k,n}=|P(k)|-|P(k,k+j)|+|P(k,k+j,k+l)|-\left \{ |P(k,k)|-|P(k,k,k+j)|-\big [ |P(k,k,k)| \big ] \right \} $
So the brackets are somehow going nested starting with $P(k),P(k,k)...$ in the expression along with the alternate signs as one goes within a chain of fixed number of cycles of length $k$ and increasing the number of cycles of length greater than $k$ along the chain .
OK I try writing out the $L_{k,n}$ for the case $\frac n5<k \le \frac n4$
$$L_{k,n}=|P(k)|-|P(k,k+j)|+|P(k,k+j,k+l)|-|P(k,k+j,k+l,k+m)|-\left \{ |P(k,k)|-|P(k,k,k+j)|+|P(k,k,k+j,k+l)|-\big [ |P(k,k,k)|- |P(k,k,k,k+j)| -|P(k,k,k,k)|\big ] \right \} $$
Which turns out to be matching with the formula provided in the linked text. So I guess my understanding is correct.
Now coming to the general formula , I think the upper bound for $j=\lfloor n/k \rfloor$ says how many maximum $k$ length cycles can be formed from the $n$ objects .
The expression $$\frac{1}{j!k^j}\frac{n!}{(n-kj)!}=\frac{\left \{(k-1) !\right \}^j}{j!}{n \choose k}{{n-k} \choose k}\dots {{n-kj+k} \choose k}$$
tells how many permutations on $n$ objects have $j$ cycles of length $k$
Now , for each of the above permutations (for a fixed $j$), the inner sum tells us how many permutations (on the remaining $(n-kj)$ objects )are there of greatest cycle length from $1$ upto $(k-1)$ or $(n-kj)$ whichever is smaller.
So the general formula gives us all permutations having a certain no of cycles each of length $k$ along with cycles of length shorter than $k$ thus giving all permutations having greatest cycle of length $k$
Suggestions ??