Number of partitions of an integer

AUTHOR:

  • William Stein (2007-07-28): initial version
  • Jonathan Bober (2007-07-28): wrote the program partitions_c.cc that does all the actual heavy lifting.
sage.combinat.partitions.ZS1_iterator(n)

A fast iterator for the partitions of n (in the decreasing lexicographic order) which returns lists and not objects of type Partition.

This is an implementation of the ZS1 algorithm found in [ZS98].

REFERENCES:

[ZS98]Antoine Zoghbi, Ivan Stojmenovic, Fast Algorithms for Generating Integer Partitions, Intern. J. Computer Math., Vol. 70., pp. 319–332. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.1287

EXAMPLES:

sage: from sage.combinat.partitions import ZS1_iterator
sage: it = ZS1_iterator(4)
sage: next(it)
[4]
sage: type(_)
<... 'list'>
sage.combinat.partitions.ZS1_iterator_nk(n, k)

An iterator for the partitions of n of length at most k (in the decreasing lexicographic order) which returns lists and not objects of type Partition.

The algorithm is a mild variation on ZS1_iterator(); I would not vow for its speed.

EXAMPLES:

sage: from sage.combinat.partitions import ZS1_iterator_nk
sage: it = ZS1_iterator_nk(4, 3)
sage: next(it)
[4]
sage: type(_)
<... 'list'>
sage.combinat.partitions.number_of_partitions(n)

Returns the number of partitions of the integer \(n\).

EXAMPLES:

sage: from sage.combinat.partitions import number_of_partitions
sage: number_of_partitions(0)
1
sage: number_of_partitions(1)
1
sage: number_of_partitions(2)
2
sage: number_of_partitions(3)
3
sage: number_of_partitions(10)
42
sage: number_of_partitions(40)
37338
sage: number_of_partitions(100)
190569292
sage: number_of_partitions(100000)
27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519
sage.combinat.partitions.run_tests(longtest=False, forever=False)

Test Bober’s algorithm.

EXAMPLES:

sage: from sage.combinat.partitions import run_tests
sage: run_tests(False, False)
Computing p(1)... OK.
...
Done.