NZMATH  1.2.0
About: NZMATH is a Python based number theory oriented calculation system.
  Fossies Dox: NZMATH-1.2.0.tar.gz  ("inofficial" and yet experimental doxygen-generated source code documentation)  

nzmath.combinatorial Namespace Reference

Classes

class  LimitedMaximumPartitionDriver
 
class  OddMaximumPartitionDriver
 
class  OddPartitionDriver
 
class  PartitionDriver
 

Functions

def binomial (n, m)
 
def factorial (n)
 
def bernoulli (n)
 
def catalan (n)
 
def euler (n)
 
def fallingfactorial (n, m)
 
def risingfactorial (n, m)
 
def multinomial (n, parts)
 
def stirling1 (n, m)
 
def stirling2 (n, m)
 
def stirling2_negative (n, m)
 
def bell (n)
 
def combination_index_generator (n, m)
 
def permutation_generator (n)
 
def dyck_word_generator (n, alphabet=(0, 1))
 
def partition_generator (n, maxi=None)
 
def partition_into_odd_generator (n, maxi=None)
 
def partition_numbers_upto (n)
 
def _pentagonal ()
 
def partition_number (n)
 
def partition_conjugate (partition)
 

Variables

def combinationIndexGenerator = combination_index_generator
 
def partitionGenerator = partition_generator
 
def permutationGenerator = permutation_generator
 
def DyckWordGenerator = dyck_word_generator
 

Detailed Description

Combinatorial functions

Function Documentation

◆ _pentagonal()

def nzmath.combinatorial._pentagonal ( )
private
Generates pentagonal and skew pentagonal numbers.
(1, 2, 5, 7, 12, 15, ...)

Definition at line 668 of file combinatorial.py.

Referenced by nzmath.combinatorial.partition_numbers_upto().

◆ bell()

def nzmath.combinatorial.bell (   n)
Bell number.

The Bell number b is defined by:
  b(n) = \sum_{i=0}^{n} S(n, i)
where S denotes Stirling number of the second kind.

Definition at line 253 of file combinatorial.py.

References nzmath.bigrange.range(), and nzmath.combinatorial.stirling2().

◆ bernoulli()

def nzmath.combinatorial.bernoulli (   n)
Return n-th Bernoulli number.

Definition at line 64 of file combinatorial.py.

References nzmath.combinatorial.binomial(), and nzmath.bigrange.range().

◆ binomial()

def nzmath.combinatorial.binomial (   n,
  m 
)
The binomial coefficient.
binomial(n, m) returns n ! / ((n - m) ! * m !).

n must be a positive integer and m must be a non-negative integer.
For convinience, binomial(n, n+i) = 0 for positive i, and
binomial(0,0) = 1.

In other cases, it raises an exception.

Definition at line 10 of file combinatorial.py.

References nzmath.bigrange.range().

Referenced by nzmath.combinatorial.bernoulli(), nzmath.combinatorial.catalan(), nzmath.combinatorial.euler(), nzmath.combinatorial.multinomial(), and nzmath.combinatorial.stirling1().

◆ catalan()

def nzmath.combinatorial.catalan (   n)
Return n-th Catalan number.

Definition at line 79 of file combinatorial.py.

References nzmath.combinatorial.binomial().

◆ combination_index_generator()

def nzmath.combinatorial.combination_index_generator (   n,
  m 
)
Generate indices of m elment subsets of n element set.

The number of generated indices is binomial(n, m).

For example,
combinationIndexGenerator(5,3) generates the following lists:
    [0, 1, 2]
    [0, 1, 3]
    [0, 1, 4]
    [0, 2, 3]
    [0, 2, 4]
    [0, 3, 4]
    [1, 2, 3]
    [1, 2, 4]
    [1, 3, 4]
    [2, 3, 4]

Definition at line 265 of file combinatorial.py.

References nzmath.bigrange.range().

◆ dyck_word_generator()

def nzmath.combinatorial.dyck_word_generator (   n,
  alphabet = (0, 1) 
)
Generate all Dyck words of length 2*n as tuples.

The Dyck words are words on a two character alphabet.
The number of each character in a word is equal, 
and the number of the second character never exceeds the first
in any initial parts of the word.

The number of generated words is the n-th Catalan number.

The alphabet is {0, 1} by default, but you can pass it into the
optional argument 'alphabet'.

For example,
>>> for word in dyck_word_generator(3, alphabet=("(", ")")):
...     print "".join(word)
... 
()()()
()(())
(())()
(()())
((()))
>>> 

Definition at line 340 of file combinatorial.py.

References nzmath.bigrange.range().

◆ euler()

def nzmath.combinatorial.euler (   n)
Return n-th Euler number.

Definition at line 85 of file combinatorial.py.

References nzmath.combinatorial.binomial(), and nzmath.bigrange.range().

◆ factorial()

def nzmath.combinatorial.factorial (   n)

◆ fallingfactorial()

def nzmath.combinatorial.fallingfactorial (   n,
  m 
)
Return the falling factorial; n to the m falling, i.e. n(n-1)..(n-m+1).

For Example:
>>> fallingfactorial(7, 3)
210

Definition at line 96 of file combinatorial.py.

References nzmath.bigrange.range().

◆ multinomial()

def nzmath.combinatorial.multinomial (   n,
  parts 
)
Return multinomial coefficient.

parts MUST be a sequence of natural numbers and n==sum(parts) holds.

Definition at line 122 of file combinatorial.py.

References nzmath.combinatorial.binomial(), and nzmath.combinatorial.factorial().

◆ partition_conjugate()

def nzmath.combinatorial.partition_conjugate (   partition)
Return the conjugate partition of 'partition'.

For example:
>>> partition_conjugate((5, 3, 1))
(3, 2, 2, 1, 1)

Definition at line 685 of file combinatorial.py.

◆ partition_generator()

def nzmath.combinatorial.partition_generator (   n,
  maxi = None 
)
Generate partitions of n.
If maxi is given, then parts are limited to at most maxi.

Definition at line 391 of file combinatorial.py.

◆ partition_into_odd_generator()

def nzmath.combinatorial.partition_into_odd_generator (   n,
  maxi = None 
)

Definition at line 642 of file combinatorial.py.

◆ partition_number()

def nzmath.combinatorial.partition_number (   n)
Return the partition number for '''n'''.

Definition at line 679 of file combinatorial.py.

References nzmath.combinatorial.partition_numbers_upto().

◆ partition_numbers_upto()

def nzmath.combinatorial.partition_numbers_upto (   n)
Return the partition numbers for 0 to '''n''' (inclusive).

Definition at line 651 of file combinatorial.py.

References nzmath.combinatorial._pentagonal(), and nzmath.bigrange.range().

Referenced by nzmath.combinatorial.partition_number().

◆ permutation_generator()

def nzmath.combinatorial.permutation_generator (   n)
Generate all permutations of n elements as lists.

The number of generated lists is n!, so be careful to use big n.

For example,
permutationGenerator(3) generates the following lists:
    [0, 1, 2]
    [0, 2, 1]
    [1, 0, 2]
    [1, 2, 0]
    [2, 0, 1]
    [2, 1, 0]

Definition at line 298 of file combinatorial.py.

References nzmath.bigrange.range().

◆ risingfactorial()

def nzmath.combinatorial.risingfactorial (   n,
  m 
)
Return the rising factorial; n to the m rising, i.e. n(n+1)..(n+m-1).

For example:
>>> risingfactorial(7, 3)
504

Definition at line 109 of file combinatorial.py.

References nzmath.bigrange.range().

◆ stirling1()

def nzmath.combinatorial.stirling1 (   n,
  m 
)
Stirling number of the first kind.

Let s denote the Stirling number, (x)_n falling factorial, then
  (x)_n = \sum_{i=0}^{n} s(n, i) * x**i
and s satisfies the recurrence relation:
  s(n, m) = s(n-1, m-1) - (n-1)*s(n-1, m)

Definition at line 143 of file combinatorial.py.

References nzmath.combinatorial.binomial(), nzmath.combinatorial.factorial(), and nzmath.bigrange.range().

◆ stirling2()

def nzmath.combinatorial.stirling2 (   n,
  m 
)
Stirling number of the second kind.

Let S denote the Stirling number, (x)_i falling factorial, then:
  x**n = \sum_{i=0}^{n} S(n, i) * (x)_i
S satisfies:
  S(n, m) = S(n-1, m-1) + m*S(n-1, m)

Definition at line 182 of file combinatorial.py.

References nzmath.combinatorial.factorial(), and nzmath.combinatorial.stirling2_negative().

Referenced by nzmath.combinatorial.bell(), and nzmath.combinatorial.stirling2_negative().

◆ stirling2_negative()

def nzmath.combinatorial.stirling2_negative (   n,
  m 
)
Stiring number of the second kind extended to negative numbers.

Let S# denote the extended Stirling number, S the original, then
S#(n, m) = S(-m, -n) and extended by the recurrence relation:
  S#(n, m) = S#(n-1, m-1) + (n-1)*S#(n-1, m)

Definition at line 220 of file combinatorial.py.

References nzmath.combinatorial.factorial(), nzmath.bigrange.range(), and nzmath.combinatorial.stirling2().

Referenced by nzmath.combinatorial.stirling2().

Variable Documentation

◆ combinationIndexGenerator

def nzmath.combinatorial.combinationIndexGenerator = combination_index_generator

Definition at line 705 of file combinatorial.py.

◆ DyckWordGenerator

def nzmath.combinatorial.DyckWordGenerator = dyck_word_generator

Definition at line 708 of file combinatorial.py.

◆ partitionGenerator

def nzmath.combinatorial.partitionGenerator = partition_generator

Definition at line 706 of file combinatorial.py.

◆ permutationGenerator

def nzmath.combinatorial.permutationGenerator = permutation_generator

Definition at line 707 of file combinatorial.py.