Combinatorial Functions¶

This module implements some combinatorial functions, as listed below. For a more detailed description, see the relevant docstrings.

Sequences:

Set-theoretic constructions:

Warning

The following functions are deprecated and will soon be removed.

Partitions:

• Partitions of a set, partitions_set(), number_of_partitions_set(). An unordered partition of set S is a set of pairwise disjoint nonempty sets with union S and is represented by a sorted list of such sets.
• Partitions of an integer, Partitions(). An unordered partition of n is an unordered sum $$n = p_1+p_2 +\ldots+ p_k$$ of positive integers and is represented by the list $$p = [p_1,p_2,\ldots,p_k]$$, in nonincreasing order, i.e., $$p1\geq p_2 ...\geq p_k$$.
• Ordered partitions of an integer, ordered_partitions(), number_of_ordered_partitions(). An ordered partition of n is an ordered sum $$n = p_1+p_2 +\ldots+ p_k$$ of positive integers and is represented by the list $$p = [p_1,p_2,\ldots,p_k]$$, in nonincreasing order, i.e., $$p1\geq p_2 ...\geq p_k$$.
• partitions_greatest() implements a special type of restricted partition.
• partitions_greatest_eq() is another type of restricted partition.
• Tuples of partitions, PartitionTuples. A $$k$$-tuple of partitions is represented by a list of all $$k$$-tuples of partitions which together form a partition of $$n$$.

Related functions:

Implemented in other modules (listed for completeness):

The sage.rings.arith module contains the following combinatorial functions:

• binomial the binomial coefficient (wrapped from PARI)
• factorial (wrapped from PARI)
• partition (from the Python Cookbook) Generator of the list of all the partitions of the integer $$n$$.
• number_of_partitions() (wrapped from PARI) the number of partitions:
• falling_factorial() Definition: for integer $$a \ge 0$$ we have $$x(x-1) \cdots (x-a+1)$$. In all other cases we use the GAMMA-function: $$\frac {\Gamma(x+1)} {\Gamma(x-a+1)}$$.
• rising_factorial() Definition: for integer $$a \ge 0$$ we have $$x(x+1) \cdots (x+a-1)$$. In all other cases we use the GAMMA-function: $$\frac {\Gamma(x+a)} {\Gamma(x)}$$.
• gaussian_binomial the gaussian binomial
$\binom{n}{k}_q = \frac{(1-q^m)(1-q^{m-1})\cdots (1-q^{m-r+1})} {(1-q)(1-q^2)\cdots (1-q^r)}.$

The sage.groups.perm_gps.permgroup_elements contains the following combinatorial functions:

• matrix method of PermutationGroupElement yielding the permutation matrix of the group element.

Todo

GUAVA commands:
• MOLS returns a list of n Mutually Orthogonal Latin Squares (MOLS).
• VandermondeMat
• GrayMat returns a list of all different vectors of length n over the field F, using Gray ordering.
Not in GAP:

REFERENCES:

AUTHORS:

• David Joyner (2006-07): initial implementation.
• William Stein (2006-07): editing of docs and code; many optimizations, refinements, and bug fixes in corner cases
• David Joyner (2006-09): bug fix for combinations, added permutations_iterator, combinations_iterator from Python Cookbook, edited docs.
• Florent Hivert (2009-02): combinatorial class cleanup
• Fredrik Johansson (2010-07): fast implementation of stirling_number2
• Punarbasu Purkayastha (2012-12): deprecate arrangements, combinations, combinations_iterator, and clean up very old deprecated methods.

Functions and classes¶

class sage.combinat.combinat.CombinatorialClass(category=None, *keys, **opts)

This class is deprecated, and will disappear as soon as all derived classes in Sage’s library will have been fixed. Please derive directly from Parent and use the category EnumeratedSets, FiniteEnumeratedSets, or InfiniteEnumeratedSets, as appropriate.

For examples, see:

sage: FiniteEnumeratedSets().example()
An example of a finite enumerated set: {1,2,3}
sage: InfiniteEnumeratedSets().example()
An example of an infinite enumerated set: the non negative integers

Element

alias of CombinatorialObject

cardinality()

Default implementation of cardinality which just goes through the iterator of the combinatorial class to count the number of objects.

EXAMPLES:

sage: class C(CombinatorialClass):
...     def __iter__(self):
...          return iter([1,2,3])
...
sage: C().cardinality() #indirect doctest
3

element_class()

This function is a temporary helper so that a CombinatorialClass behaves as a parent for creating elements. This will disappear when combinatorial classes will be turned into actual parents (in the category EnumeratedSets).

TESTS:

sage: P5 = Partitions(5)
sage: P5.element_class
<class 'sage.combinat.partition.Partitions_n_with_category.element_class'>

filter(f, name=None)

Returns the combinatorial subclass of f which consists of the elements x of self such that f(x) is True.

EXAMPLES:

sage: from sage.combinat.combinat import Permutations_CC
sage: P = Permutations_CC(3).filter(lambda x: x.avoids([1,2]))
sage: P.list()
[[3, 2, 1]]

first()

Default implementation for first which uses iterator.

EXAMPLES:

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.first() # indirect doctest
1

is_finite()

Returns whether self is finite or not.

EXAMPLES:

sage: Partitions(5).is_finite()
True
sage: Permutations().is_finite()
False

last()

Default implementation for first which uses iterator.

EXAMPLES:

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.last() # indirect doctest
3

list()

The default implementation of list which builds the list from the iterator.

EXAMPLES:

sage: class C(CombinatorialClass):
...     def __iter__(self):
...          return iter([1,2,3])
...
sage: C().list() #indirect doctest
[1, 2, 3]

map(f, name=None)

Returns the image $$\{f(x) | x \in \text{self}\}$$ of this combinatorial class by $$f$$, as a combinatorial class.

$$f$$ is supposed to be injective.

EXAMPLES:

sage: R = Permutations(3).map(attrcall('reduced_word')); R
Image of Standard permutations of 3 by *.reduced_word()
sage: R.cardinality()
6
sage: R.list()
[[], [2], [1], [1, 2], [2, 1], [2, 1, 2]]
sage: [ r for r in R]
[[], [2], [1], [1, 2], [2, 1], [2, 1, 2]]

If the function is not injective, then there may be repeated elements:
sage: P = Partitions(4)
sage: P.list()
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
sage: P.map(len).list()
[1, 2, 2, 3, 4]


TESTS:

sage: R = Permutations(3).map(attrcall('reduced_word'))
True

next(obj)

Default implementation for next which uses iterator.

EXAMPLES:

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.next(2) # indirect doctest
3

previous(obj)

Default implementation for next which uses iterator.

EXAMPLES:

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.previous(2) # indirect doctest
1

random()

EXAMPLES:

sage: C = CombinatorialClass()
sage: C.random()
Traceback (most recent call last):
...

random_element()

Default implementation of random which uses unrank.

EXAMPLES:

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.random_element()       # indirect doctest
1

rank(obj)

Default implementation of rank which uses iterator.

EXAMPLES:

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.rank(3) # indirect doctest
2

union(right_cc, name=None)

Returns the combinatorial class representing the union of self and right_cc.

EXAMPLES:

sage: from sage.combinat.combinat import Permutations_CC
sage: P = Permutations_CC(2).union(Permutations_CC(1))
sage: P.list()
[[1, 2], [2, 1], [1]]

unrank(r)

Default implementation of unrank which goes through the iterator.

EXAMPLES:

sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.unrank(1) # indirect doctest
2

class sage.combinat.combinat.CombinatorialObject(l)

CombinatorialObject provides a thin wrapper around a list. The main differences are that __setitem__ is disabled so that CombinatorialObjects are shallowly immutable, and the intention is that they are semantically immutable.

Because of this, CombinatorialObjects provide a __hash__ function which computes the hash of the string representation of a list and the hash of its parent’s class. Thus, each CombinatorialObject should have a unique string representation.

INPUT:

• l - a list or any object that can be convert to a list by

list

EXAMPLES:

sage: c = CombinatorialObject([1,2,3])
True
sage: c._list
[1, 2, 3]
sage: c._hash is None
True

index(key)

EXAMPLES:

sage: c = CombinatorialObject([1,2,3])
sage: c.index(1)
0
sage: c.index(3)
2

class sage.combinat.combinat.FilteredCombinatorialClass(combinatorial_class, f, name=None)

A filtered combinatorial class F is a subset of another combinatorial class C specified by a function f that takes in an element c of C and returns True if and only if c is in F.

TESTS:

sage: from sage.combinat.combinat import Permutations_CC
sage: Permutations_CC(3).filter(lambda x: x.avoids([1,2]))
Filtered subclass of Standard permutations of 3

cardinality()

EXAMPLES:

sage: from sage.combinat.combinat import Permutations_CC
sage: P = Permutations_CC(3).filter(lambda x: x.avoids([1,2]))
sage: P.cardinality()
1

class sage.combinat.combinat.InfiniteAbstractCombinatorialClass(category=None, *keys, **opts)

This is an internal class that should not be used directly. A class which inherits from InfiniteAbstractCombinatorialClass inherits the standard methods list and count.

If self._infinite_cclass_slice exists then self.__iter__ returns an iterator for self, otherwise raise NotImplementedError. The method self._infinite_cclass_slice is supposed to accept any integer as an argument and return something which is iterable.

cardinality()

Counts the elements of the combinatorial class.

EXAMPLES:
sage: R = InfiniteAbstractCombinatorialClass() sage: R.cardinality() +Infinity
list()

Returns an error since self is an infinite combinatorial class.

EXAMPLES:
sage: R = InfiniteAbstractCombinatorialClass() sage: R.list() Traceback (most recent call last): ... NotImplementedError: infinite list
class sage.combinat.combinat.MapCombinatorialClass(cc, f, name=None)

A MapCombinatorialClass models the image of a combinatorial class through a function which is assumed to be injective

See CombinatorialClass.map for examples

an_element()

Returns an element of this combinatorial class

EXAMPLES:

sage: R = SymmetricGroup(10).map(attrcall('reduced_word'))
sage: R.an_element()
[9, 8, 7, 6, 5, 4, 3, 2, 1]

cardinality()

Returns the cardinality of this combinatorial class

EXAMPLES:

sage: R = Permutations(10).map(attrcall('reduced_word'))
sage: R.cardinality()
3628800

class sage.combinat.combinat.Permutations_CC(n)

A testing class for CombinatorialClass since Permutations no longer inherits from CombinatorialClass in trac ticket #14772.

class sage.combinat.combinat.UnionCombinatorialClass(left_cc, right_cc, name=None)

A UnionCombinatorialClass is a union of two other combinatorial classes.

TESTS:

sage: from sage.combinat.combinat import Permutations_CC
sage: P = Permutations_CC(3).union(Permutations_CC(2))
True

cardinality()

EXAMPLES:

sage: from sage.combinat.combinat import Permutations_CC
sage: P = Permutations_CC(3).union(Permutations_CC(2))
sage: P.cardinality()
8

first()

EXAMPLES:

sage: from sage.combinat.combinat import Permutations_CC
sage: P = Permutations_CC(3).union(Permutations_CC(2))
sage: P.first()
[1, 2, 3]

last()

EXAMPLES:

sage: from sage.combinat.combinat import Permutations_CC
sage: P = Permutations_CC(3).union(Permutations_CC(2))
sage: P.last()
[2, 1]

list()

EXAMPLES:

sage: from sage.combinat.combinat import Permutations_CC
sage: P = Permutations_CC(3).union(Permutations_CC(2))
sage: P.list()
[[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1],
[1, 2],
[2, 1]]

rank(x)

EXAMPLES:

sage: from sage.combinat.combinat import Permutations_CC
sage: P = Permutations_CC(3).union(Permutations_CC(2))
sage: P.rank(Permutation([2,1]))
7
sage: P.rank(Permutation([1,2,3]))
0

unrank(x)

EXAMPLES:

sage: from sage.combinat.combinat import Permutations_CC
sage: P = Permutations_CC(3).union(Permutations_CC(2))
sage: P.unrank(7)
[2, 1]
sage: P.unrank(0)
[1, 2, 3]

sage.combinat.combinat.arrangements(mset, k)

An arrangement of mset is an ordered selection without repetitions and is represented by a list that contains only elements from mset, but maybe in a different order.

arrangements returns the set of arrangements of the multiset mset that contain k elements.

INPUT:

• mset – (list) the multiset presented as a list of objects.
• k – (integer) the size of each set.

Note

This function is deprecated in favor of sage.combinat.permutation.Arrangements(). Use Arrangements(mset, k).list() directly to get the list of arrangements of mset.

EXAMPLES:

sage: arrangements([1,2,3], 2)
doctest:...: DeprecationWarning: Use Arrangements(mset,k).list()
[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
sage: mset = [1,1,2,3,4,4,5]
sage: arrangements(mset,2)
[[1, 1],
[1, 2],
[1, 3],
[1, 4],
[1, 5],
[2, 1],
[2, 3],
[2, 4],
[2, 5],
[3, 1],
[3, 2],
[3, 4],
[3, 5],
[4, 1],
[4, 2],
[4, 3],
[4, 4],
[4, 5],
[5, 1],
[5, 2],
[5, 3],
[5, 4]]
sage: arrangements( ["c","a","t"], 2 )
[['c', 'a'], ['c', 't'], ['a', 'c'],
['a', 't'], ['t', 'c'], ['t', 'a']]
sage: arrangements( ["c","a","t"], 3 )
[['c', 'a', 't'], ['c', 't', 'a'], ['a', 'c', 't'],
['a', 't', 'c'], ['t', 'c', 'a'], ['t', 'a', 'c']]

sage.combinat.combinat.bell_number(n, algorithm='dobinski', **options)

Return the $$n$$-th Bell number (the number of ways to partition a set of n elements into pairwise disjoint nonempty subsets). If $$n \leq 0$$, return $$1$$.

INPUT:

• n – a positive integer
• algorithm – (Default 'dobinski') Can be any one of the following:
• 'dobinski' – Use Dobinski’s summation formula (when $$n < 200$$, this just wraps GAP)
• 'gap' – Wrap GAP’s Bell
• 'mpmath' – Wrap mpmath’s bell

Warning

When using the mpmath algorithm to compute bell numbers and you specify prec, it can return incorrect results due to low precision. See the examples section.

Let $$B_n$$ denote the $$n$$-th Bell number. Dobinski’s formula is:

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

To show our implementation of Dobinski’s method works, suppose that $$n > 8$$ and let $$k_0$$ be the smallest integer for that $$\frac{k_0^n}{k_0!} < 1$$. Note that $$k_0 > n$$ and $$k_0 \leq 2n$$ because we can prove that $$\frac{(2n)^n}{(2n)!} < 1$$ by Stirling.

Next if $$k > k_0$$, then we have $$\frac{k^n}{k!} < \frac{1}{2^{k-k_0}}$$, and the proof is by induction. Let $$c_k = \frac{k^n}{k!}$$, if $$k > n$$ then

$\begin{split}\frac{c_{k+1}}{c_k} = \frac{(1+k^{-1})^n}{k+1} < \frac{(1+n^{-1})^n}{n} < \frac{4}{n} < \frac{1}{2}.\end{split}$

By using this, we can see that $$\frac{c_k}{c_{k_0}} < \frac{1}{2^{k-k_0}}$$ for $$k > k_0 > n$$. So summing this it gives that $$\sum_{k=k_0+1}^{\infty} \frac{k^n}{k!} < 1$$, and hence

$B_n = e^{-1} \left( \sum_{k=0}^{k_0} \frac{k^n}{k!} + E_1 \right) = e^{-1} \sum_{k=0}^{k_0} \frac{k^n}{k!} + E_2,$

where $$0 < E_1 < 1$$ and $$0 < E_2 < e^{-1}$$. Next we have:

$\sum_{k=0}^{k_0} \frac{k^n}{k!} = \sum_{k=0}^{k_0} n^{-2} \left\lfloor \frac{n^2 k^n}{k!} \right\rfloor + \frac{E_3}{n^2}$

where $$0 \leq E_3 \leq k_0 + 1 \leq 2n + 1 \leq 3n$$, so

$\sum_{k=0}^{k_0} \frac{k^n}{k!} = \sum_{k=0}{k_0} n^{-2} \left\lfloor \frac{n^2 k^n}{k!} \right\rfloor + E_4,$

where $$0 \leq E_4 \leq \frac{3}{n}$$. These two bounds gives:

\begin{split}\begin{aligned} B_n & = e^{-1} \sum_{k=0}^{k_0} n^{-2} \left\lfloor \frac{n^2 k^n}{k!} \right\rfloor + e^{-1} E_4 + E_2 \\ & = e^{-1} \sum_{k=0}^{k_0} n^{-2} \left\lfloor \frac{n^2 k^n}{k!} \right\rfloor + E_5 \end{aligned}\end{split}

where

$\begin{split}0 \leq E_5 < e^{-1} + \frac{3e^{-1}}{n} \leq e^{-1} \left(1 + \frac{3}{9}\right) < \frac{1}{2}.\end{split}$

Note $$E_5$$ can be close to 0, so to avoid this, we subtract $$\frac{1}{4}$$ from the sum:

\begin{split}\begin{aligned} B_n & = e^{-1} \sum_{k=0}^{k_0} n^{-2} \left\lfloor \frac{n^2 k^n}{k!} \right\rfloor - \frac{1}{4} + E, \\ B_n & = \left\lceil e^{-1} \sum_{k=0}^{k_0} n^{-2} \left\lfloor \frac{n^2 k^n}{k!} \right\rfloor -1/4 \right\rceil \end{aligned}\end{split}

where $$\frac{1}{4} \leq E < \frac{3}{4}$$.

Lastly, to avoid the costly integer division by $$k!$$, in one step collect more terms and do only one division, say collect 3 terms:

$\frac{k^n}{k!} + \frac{(k+1)^n}{(k+1)!} + \frac{(k+2)^n}{(k+2)!} = \frac{k^n (k+1)(k+2) + (k+1)^n (k+2) + (k+2)^n}{(k+2)!}$

using this all above error terms.

EXAMPLES:

sage: bell_number(10)
115975
sage: bell_number(2)
2
sage: bell_number(-10)
1
sage: bell_number(1)
1
sage: bell_number(1/3)
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer


When using the mpmath algorithm, we are required have mpmath’s precision set to at least $$\log_2(B_n)$$ bits. If upon computing the Bell number the first time, we deem the precision too low, we use our guess to (temporarily) raise mpmath’s precision and the Bell number is recomputed. The result from GAP’s bell number was checked agaist OEIS.

sage: k = bell_number(30, 'mpmath'); k
846749014511809332450147
sage: k == bell_number(30)
True


If you knows what precision is necessary before computing the Bell number, you can use the prec option:

sage: k2 = bell_number(30, 'mpmath', prec=30); k2
846749014511809332450147
sage: k == k2
True


Warning

Running mpmath with the precision set too low can result in incorrect results:

sage: k = bell_number(30, 'mpmath', prec=15); k
846749014511809388871680
sage: k == bell_number(30)
False


TESTS:

sage: all([bell_number(n) == bell_number(n,'gap') for n in range(200, 220)])
True
sage: all([bell_number(n) == bell_number(n,'mpmath', prec=500) for n in range(200, 220)])
True


AUTHORS:

• Robert Gerbicz

REFERENCES:

sage.combinat.combinat.bell_polynomial(n, k)

This function returns the Bell Polynomial

$B_{n,k}(x_1, x_2, \ldots, x_{n-k+1}) = \sum_{\sum{j_i}=k, \sum{i j_i} =n} \frac{n!}{j_1!j_2!\ldots} \frac{x_1}{1!}^j_1 \frac{x_2}{2!}^j_2 \ldots$

INPUT:

• n - integer
• k - integer

OUTPUT:

• polynomial expression (SymbolicArithmetic)

EXAMPLES:

sage: bell_polynomial(6,2)
10*x_3^2 + 15*x_2*x_4 + 6*x_1*x_5
sage: bell_polynomial(6,3)
15*x_2^3 + 60*x_1*x_2*x_3 + 15*x_1^2*x_4


REFERENCES:

• E.T. Bell, “Partition Polynomials”

AUTHORS:

• Blair Sutton (2009-01-26)
sage.combinat.combinat.bernoulli_polynomial(x, n)

Return the nth Bernoulli polynomial evaluated at x.

The generating function for the Bernoulli polynomials is

$\frac{t e^{xt}}{e^t-1}= \sum_{n=0}^\infty B_n(x) \frac{t^n}{n!},$

and they are given directly by

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

One has $$B_n(x) = - n\zeta(1 - n,x)$$, where $$\zeta(s,x)$$ is the Hurwitz zeta function. Thus, in a certain sense, the Hurwitz zeta function generalizes the Bernoulli polynomials to non-integer values of n.

EXAMPLES:

sage: y = QQ['y'].0
sage: bernoulli_polynomial(y, 5)
y^5 - 5/2*y^4 + 5/3*y^3 - 1/6*y
sage: bernoulli_polynomial(y, 5)(12)
199870
sage: bernoulli_polynomial(12, 5)
199870
sage: bernoulli_polynomial(y^2 + 1, 5)
y^10 + 5/2*y^8 + 5/3*y^6 - 1/6*y^2
sage: P.<t> = ZZ[]
sage: p = bernoulli_polynomial(t, 6)
sage: p.parent()
Univariate Polynomial Ring in t over Rational Field


We verify an instance of the formula which is the origin of the Bernoulli polynomials (and numbers):

sage: power_sum = sum(k^4 for k in range(10))
sage: 5*power_sum == bernoulli_polynomial(10, 5) - bernoulli(5)
True


REFERENCES:

sage.combinat.combinat.catalan_number(n)

Returns the n-th Catalan number

Catalan numbers: The $$n$$-th Catalan number is given directly in terms of binomial coefficients by

$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad\mbox{ for }\quad n\ge 0.$

Consider the set $$S = \{ 1, ..., n \}$$. A noncrossing partition of $$S$$ is a partition in which no two blocks “cross” each other, i.e., if a and b belong to one block and x and y to another, they are not arranged in the order axby. $$C_n$$ is the number of noncrossing partitions of the set $$S$$. There are many other interpretations (see REFERENCES).

When $$n=-1$$, this function raises a ZeroDivisionError; for other $$n<0$$ it returns $$0$$.

INPUT:

• n - integer

OUTPUT: integer

EXAMPLES:

sage: [catalan_number(i) for i in range(7)]
[1, 1, 2, 5, 14, 42, 132]
sage: taylor((-1/2)*sqrt(1 - 4*x^2), x, 0, 15)
132*x^14 + 42*x^12 + 14*x^10 + 5*x^8 + 2*x^6 + x^4 + x^2 - 1/2
sage: [catalan_number(i) for i in range(-7,7) if i != -1]
[0, 0, 0, 0, 0, 0, 1, 1, 2, 5, 14, 42, 132]
sage: catalan_number(-1)
Traceback (most recent call last):
...
ZeroDivisionError
sage: [catalan_number(n).mod(2) for n in range(16)]
[1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]


REFERENCES:

sage.combinat.combinat.combinations(mset, k)

A combination of a multiset (a list of objects which may contain the same object several times) mset is an unordered selection without repetitions and is represented by a sorted sublist of mset. Returns the set of all combinations of the multiset mset with k elements.

INPUT:

• mset – (list) the multiset presented as a list of objects.
• k – (integer) the size of each set.

Note

This function is deprecated in favor of sage.combinat.combination.Combinations(). Use Combinations(mset, k).list() directly to get the list of combinations of mset.

EXAMPLES:

sage: combinations([1,2,3], 2)
doctest:...: DeprecationWarning: Use Combinations(mset,k).list()
[[1, 2], [1, 3], [2, 3]]
sage: mset = [1,1,2,3,4,4,5]
sage: combinations(mset,2)
[[1, 1],
[1, 2],
[1, 3],
[1, 4],
[1, 5],
[2, 3],
[2, 4],
[2, 5],
[3, 4],
[3, 5],
[4, 4],
[4, 5]]
sage: mset = ["d","a","v","i","d"]
sage: combinations(mset,3)
[['d', 'd', 'a'],
['d', 'd', 'v'],
['d', 'd', 'i'],
['d', 'a', 'v'],
['d', 'a', 'i'],
['d', 'v', 'i'],
['a', 'v', 'i']]


It is possible to take combinations of Sage objects:

sage: combinations([vector([1,1]), vector([2,2]), vector([3,3])], 2)
[[(1, 1), (2, 2)], [(1, 1), (3, 3)], [(2, 2), (3, 3)]]

sage.combinat.combinat.combinations_iterator(mset, k=None)

An iterator for combinations of the elements of a multiset mset.

INPUT:

• mset – (list) the multiset presented as a list of objects.
• k – (integer, default: None) the size of each set.

Note

This function is deprecated in favor of sage.combinat.combination.Combinations(). Use Combinations(mset, k) instead.

EXAMPLES:

sage: X = combinations_iterator([1,2,3,4,5],3)
See http://trac.sagemath.org/13821 for details.
sage: [x for x in X]
[[1, 2, 3],
[1, 2, 4],
[1, 2, 5],
[1, 3, 4],
[1, 3, 5],
[1, 4, 5],
[2, 3, 4],
[2, 3, 5],
[2, 4, 5],
[3, 4, 5]]

sage.combinat.combinat.cyclic_permutations(mset)

This function is deprecated in trac ticket #14772. Use instead CyclicPermutations.

Return a list of all cyclic permutations of mset. Treats mset as a list, not a set, i.e. entries with the same value are distinct.

Note that CyclicPermutations, unlike this function, treats repeated elements as identical.

AUTHORS:

• Emily Kirkman

EXAMPLES:

sage: from sage.combinat.combinat import cyclic_permutations, cyclic_permutations_iterator
sage: cyclic_permutations(range(4))
doctest:...: DeprecationWarning: Use the CyclicPermutations object instead.
See http://trac.sagemath.org/14772 for details.
doctest:...: DeprecationWarning: Use the CyclicPermutations object instead.
See http://trac.sagemath.org/14772 for details.
[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1]]
sage: for cycle in cyclic_permutations(['a', 'b', 'c']):
....:     print cycle
['a', 'b', 'c']
['a', 'c', 'b']


Since trac ticket #14138 some repetitions are handled as expected:

sage: cyclic_permutations([1,1,1])
[[1, 1, 1]]

sage.combinat.combinat.cyclic_permutations_iterator(mset)

This function is deprecated in trac ticket #14772. Use instead CyclicPermutations.

Iterates over all cyclic permutations of mset in cycle notation. Treats mset as a list, not a set, i.e. entries with the same value are distinct.

Note that CyclicPermutations, unlike this function, treats repeated elements as identical.

AUTHORS:

• Emily Kirkman

EXAMPLES:

sage: from sage.combinat.combinat import cyclic_permutations, cyclic_permutations_iterator
sage: cyclic_permutations(range(4))
doctest:...: DeprecationWarning: Use the CyclicPermutations object instead.
See http://trac.sagemath.org/14772 for details.
[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1]]
sage: for cycle in cyclic_permutations(['a', 'b', 'c']):
....:     print cycle
['a', 'b', 'c']
['a', 'c', 'b']


Since trac ticket #14138 some repetitions are handled as expected:

sage: cyclic_permutations([1,1,1])
[[1, 1, 1]]

sage.combinat.combinat.derangements(mset)

This is deprecated in trac ticket #9005. Use instead Derangements.

EXAMPLES:

sage: mset = [1,2,3,4]
sage: D = derangements(mset); D
doctest:1: DeprecationWarning: derangements() is deprecated. Use Derangements instead.
See http://trac.sagemath.org/9005 for details.
Derangements of the set [1, 2, 3, 4]

sage.combinat.combinat.euler_number(n)

Returns the n-th Euler number

IMPLEMENTATION: Wraps Maxima’s euler.

EXAMPLES:

sage: [euler_number(i) for i in range(10)]
[1, 0, -1, 0, 5, 0, -61, 0, 1385, 0]
sage: maxima.eval("taylor (2/(exp(x)+exp(-x)), x, 0, 10)")
'1-x^2/2+5*x^4/24-61*x^6/720+277*x^8/8064-50521*x^10/3628800'
sage: [euler_number(i)/factorial(i) for i in range(11)]
[1, 0, -1/2, 0, 5/24, 0, -61/720, 0, 277/8064, 0, -50521/3628800]
sage: euler_number(-1)
Traceback (most recent call last):
...
ValueError: n (=-1) must be a nonnegative integer


REFERENCES:

sage.combinat.combinat.fibonacci(n, algorithm='pari')

Returns the n-th Fibonacci number. The Fibonacci sequence $$F_n$$ is defined by the initial conditions $$F_1=F_2=1$$ and the recurrence relation $$F_{n+2} = F_{n+1} + F_n$$. For negative $$n$$ we define $$F_n = (-1)^{n+1}F_{-n}$$, which is consistent with the recurrence relation.

INPUT:

• algorithm - string:
• "pari" - (default) - use the PARI C library’s fibo function.
• "gap" - use GAP’s Fibonacci function

Note

PARI is tens to hundreds of times faster than GAP here; moreover, PARI works for every large input whereas GAP doesn’t.

EXAMPLES:

sage: fibonacci(10)
55
sage: fibonacci(10, algorithm='gap')
55

sage: fibonacci(-100)
-354224848179261915075
sage: fibonacci(100)
354224848179261915075

sage: fibonacci(0)
0
sage: fibonacci(1/2)
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer

sage.combinat.combinat.fibonacci_sequence(start, stop=None, algorithm=None)

Returns an iterator over the Fibonacci sequence, for all fibonacci numbers $$f_n$$ from n = start up to (but not including) n = stop

INPUT:

• start - starting value
• stop - stopping value
• algorithm - default (None) - passed on to fibonacci function (or not passed on if None, i.e., use the default).

EXAMPLES:

sage: fibs = [i for i in fibonacci_sequence(10, 20)]
sage: fibs
[55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

sage: sum([i for i in fibonacci_sequence(100, 110)])
69919376923075308730013


AUTHORS:

• Bobby Moretti
sage.combinat.combinat.fibonacci_xrange(start, stop=None, algorithm='pari')

Returns an iterator over all of the Fibonacci numbers in the given range, including f_n = start up to, but not including, f_n = stop.

EXAMPLES:

sage: fibs_in_some_range =  [i for i in fibonacci_xrange(10^7, 10^8)]
sage: len(fibs_in_some_range)
4
sage: fibs_in_some_range
[14930352, 24157817, 39088169, 63245986]

sage: fibs = [i for i in fibonacci_xrange(10, 100)]
sage: fibs
[13, 21, 34, 55, 89]

sage: list(fibonacci_xrange(13, 34))
[13, 21]


A solution to the second Project Euler problem:

sage: sum([i for i in fibonacci_xrange(10^6) if is_even(i)])
1089154


AUTHORS:

• Bobby Moretti
sage.combinat.combinat.lucas_number1(n, P, Q)

Returns the n-th Lucas number “of the first kind” (this is not standard terminology). The Lucas sequence $$L^{(1)}_n$$ is defined by the initial conditions $$L^{(1)}_1=0$$, $$L^{(1)}_2=1$$ and the recurrence relation $$L^{(1)}_{n+2} = P*L^{(1)}_{n+1} - Q*L^{(1)}_n$$.

Wraps GAP’s Lucas(...)[1].

P=1, Q=-1 gives the Fibonacci sequence.

INPUT:

• n - integer
• P, Q - integer or rational numbers

OUTPUT: integer or rational number

EXAMPLES:

sage: lucas_number1(5,1,-1)
5
sage: lucas_number1(6,1,-1)
8
sage: lucas_number1(7,1,-1)
13
sage: lucas_number1(7,1,-2)
43

sage: lucas_number1(5,2,3/5)
229/25
sage: lucas_number1(5,2,1.5)
Traceback (most recent call last):
...
TypeError: no canonical coercion from Real Field with 53 bits of precision to Rational Field


There was a conjecture that the sequence $$L_n$$ defined by $$L_{n+2} = L_{n+1} + L_n$$, $$L_1=1$$, $$L_2=3$$, has the property that $$n$$ prime implies that $$L_n$$ is prime.

sage: lucas = lambda n : Integer((5/2)*lucas_number1(n,1,-1)+(1/2)*lucas_number2(n,1,-1))
sage: [[lucas(n),is_prime(lucas(n)),n+1,is_prime(n+1)] for n in range(15)]
[[1, False, 1, False],
[3, True, 2, True],
[4, False, 3, True],
[7, True, 4, False],
[11, True, 5, True],
[18, False, 6, False],
[29, True, 7, True],
[47, True, 8, False],
[76, False, 9, False],
[123, False, 10, False],
[199, True, 11, True],
[322, False, 12, False],
[521, True, 13, True],
[843, False, 14, False],
[1364, False, 15, False]]


Can you use Sage to find a counterexample to the conjecture?

sage.combinat.combinat.lucas_number2(n, P, Q)

Returns the n-th Lucas number “of the second kind” (this is not standard terminology). The Lucas sequence $$L^{(2)}_n$$ is defined by the initial conditions $$L^{(2)}_1=2$$, $$L^{(2)}_2=P$$ and the recurrence relation $$L^{(2)}_{n+2} = P*L^{(2)}_{n+1} - Q*L^{(2)}_n$$.

Wraps GAP’s Lucas(...)[2].

INPUT:

• n - integer
• P, Q - integer or rational numbers

OUTPUT: integer or rational number

EXAMPLES:

sage: [lucas_number2(i,1,-1) for i in range(10)]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
sage: [fibonacci(i-1)+fibonacci(i+1) for i in range(10)]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]

sage: n = lucas_number2(5,2,3); n
2
sage: type(n)
<type 'sage.rings.integer.Integer'>
sage: n = lucas_number2(5,2,-3/9); n
418/9
sage: type(n)
<type 'sage.rings.rational.Rational'>


The case P=1, Q=-1 is the Lucas sequence in Brualdi’s Introductory Combinatorics, 4th ed., Prentice-Hall, 2004:

sage: [lucas_number2(n,1,-1) for n in range(10)]
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]

sage.combinat.combinat.number_of_arrangements(mset, k)

Returns the size of arrangements(mset,k).

EXAMPLES:

sage: mset = [1,1,2,3,4,4,5]
sage: number_of_arrangements(mset,2)
See http://trac.sagemath.org/14138 for details.
22

sage.combinat.combinat.number_of_combinations(mset, k)

Returns the size of combinations(mset,k). IMPLEMENTATION: Wraps GAP’s NrCombinations.

EXAMPLES:

sage: mset = [1,1,2,3,4,4,5]
sage: number_of_combinations(mset,2)
See http://trac.sagemath.org/14138 for details.
12

sage.combinat.combinat.number_of_derangements(mset)

This is deprecated in trac ticket #9005. Use Derangements.cardinality() instead.

EXAMPLES:

sage: mset = [1,2,3,4]
sage: number_of_derangements(mset)
doctest:1: DeprecationWarning: number_of_derangements() is deprecated. Use Derangements.cardinality() instead.
See http://trac.sagemath.org/9005 for details.
9

sage.combinat.combinat.number_of_permutations(mset)

Do not use this function. It was deprecated in trac ticket #14138. Use Permutations instead. For example, instead of

number_of_permutations(mset)

use

Permutations(mset).cardinality().

If you insist on using this now:

Returns the size of permutations(mset).

AUTHORS:

• Robert L. Miller

EXAMPLES:

sage: mset = [1,1,2,2,2]
sage: number_of_permutations(mset)
doctest:...: DeprecationWarning: Use the Permutations object instead.
See http://trac.sagemath.org/14138 for details.
10

sage.combinat.combinat.number_of_tuples(S, k)

Returns the size of tuples(S,k). Wraps GAP’s NrTuples.

EXAMPLES:

sage: S = [1,2,3,4,5]
sage: number_of_tuples(S,2)
25
sage: S = [1,1,2,3,4,5]
sage: number_of_tuples(S,2)
25

sage.combinat.combinat.number_of_unordered_tuples(S, k)

Returns the size of unordered_tuples(S,k). Wraps GAP’s NrUnorderedTuples.

EXAMPLES:

sage: S = [1,2,3,4,5]
sage: number_of_unordered_tuples(S,2)
15

sage.combinat.combinat.permutations(mset)

This is deprecated in trac ticket #14772. Use Permutations instead. To get the same output as $$permutations(mset)$$, use Permutations(mset).list().

A permutation is represented by a list that contains exactly the same elements as mset, but possibly in different order. If mset is a proper set there are $$|mset| !$$ such permutations. Otherwise if the first elements appears $$k_1$$ times, the second element appears $$k_2$$ times and so on, the number of permutations is $$|mset|! / (k_1! k_2! \ldots)$$, which is sometimes called a multinomial coefficient.

permutations returns the list of all permutations of a multiset.

EXAMPLES:

sage: mset = [1,1,2,2,2]
sage: permutations(mset)
doctest:...: DeprecationWarning: Use the Permutations object instead.
See http://trac.sagemath.org/14772 for details.
[[1, 1, 2, 2, 2],
[1, 2, 1, 2, 2],
[1, 2, 2, 1, 2],
[1, 2, 2, 2, 1],
[2, 1, 1, 2, 2],
[2, 1, 2, 1, 2],
[2, 1, 2, 2, 1],
[2, 2, 1, 1, 2],
[2, 2, 1, 2, 1],
[2, 2, 2, 1, 1]]
sage: MS = MatrixSpace(GF(2),2,2)
sage: A = MS([1,0,1,1])
sage: rows = A.rows()
sage: rows[0].set_immutable()
sage: rows[1].set_immutable()
sage: permutations(rows)
[[(1, 0), (1, 1)], [(1, 1), (1, 0)]]

sage.combinat.combinat.permutations_iterator(mset, n=None)

Do not use this function. It is deprecated in trac ticket #14138. Use Permutations instead. For example, instead of

for p in permutations_iterator(range(1, m+1), n)

use

for p in Permutations(m, n).

Note that Permutations, unlike this function, treats repeated elements as identical.

If you insist on using this now:

Returns an iterator (http://docs.python.org/lib/typeiter.html) which can be used in place of permutations(mset) if all you need it for is a ‘for’ loop.

Posted by Raymond Hettinger, 2006/03/23, to the Python Cookbook: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474124

Note- This function considers repeated elements as different entries, so for example:

sage: from sage.combinat.combinat import permutations, permutations_iterator
sage: mset = [1,2,2]
sage: permutations(mset)
doctest:...: DeprecationWarning: Use the Permutations object instead.
See http://trac.sagemath.org/14772 for details.
[[1, 2, 2], [2, 1, 2], [2, 2, 1]]
sage: for p in permutations_iterator(mset): print p
doctest:...: DeprecationWarning: Use the Permutations object instead.
See http://trac.sagemath.org/14138 for details.
[1, 2, 2]
[2, 1, 2]
[2, 2, 1]
[2, 1, 2]
[2, 2, 1]


EXAMPLES:

sage: X = permutations_iterator(range(3),2)
sage: [x for x in X]
[[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]

sage.combinat.combinat.stirling_number1(n, k)

Returns the n-th Stilling number $$S_1(n,k)$$ of the first kind (the number of permutations of n points with k cycles). Wraps GAP’s Stirling1.

EXAMPLES:

sage: stirling_number1(3,2)
3
sage: stirling_number1(5,2)
50
sage: 9*stirling_number1(9,5)+stirling_number1(9,4)
269325
sage: stirling_number1(10,5)
269325


Indeed, $$S_1(n,k) = S_1(n-1,k-1) + (n-1)S_1(n-1,k)$$.

sage.combinat.combinat.stirling_number2(n, k, algorithm=None)

Returns the n-th Stirling number $$S_2(n,k)$$ of the second kind (the number of ways to partition a set of n elements into k pairwise disjoint nonempty subsets). (The n-th Bell number is the sum of the $$S_2(n,k)$$‘s, $$k=0,...,n$$.)

INPUT:

• n - nonnegative machine-size integer
• k - nonnegative machine-size integer
• algorithm:
• None (default) - use native implementation
• "maxima" - use Maxima’s stirling2 function
• "gap" - use GAP’s Stirling2 function

EXAMPLES:

Print a table of the first several Stirling numbers of the second kind:

sage: for n in range(10):
...       for k in range(10):
...           print str(stirling_number2(n,k)).rjust(k and 6),
...       print
...
1      0      0      0      0      0      0      0      0      0
0      1      0      0      0      0      0      0      0      0
0      1      1      0      0      0      0      0      0      0
0      1      3      1      0      0      0      0      0      0
0      1      7      6      1      0      0      0      0      0
0      1     15     25     10      1      0      0      0      0
0      1     31     90     65     15      1      0      0      0
0      1     63    301    350    140     21      1      0      0
0      1    127    966   1701   1050    266     28      1      0
0      1    255   3025   7770   6951   2646    462     36      1


Stirling numbers satisfy $$S_2(n,k) = S_2(n-1,k-1) + kS_2(n-1,k)$$:

sage: 5*stirling_number2(9,5) + stirling_number2(9,4)
42525
sage: stirling_number2(10,5)
42525


TESTS:

   sage: stirling_number2(500,501)
0
sage: stirling_number2(500,500)
1
sage: stirling_number2(500,499)
124750
sage: stirling_number2(500,498)
7739801875
sage: stirling_number2(500,497)
318420320812125
sage: stirling_number2(500,0)
0
sage: stirling_number2(500,1)
1
sage: stirling_number2(500,2)
1636695303948070935006594848413799576108321023021532394741645684048066898202337277441635046162952078575443342063780035504608628272942696526664263794687
sage: stirling_number2(500,3)
6060048632644989473730877846590553186337230837666937173391005972096766698597315914033083073801260849147094943827552228825899880265145822824770663507076289563105426204030498939974727520682393424986701281896187487826395121635163301632473646
sage: stirling_number2(500,30)
13707767141249454929449108424328432845001327479099713037876832759323918134840537229737624018908470350134593241314462032607787062188356702932169472820344473069479621239187226765307960899083230982112046605340713218483809366970996051181537181362810003701997334445181840924364501502386001705718466534614548056445414149016614254231944272872440803657763210998284198037504154374028831561296154209804833852506425742041757849726214683321363035774104866182331315066421119788248419742922490386531970053376982090046434022248364782970506521655684518998083846899028416459701847828711541840099891244700173707021989771147674432503879702222276268661726508226951587152781439224383339847027542755222936463527771486827849728880
sage: stirling_number2(500,31)
5832088795102666690960147007601603328246123996896731854823915012140005028360632199516298102446004084519955789799364757997824296415814582277055514048635928623579397278336292312275467402957402880590492241647229295113001728653772550743446401631832152281610081188041624848850056657889275564834450136561842528589000245319433225808712628826136700651842562516991245851618481622296716433577650218003181535097954294609857923077238362717189185577756446945178490324413383417876364657995818830270448350765700419876347023578011403646501685001538551891100379932684279287699677429566813471166558163301352211170677774072447414719380996777162087158124939742564291760392354506347716119002497998082844612434332155632097581510486912
sage: n = stirling_number2(20,11)
sage: n
1900842429486
sage: type(n)
<type 'sage.rings.integer.Integer'>
sage: n = stirling_number2(20,11,algorithm='gap')
sage: n
1900842429486
sage: type(n)
<type 'sage.rings.integer.Integer'>
sage: n = stirling_number2(20,11,algorithm='maxima')
sage: n
1900842429486
sage: type(n)
<type 'sage.rings.integer.Integer'>

Sage's implementation splitting the computation of the Stirling
numbers of the second kind in two cases according to n, let us
check the result it gives agree with both maxima and gap.

For n<200::

sage: for n in Subsets(range(100,200), 5).random_element():
...      for k in Subsets(range(n), 5).random_element():
...         s_sage = stirling_number2(n,k)
...         s_maxima = stirling_number2(n,k, algorithm = "maxima")
...         s_gap = stirling_number2(n,k, algorithm = "gap")
...         if not (s_sage == s_maxima and s_sage == s_gap):
...             print "Error with n<200"

For n\geq 200::

sage: for n in Subsets(range(200,300), 5).random_element():
...      for k in Subsets(range(n), 5).random_element():
...         s_sage = stirling_number2(n,k)
...         s_maxima = stirling_number2(n,k, algorithm = "maxima")
...         s_gap = stirling_number2(n,k, algorithm = "gap")
...         if not (s_sage == s_maxima and s_sage == s_gap):
...             print "Error with n<200"

TESTS:

Checking an exception is raised whenever a wrong value is given
for algorithm::

sage: s_sage = stirling_number2(50,3, algorithm = "CloudReading")
Traceback (most recent call last):
...
ValueError: unknown algorithm: CloudReading
sage.combinat.combinat.tuples(S, k)

An ordered tuple of length k of set is an ordered selection with repetition and is represented by a list of length k containing elements of set. tuples returns the set of all ordered tuples of length k of the set.

EXAMPLES:

sage: S = [1,2]
sage: tuples(S,3)
[[1, 1, 1], [2, 1, 1], [1, 2, 1], [2, 2, 1], [1, 1, 2], [2, 1, 2], [1, 2, 2], [2, 2, 2]]
sage: mset = ["s","t","e","i","n"]
sage: tuples(mset,2)
[['s', 's'], ['t', 's'], ['e', 's'], ['i', 's'], ['n', 's'], ['s', 't'], ['t', 't'],
['e', 't'], ['i', 't'], ['n', 't'], ['s', 'e'], ['t', 'e'], ['e', 'e'], ['i', 'e'],
['n', 'e'], ['s', 'i'], ['t', 'i'], ['e', 'i'], ['i', 'i'], ['n', 'i'], ['s', 'n'],
['t', 'n'], ['e', 'n'], ['i', 'n'], ['n', 'n']]


The Set(...) comparisons are necessary because finite fields are not enumerated in a standard order.

sage: K.<a> = GF(4, 'a')
sage: mset = [x for x in K if x!=0]
sage: tuples(mset,2)
[[a, a], [a + 1, a], [1, a], [a, a + 1], [a + 1, a + 1], [1, a + 1], [a, 1], [a + 1, 1], [1, 1]]


AUTHORS:

• Jon Hanke (2006-08)
sage.combinat.combinat.unordered_tuples(S, k)

An unordered tuple of length k of set is a unordered selection with repetitions of set and is represented by a sorted list of length k containing elements from set.

unordered_tuples returns the set of all unordered tuples of length k of the set. Wraps GAP’s UnorderedTuples.

Warning

Wraps GAP - hence mset must be a list of objects that have string representations that can be interpreted by the GAP interpreter. If mset consists of at all complicated Sage objects, this function does not do what you expect. A proper function should be written! (TODO!)

EXAMPLES:

sage: S = [1,2]
sage: unordered_tuples(S,3)
[[1, 1, 1], [1, 1, 2], [1, 2, 2], [2, 2, 2]]
sage: unordered_tuples(["a","b","c"],2)
['aa', 'ab', 'ac', 'bb', 'bc', 'cc']