Content deleted Content added
Category:Number theory |
m minor formatting |
||
Line 3:
One way of getting a handle on the partition function involves an intermediate function p(''k'',''n'') which represents the number of partitions of ''n'' using only natural numbers at least as large as ''k''. For any given value of ''k'', partitions counted by p(''k'',''n'') fit into exactly one of the following categories:
▲2. smallest addend is strictly greater than ''k''
The number of partitions meeting the first condition is p(''k'',''n''-''k''). To see this, imagine a list of all the partitions of the number ''n''-''k'' into numbers of size at least ''k'', then imagine appending "+''k''" to each partition in the list. Now what is it a list of?
Line 30 ⟶ 29:
An alternative computation of the partition function involves [[generating function|generating functions]]. Consider the infinite product
:<math>\prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right) </math>
Expanding each term as a [[geometric series]], we can rewrite it as
:(1 + <i>x</i> + <i>x</i><sup>2</sup> + <i>x</i><sup>3</sup> + ...)(1 + <i>x</i><sup>2</sup> + <i>x</i><sup>4</sup> + <i>x</i><sup>6</sup> + ...)(1 + <i>x</i><sup>3</sup> + <i>x</i><sup>6</sup> + <i>x</i><sup>9</sup> + ...) ...
The <i>x</i><sup>m</sup> term in this product counts the number of ways to write
:<i>n</i> = <i>a</i><sub>1</sub> + 2<i>a</i><sub>2</sub> + 3<i>a</i><sub>3</sub> + ... = (1 + 1 + 1 + 1 + ...) + (2 + 2 + 2 + 2 + ...) + (3 + 3 + 3 ...) + ...,
where each number <i>i</i> appears <i>a</i><sub>i</sub> times. This is precisely the definition of a partition of <i>n</i>, so our product is the desired generating function. More generally, the generating function for the partitions of <i>n</i> into numbers from a set <i>A</i> can be found by taking only those terms in the product where <i>k</i> is an element of <i>A</i> This result is due to [[Leonhard Euler|Euler]]
| |||