Generalizing the recursion relationship for the partition function (Q1369681): Difference between revisions

The recurrence relation referred to in the title is \[ p(n)= {1\over n} \sum^n_{r= 1}\sigma(r) p(n-r),\tag{1} \] where \(p\) is the partition function and \(\sigma\) is the divisor sum function. Let \(\phi_r(q)= (1-q)(1- q^2)\dots(1- q^r)\), \(\phi_0(q)= 1\). For a partition \(\mu= 1^{\mu_1}2^{\mu_2}\dots\) of \(n\), define \[ b_\mu(q)= \prod_i \phi_{\mu_i}(q)\quad\text{and} \quad P_1(n,q)= \sum_\mu {1\over b_\mu(q^{-1})}, \] where the sum is over all partitions \(\mu\) of \(n\). Let \[ H_i(n, q)=\sum_{d|n} {n\over d} {1\over 1-q^{-d}}. \] Then it is shown that \[ P_1(n, q)={1\over n} \sum^n_{r=1} H_1(r,q) P_1(n-r,q).\tag{2} \] Letting \(q\to\infty\) gives (1). (2) in turn is generalised to \(P_g(n,q)\), and similar results are obtained for the function \(M_g(n, q)\), the number of classes of ordered \(g\)-tuples of \(n\times n\) matrices over \(\text{GF}(q)\) up to simultaneous similarity, giving a recurrence relation similar to (2) which reduces to (1) when \(q=1\).