On Relations between Partition Classes with a Restricted Number of Parts

Abstract

This paper investigates relations between classes of partitions of a positive integer n with restricted number of parts. The main focus is on partitions into exactly k distinct odd parts. To relate this class of partitions to those with restricted part size, we employ conjugation of Young diagrams. This allows one to construct an explicit bijection and prove that the number of such partitions r(n, k) exactly equals P((n−k²)/2, k) for n ≡ k (mod 2) and n ≥ k², where the parts of the latter do not exceed k. Using this relation, we compare the asymptotic behavior of the partition functions r(n, k), p(n, k) - the number of partitions of n into exactly k parts, and q(n, k) - the number of partitions of n into k distinct parts. For k = O(n^(1/3)), it is proved that the ratios q(n,k)/r(n,k) and p(n,k)/r(n,k) asymptotically tend to 2^(k−1) as n → ∞. For the numerical verification of the obtained theorems, two algorithms based on dynamic programming are implemented. The first algorithm relies on the recurrence relation for counting partitions into distinct odd parts r(n, k). The second one relies on the proved bijection and the recurrence formula for the number of partitions P(m, k) whose parts do not exceed k. Computational experiments show that the algorithm based on the established bijection provides a significant performance gain as n increases. The developed algorithms are also applied to verify the Kargapolov conjecture concerning the ranks of the group of central units of the integer group ring of the alternating group A_n, which are related to partitions into distinct odd parts under additional constraints. Computations performed up to n = 100000 confirm the asymptotic behavior, with a relative error below 0.1%.