Partition function (number theory): Difference between revisions

Revision as of 14:07, 14 February 2023

Revision as of 14:08, 14 February 2023

Line 1:

{{Short description|The number of partitions of an integer}}

== Python(3.9) code to calculate p(n) ==

Partition theory is a branch of mathematics that deals with the study of partitions of integers. A partition of an integer <code>n</code> is a non-increasing sequence of positive integers that add up to <code>n</code>. For example, the partitions of 4 are: <code>4</code>, <code>3 + 1</code>, <code>2 + 2</code>, <code>2 + 1 + 1</code>, and <code>1 + 1 + 1 + 1</code>.

In this article, we'll look at a Python code that calculates the number of partitions of an integer <code>n</code>. The code uses a recursive approach and memorization to optimize the calculation.

Here's the code:<syntaxhighlight lang="python3" line="1">

import sys

sys.setrecursionlimit(5000) #increase the maximum recursion depth

def partitions(n):

def partition_helper(n, m, memo={}):

if n == 0:

return 1

if n < 0 or m == 0:

return 0

if (n, m) in memo:

return memo[(n, m)]

memo[(n, m)] = partition_helper(n - m, m, memo) + partition_helper(n, m - 1, memo)

return memo[(n, m)]

return partition_helper(n, n)

# Example usage:

print(partitions(4)) # Output: 5

</syntaxhighlight>The <code>partitions</code> function takes an integer <code>n</code> as input and returns the number of partitions of <code>n</code>. The function uses a recursive helper function <code>partition_helper</code> to calculate the number of partitions. The <code>partition_helper</code> function takes three inputs: <code>n</code> (the integer being partitioned), <code>m</code> (the current number being used to partition <code>n</code>), and <code>memo</code> (a dictionary to store the intermediate results).

The function starts by checking if <code>n</code> is 0. If <code>n</code> is 0, it returns 1, as there is only 1 way to partition 0 (into 0 parts). If <code>n</code> is less than 0 or <code>m</code> is 0, it returns 0, as there are no valid partitions in these cases.

Next, the function checks if the current values of <code>n</code> and <code>m</code> are stored in the <code>memo</code> dictionary. If they are, it returns the stored result. This is the memoization step, which speeds up the calculation by avoiding redundant computations.

If <code>n</code> and <code>m</code> are not in the <code>memo</code> dictionary, the function calculates the number of partitions using the following formula:<syntaxhighlight lang="python3">

partitions(n, m) = partitions(n - m, m) + partitions(n, m - 1)

</syntaxhighlight>This formula says that the number of partitions of <code>n</code> with the largest part <code>m</code> is equal to the number of partitions of <code>n</code> with the largest part <code>m</code> minus 1, plus the number of partitions of <code>n - m</code> with the largest part <code>m</code>.

The intermediate results are stored in the <code>memo</code> dictionary for future use, and the result is returned.

This code demonstrates a classic example of dynamic programming, where a problem is broken down into smaller sub-problems and the intermediate results are stored to avoid redundant computations. The use of memoization in the <code>partition_helper</code> function makes the code efficient and fast.

In conclusion, this Python code provides a simple and efficient way to calculate the number of partitions of an integer <code>n</code>. The code uses dynamic{{Short description|The number of partitions of an integer}}

[[File:Ferrer partitioning diagrams.svg|thumb|The values <math>p(1), \dots, p(8)</math> of the partition function (1, 2, 3, 5, 7, 11, 15, and 22) can be determined by counting the [[Young diagram]]s for the partitions of the numbers from 1 to 8.]]

In [[number theory]], the '''partition function''' {{math|''p''(''n'')}} represents the [[number]] of possible [[Partition (number theory)|partitions]] of a non-negative integer {{mvar|n}}. For instance, {{math|1=''p''(4) = 5}} because the integer 4 has the five partitions {{math|1 + 1 + 1 + 1}}, {{math|1 + 1 + 2}}, {{math|1 + 3}}, {{math|2 + 2}}, and {{math|4}}.