/

# Combinatorial¶

This module implements various combinatorial functions.

## bell¶

class sympy.functions.combinatorial.numbers.bell[source]

Bell numbers / Bell polynomials

The Bell numbers satisfy $$B_0 = 1$$ and

$B_n = \sum_{k=0}^{n-1} \binom{n-1}{k} B_k.$

They are also given by:

$B_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}.$

The Bell polynomials are given by $$B_0(x) = 1$$ and

$B_n(x) = x \sum_{k=1}^{n-1} \binom{n-1}{k-1} B_{k-1}(x).$

The second kind of Bell polynomials (are sometimes called “partial” Bell polynomials or incomplete Bell polynomials) are defined as

$B_{n,k}(x_1, x_2,\dotsc x_{n-k+1}) = \sum_{j_1+j_2+j_2+\dotsb=k \atop j_1+2j_2+3j_2+\dotsb=n} \frac{n!}{j_1!j_2!\dotsb j_{n-k+1}!} \left(\frac{x_1}{1!} \right)^{j_1} \left(\frac{x_2}{2!} \right)^{j_2} \dotsb \left(\frac{x_{n-k+1}}{(n-k+1)!} \right) ^{j_{n-k+1}}.$
• bell(n) gives the $$n^{th}$$ Bell number, $$B_n$$.
• bell(n, x) gives the $$n^{th}$$ Bell polynomial, $$B_n(x)$$.
• bell(n, k, (x1, x2, ...)) gives Bell polynomials of the second kind, $$B_{n,k}(x_1, x_2, \dotsc, x_{n-k+1})$$.

euler, bernoulli

Notes

Not to be confused with Bernoulli numbers and Bernoulli polynomials, which use the same notation.

References

Examples

>>> from sympy import bell, Symbol, symbols

>>> [bell(n) for n in range(11)]
[1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975]
>>> bell(30)
846749014511809332450147
>>> bell(4, Symbol('t'))
t**4 + 6*t**3 + 7*t**2 + t
>>> bell(6, 2, symbols('x:6')[1:])
6*x1*x5 + 15*x2*x4 + 10*x3**2


Attributes

 nargs

## bernoulli¶

class sympy.functions.combinatorial.numbers.bernoulli[source]

Bernoulli numbers / Bernoulli polynomials

The Bernoulli numbers are a sequence of rational numbers defined by B_0 = 1 and the recursive relation (n > 0):

      n
___
\      / n + 1 \
0 =  )     |       | * B .
/___   \   k   /    k
k = 0

They are also commonly defined by their exponential generating function, which is x/(exp(x) - 1). For odd indices > 1, the Bernoulli numbers are zero.

The Bernoulli polynomials satisfy the analogous formula:

          n
___
\      / n \         n-k
B (x) =  )     |   | * B  * x   .
n      /___   \ k /    k
k = 0

Bernoulli numbers and Bernoulli polynomials are related as B_n(0) = B_n.

We compute Bernoulli numbers using Ramanujan’s formula:

                         / n + 3 \
B   =  (A(n) - S(n))  /  |       |
n                       \   n   /

where A(n) = (n+3)/3 when n = 0 or 2 (mod 6), A(n) = -(n+3)/6 when n = 4 (mod 6), and:

       [n/6]
___
\      /  n + 3  \
S(n) =  )     |         | * B
/___   \ n - 6*k /    n-6*k
k = 1

This formula is similar to the sum given in the definition, but cuts 2/3 of the terms. For Bernoulli polynomials, we use the formula in the definition.

• bernoulli(n) gives the nth Bernoulli number, B_n
• bernoulli(n, x) gives the nth Bernoulli polynomial in x, B_n(x)

euler, bell

References

Examples

>>> from sympy import bernoulli

>>> [bernoulli(n) for n in range(11)]
[1, -1/2, 1/6, 0, -1/30, 0, 1/42, 0, -1/30, 0, 5/66]
>>> bernoulli(1000001)
0


Attributes

 nargs

## binomial¶

class sympy.functions.combinatorial.factorials.binomial[source]

Implementation of the binomial coefficient. It can be defined in two ways depending on its desired interpretation:

C(n,k) = n!/(k!(n-k)!) or C(n, k) = ff(n, k)/k!

First, in a strict combinatorial sense it defines the number of ways we can choose ‘k’ elements from a set of ‘n’ elements. In this case both arguments are nonnegative integers and binomial is computed using an efficient algorithm based on prime factorization.

The other definition is generalization for arbitrary ‘n’, however ‘k’ must also be nonnegative. This case is very useful when evaluating summations.

For the sake of convenience for negative ‘k’ this function will return zero no matter what valued is the other argument.

Examples

>>> from sympy import Symbol, Rational, binomial
>>> n = Symbol('n', integer=True)

>>> binomial(15, 8)
6435

>>> binomial(n, -1)
0

>>> [ binomial(0, i) for i in range(1)]
[1]
>>> [ binomial(1, i) for i in range(2)]
[1, 1]
>>> [ binomial(2, i) for i in range(3)]
[1, 2, 1]
>>> [ binomial(3, i) for i in range(4)]
[1, 3, 3, 1]
>>> [ binomial(4, i) for i in range(5)]
[1, 4, 6, 4, 1]

>>> binomial(Rational(5,4), 3)
-5/128

>>> binomial(n, 3)
n*(n - 2)*(n - 1)/6


## catalan¶

class sympy.functions.combinatorial.numbers.catalan[source]

Catalan numbers

The n-th catalan number is given by:

       1   / 2*n \
C  = ----- |     |
n   n + 1 \  n  /
• catalan(n) gives the n-th Catalan number, C_n

References

Examples

>>> from sympy import (Symbol, binomial, gamma, hyper, polygamma,
...             catalan, diff, combsimp, Rational, I)

>>> [ catalan(i) for i in range(1,10) ]
[1, 2, 5, 14, 42, 132, 429, 1430, 4862]

>>> n = Symbol("n", integer=True)

>>> catalan(n)
catalan(n)


Catalan numbers can be transformed into several other, identical expressions involving other mathematical functions

>>> catalan(n).rewrite(binomial)
binomial(2*n, n)/(n + 1)

>>> catalan(n).rewrite(gamma)
4**n*gamma(n + 1/2)/(sqrt(pi)*gamma(n + 2))

>>> catalan(n).rewrite(hyper)
hyper((-n + 1, -n), (2,), 1)


For some non-integer values of n we can get closed form expressions by rewriting in terms of gamma functions:

>>> catalan(Rational(1,2)).rewrite(gamma)
8/(3*pi)


We can differentiate the Catalan numbers C(n) interpreted as a continuous real funtion in n:

>>> diff(catalan(n), n)
(polygamma(0, n + 1/2) - polygamma(0, n + 2) + 2*log(2))*catalan(n)


As a more advanced example consider the following ratio between consecutive numbers:

>>> combsimp((catalan(n + 1)/catalan(n)).rewrite(binomial))
2*(2*n + 1)/(n + 2)


The Catalan numbers can be generalized to complex numbers:

>>> catalan(I).rewrite(gamma)
4**I*gamma(1/2 + I)/(sqrt(pi)*gamma(2 + I))


and evaluated with arbitrary precision:

>>> catalan(I).evalf(20)
0.39764993382373624267 - 0.020884341620842555705*I


Attributes

 nargs

## euler¶

class sympy.functions.combinatorial.numbers.euler[source]

Euler numbers

The euler numbers are given by:

        2*n+1   k
___   ___            j          2*n+1
\     \     / k \ (-1)  * (k-2*j)
E   = I  )     )    |   | --------------------
2n     /___  /___  \ j /      k    k
k = 1 j = 0           2  * I  * k

E     = 0
2n+1
• euler(n) gives the n-th Euler number, E_n

bernoulli, bell

References

Examples

>>> from sympy import Symbol, euler
>>> [euler(n) for n in range(10)]
[1, 0, -1, 0, 5, 0, -61, 0, 1385, 0]
>>> n = Symbol("n")
>>> euler(n+2*n)
euler(3*n)


## factorial¶

class sympy.functions.combinatorial.factorials.factorial[source]

Implementation of factorial function over nonnegative integers. For the sake of convenience and simplicity of procedures using this function it is defined for negative integers and returns zero in this case.

The factorial is very important in combinatorics where it gives the number of ways in which ‘n’ objects can be permuted. It also arises in calculus, probability, number theory etc.

There is strict relation of factorial with gamma function. In fact n! = gamma(n+1) for nonnegative integers. Rewrite of this kind is very useful in case of combinatorial simplification.

Computation of the factorial is done using two algorithms. For small arguments naive product is evaluated. However for bigger input algorithm Prime-Swing is used. It is the fastest algorithm known and computes n! via prime factorization of special class of numbers, called here the ‘Swing Numbers’.

factorial2, RisingFactorial, FallingFactorial

Examples

>>> from sympy import Symbol, factorial
>>> n = Symbol('n', integer=True)

>>> factorial(-2)
0

>>> factorial(0)
1

>>> factorial(7)
5040

>>> factorial(n)
n!

>>> factorial(2*n)
(2*n)!


## factorial2 / double factorial¶

class sympy.functions.combinatorial.factorials.factorial2[source]

The double factorial n!!, not to be confused with (n!)!

The double factorial is defined for integers >= -1 as:

         ,
|  n*(n - 2)*(n - 4)* ... * 1    for n odd
n!! =  -|  n*(n - 2)*(n - 4)* ... * 2    for n even
|  1                             for n = 0, -1
'

factorial, RisingFactorial, FallingFactorial

Examples

>>> from sympy import factorial2, var
>>> var('n')
n
>>> factorial2(n + 1)
(n + 1)!!
>>> factorial2(5)
15
>>> factorial2(-1)
1


## FallingFactorial¶

class sympy.functions.combinatorial.factorials.FallingFactorial[source]

Falling factorial (related to rising factorial) is a double valued function arising in concrete mathematics, hypergeometric functions and series expansions. It is defined by

ff(x, k) = x * (x-1) * ... * (x - k+1)

where ‘x’ can be arbitrary expression and ‘k’ is an integer. For more information check “Concrete mathematics” by Graham, pp. 66 or visit http://mathworld.wolfram.com/FallingFactorial.html page.

>>> from sympy import ff
>>> from sympy.abc import x

>>> ff(x, 0)
1

>>> ff(5, 5)
120

>>> ff(x, 5) == x*(x-1)*(x-2)*(x-3)*(x-4)
True


factorial, factorial2, RisingFactorial

## fibonacci¶

class sympy.functions.combinatorial.numbers.fibonacci[source]

Fibonacci numbers / Fibonacci polynomials

The Fibonacci numbers are the integer sequence defined by the initial terms F_0 = 0, F_1 = 1 and the two-term recurrence relation F_n = F_{n-1} + F_{n-2}.

The Fibonacci polynomials are defined by F_1(x) = 1, F_2(x) = x, and F_n(x) = x*F_{n-1}(x) + F_{n-2}(x) for n > 2. For all positive integers n, F_n(1) = F_n.

• fibonacci(n) gives the nth Fibonacci number, F_n
• fibonacci(n, x) gives the nth Fibonacci polynomial in x, F_n(x)

lucas

References

Examples

>>> from sympy import fibonacci, Symbol

>>> [fibonacci(x) for x in range(11)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> fibonacci(5, Symbol('t'))
t**4 + 3*t**2 + 1


Attributes

 nargs

## harmonic¶

class sympy.functions.combinatorial.numbers.harmonic[source]

Harmonic numbers

The nth harmonic number is given by 1 + 1/2 + 1/3 + ... + 1/n.

More generally:

         n
___
\       -m
H    =  )     k   .
n,m   /___
k = 1

As n -> oo, H_{n,m} -> zeta(m) (the Riemann zeta function)

• harmonic(n) gives the nth harmonic number, H_n
• harmonic(n, m) gives the nth generalized harmonic number of order m, H_{n,m}, where harmonic(n) == harmonic(n, 1)

References

Examples

>>> from sympy import harmonic, oo

>>> [harmonic(n) for n in range(6)]
[0, 1, 3/2, 11/6, 25/12, 137/60]
>>> [harmonic(n, 2) for n in range(6)]
[0, 1, 5/4, 49/36, 205/144, 5269/3600]
>>> harmonic(oo, 2)
pi**2/6


## lucas¶

class sympy.functions.combinatorial.numbers.lucas[source]

Lucas numbers

Lucas numbers satisfy a recurrence relation similar to that of the Fibonacci sequence, in which each term is the sum of the preceding two. They are generated by choosing the initial values L_0 = 2 and L_1 = 1.

• lucas(n) gives the nth Lucas number

fibonacci

References

Examples

>>> from sympy import lucas

>>> [lucas(x) for x in range(11)]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123]


Attributes

 nargs

## MultiFactorial¶

class sympy.functions.combinatorial.factorials.MultiFactorial[source]

Attributes

 nargs

## RisingFactorial¶

class sympy.functions.combinatorial.factorials.RisingFactorial[source]

Rising factorial (also called Pochhammer symbol) is a double valued function arising in concrete mathematics, hypergeometric functions and series expansions. It is defined by:

rf(x, k) = x * (x+1) * ... * (x + k-1)

where ‘x’ can be arbitrary expression and ‘k’ is an integer. For more information check “Concrete mathematics” by Graham, pp. 66 or visit http://mathworld.wolfram.com/RisingFactorial.html page.

factorial, factorial2, FallingFactorial

Examples

>>> from sympy import rf
>>> from sympy.abc import x

>>> rf(x, 0)
1

>>> rf(1, 5)
120

>>> rf(x, 5) == x*(1 + x)*(2 + x)*(3 + x)*(4 + x)
True