Find closed form formula for $c(n,n-4)$.

Question

Find closed form formula for $c(n,n-4)$.

Where $c(n,k)$ are signless stirling numbers of first kind.

I need help.This is my last question all others problems of my exercise I have solved this is last one please help me.

Thanks.

Answer 1

Here is a solution by generating functions for verification purpose until something simpler appears.

Observe that there cannot be a cycle of length at least six because that leaves $n-6$ items which can form at most $n-6$ cycles for a total of $n-5$ cycles. Similarly for a cycle of length seven and so on.

The species of permutations with cycles of length at most five is is $$\mathfrak{P} (\mathcal{A}_1 \mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{A}_2 \mathfrak{C}_{=2}(\mathcal{Z}) + \cdots + \mathcal{A}_5 \mathfrak{C}_{=5}(\mathcal{Z})).$$

This gives the generating function $$G(z) = \exp\left(\sum_{q=1}^5 a_q \frac{z^q}{q}\right) = \prod_{q=1}^5 \exp\left( a_q \frac{z^q}{q} \right).$$

Now there are several cases.

First case.
A five-cycle and $n-5$ fixed points. This gives the generating function $$\frac{1}{(n-5)!} \left(\frac{z}{1}\right)^{n-5} \exp\left(a_2 \frac{z^2}{2}\right) \exp\left(a_3 \frac{z^3}{3}\right) \exp\left(a_4 \frac{z^4}{4}\right) \frac{1}{1} \left(\frac{z^5}{5}\right)^1.$$ We can drop the contributions in $a_2, a_3, a_4$ as no such cycles appear because there aren't any items left over, for an answer of $$\frac{1}{(n-5)!} \left(\frac{z}{1}\right)^{n-5} \left(\frac{z^5}{5}\right)^1.$$

Second case.
A four-cycle, a two-cycle and $n-6$ fixed points, for a contribution of $$\frac{1}{(n-6)!} \left(\frac{z}{1}\right)^{n-6} \left(\frac{z^2}{2}\right)^1 \left(\frac{z^4}{4}\right)^1.$$

Third case. Two three-cycles and $n-6$ fixed points, for a contribution of $$\frac{1}{(n-6)!}\left(\frac{z}{1}\right)^{n-6} \frac{1}{2} \left(\frac{z^3}{3}\right)^2.$$

Fourth case. A three-cycle, two two-cycles and $n-7$ fixed points for a contribution of $$\frac{1}{(n-7)!} \left(\frac{z}{1}\right)^{n-7} \frac{1}{2} \left(\frac{z^2}{2}\right)^2 \left(\frac{z^3}{3}\right)^1.$$

Fifth case. Four two-cycles and $n-8$ fixed points for a contribution of $$\frac{1}{(n-8)!}\left(\frac{z}{1}\right)^{n-8} \frac{1}{24} \left(\frac{z^2}{2}\right)^4.$$

Adding the contributions from these generating functions we obtain $$\frac{z^n}{(n-5)!} \times \left(\frac{1}{5} + \frac{n-5}{8} + \frac{n-5}{18} + \frac{(n-5)(n-6)}{24} + \frac{(n-5)(n-6)(n-7)}{384} \right) \\ = \frac{z^n}{(n-5)!} \times \left(\frac{1}{384} n^3 - \frac{1}{192} n^2 + \frac{1}{1152} n + \frac{1}{2880}\right).$$

Performing coefficient extraction on this we obtain the answer $$n! [z^n] \frac{z^n}{(n-5)!} \times \left(\frac{1}{384} n^3 - \frac{1}{192} n^2 + \frac{1}{1152} n + \frac{1}{2880}\right) \\ = \frac{n!}{(n-5)!} \left(\frac{1}{384} n^3 - \frac{1}{192} n^2 + \frac{1}{1152} n + \frac{1}{2880}\right).$$