The Network Of Knowledge

                Science   Technology   Engineering   Mathematics   History   Thought   Belief   The Modern World
                

                        Omnia Exeunt In Mysterium

Restricted Partition Functions

A restricted partition function is partition function for which there is some restriction on the size of the parts, the number of parts, the form of the parts, etc., etc. Some types of restricted partition functions have been described on other pages, including self-conjugate partitions, gap-frequency partitions, k-regular partitions, lecture hall partitions, partitions with initial repetitions and t-core partitions.

Some of these restricted partition functions occur naturally in pairs, with the number of partitions of an integer $n$ counted by one function being equinumerous with the number of partitions of $n$ counted by the other function.

One classical example of such pair of functions is $(p_{\mathcal{O}}(n), p_{\mathcal{D}}(n))$, where $p_{\mathcal{O}}(n)$ denotes the number of partitions of $n$ into odd parts, and $p_{\mathcal{D}}(n)$ denotes the number of partitions of $n$ into distinct parts. The fact that $p_{\mathcal{O}}(n)= p_{\mathcal{D}}(n)$ for all non-negative integers (an identity stated by Euler) follows from an identity between the generating functions: \[ \sum_{n=0}^{\infty}p_{\mathcal{D}}(n)q^n = \prod_{k=1}^{\infty}(1+q^k)=\frac{\prod_{k=1}^{\infty}(1-q^{2k})}{\prod_{k=1}^{\infty}(1-q^k)} =\frac{1}{\prod_{k=1}^{\infty}(1-q^{2k-1})}=\sum_{n=0}^{\infty}p_{\mathcal{O}}(n)q^n. \]

Other restricted partition function pairs $(rp_1(n),rp_2(n))$ such that $rp_1(n)=rp_2(n)$ for all non-negative integers $n$ (which can shown by either demonstrating that the generating functions are equal through algebraic/analytic manipulation, or by finding a bijection between the two types of partition) include the pairs of such functions that count

- partitions into distinct parts, and partitions in which all parts from 1 to the largest part appear at least once;

- k-regular partitions, and partitions in which no part appears more than $k-1$ times;

- self-conjugate partitions , and partitions into distinct odd parts;

- the pairs of restricted partition functions whose generating functions are represented by the $q$-series and $q$-products on each side of the The Göllnitz-Gordon Identities;

- the pairs of restricted partition functions whose generating functions are represented by the $q$-series and $q$-products on each side of the The Rogers-Ramanujan Identities;

- more generally, the pairs of restricted partition functions whose generating functions are represented by the $q$-series and $q$-products on each side of an identity of Rogers-Ramanujan-Slater type;

- partitions in which the largest part has size $k$ (for a fixed positive integer $k$), and partitions into exactly $k$ parts;

One of the restricted partition functions encoded in one side of one of The Rogers-Ramanujan Identities counts partitions into super-distinct parts, that is, partitions into distinct parts in which consecutive parts differ by at least two.
Bressoud [B1] showed that such partitions were equinumerous with partitions into distinct parts in which the smallest even part is greater that $2 \times$ (number of odd parts).

Of course it is easy to create restricted partition functions that are not part of a pair of such functions in the manner described above, or at least not in any natural, non-trivial manner. One could consider partition functions in which the parts (or multiplicities) are restricted to belong to various families of positive integers such as the primes, the Fibonacci numbers, squares or other powers, the Catalan numbers, etc., etc.

One such partition function is the binary partition function, in which parts are restricted to be powers of 2. Let $b(n)$ denote the number of partitions of $n$ into powers of 2. Churchouse [C1] conjecture that if $n$ is any odd positive integer, then \[ b(2^{r+2}n) − b(2^rn) \equiv 0 (\mod 2^{\lfloor 3r/2\rfloor +2}),\quad \forall \, r \geq 1, \] and that the result is exact, in that no higher power of 2 divides the left side. This result was first proved by Rødseth in [O1], where he also considered $m$-ary partitions, which are partitions into parts that are powers of an integer $m \geq 2$.

Many other classes of restricted partition functions have been the subject of study in the mathematical literature.

[B1] Bressoud, D. M. A new family of partition identities. Pacific J. Math. 77 (1978), no. 1, 71–74.

[C1] Churchhouse, R. F. Congruence properties of the binary partition function, Proc. Camb. Phil. Soc. 66 (1969), 371–376.

[O1] Rødseth, Ø. J. Some arithmetical properties of m-ary partitions, Proc. Camb. Phil. Soc. 68 (1970), 447–453.

Back to the main Partitions page

Page created by Oideachas, LLC