Combinatorial Functions#
This module implements some combinatorial functions, as listed below. For a more detailed description, see the relevant docstrings.
Sequences:
Bell numbers,
bell_number()
Catalan numbers,
catalan_number()
(not to be confused with the Catalan constant)Narayana numbers,
narayana_number()
Euler numbers,
euler_number()
(Maxima)Eulerian numbers,
eulerian_number()
Eulerian polynomial,
eulerian_polynomial()
Fibonacci numbers,
fibonacci()
(PARI) andfibonacci_number()
(GAP) The PARI version is better.Lucas numbers,
lucas_number1()
,lucas_number2()
.Stirling numbers,
stirling_number1()
,stirling_number2()
.Polygonal numbers,
polygonal_number()
Set-theoretic constructions:
Derangements of a multiset,
derangements()
andnumber_of_derangements()
.Tuples of a multiset,
tuples()
andnumber_of_tuples()
. An ordered tuple of length k of set S is a ordered selection with repetitions of S and is represented by a sorted list of length k containing elements from S.Unordered tuples of a set,
unordered_tuples()
andnumber_of_unordered_tuples()
. An unordered tuple of length k of set S is an unordered selection with repetitions of S and is represented by a sorted list of length k containing elements from S.
Warning
The following function is deprecated and will soon be removed.
Permutations of a multiset,
permutations()
,permutations_iterator()
,number_of_permutations()
. A permutation is a list that contains exactly the same elements but possibly in different order.
Related functions:
Bernoulli polynomials,
bernoulli_polynomial()
Implemented in other modules (listed for completeness):
The package sage.arith
contains the following
combinatorial functions:
binomial()
the binomial coefficient (wrapped from PARI)factorial()
(wrapped from PARI)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)}\).
From other modules:
number_of_partitions()
(wrapped from PARI) the number of partitions:sage.combinat.q_analogues.gaussian_binomial()
the Gaussian binomial
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:
VandermondeMat
GrayMat returns a list of all different vectors of length n over the field F, using Gray ordering.
- Not in GAP:
Rencontres numbers (Wikipedia article Rencontres_number)
REFERENCES:
Wikipedia article Twelvefold_way (general reference)
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.
David Joyner (2007-11): changed permutations, added hadamard_matrix
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)#
Bases:
Parent
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
, orInfiniteEnumeratedSets
, 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).
- filter(f, name=None)#
Return the combinatorial subclass of f which consists of the elements x of
self
such that f(x) isTrue
.EXAMPLES:
sage: from sage.combinat.combinat import Permutations_CC sage: P = Permutations_CC(3).filter(lambda x: x.avoids([1,2])) sage: P.list() # optional - sage.combinat [[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()#
Return whether
self
is finite or not.EXAMPLES:
sage: Partitions(5).is_finite() # optional - sage.combinat 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, is_injective=None)#
Return the image \(\{f(x) | x \in \text{self}\}\) of this combinatorial class by \(f\), as a combinatorial class.
INPUT:
is_injective
– boolean (default:True
) whether to assume thatf
is injective.
EXAMPLES:
sage: R = Permutations(3).map(attrcall('reduced_word')); R Image of Standard permutations of 3 by The map *.reduced_word() from Standard permutations of 3 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) # optional - sage.combinat sage: P.list() # optional - sage.combinat [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]] sage: P.map(len).list() # optional - sage.combinat [1, 2, 2, 3, 4]
Use
is_injective=False
to get a correct result in this case:sage: P.map(len, is_injective=False).list() # optional - sage.combinat [1, 2, 3, 4]
- 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_element()#
Default implementation of random which uses unrank.
EXAMPLES:
sage: C = CombinatorialClass() sage: C.list = lambda: [1,2,3] sage: C.random_element() # random # 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)#
Return the combinatorial class representing the union of
self
andright_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.CombinatorialElement(parent, *args, **kwds)#
Bases:
CombinatorialObject
,Element
CombinatorialElement
is both aCombinatorialObject
and anElement
. So it represents a list which is an element of some parent.A
CombinatorialElement
subclass also automatically supports the__classcall__
mechanism.Warning
This class is slowly being deprecated. Use
ClonableList
instead.INPUT:
parent
– theParent
class for this element.lst
– a list or any object that can be converted to a list by callinglist()
.
EXAMPLES:
sage: from sage.combinat.combinat import CombinatorialElement sage: e = CombinatorialElement(Partitions(6), [3,2,1]) # optional - sage.combinat sage: e == loads(dumps(e)) # optional - sage.combinat True sage: parent(e) # optional - sage.combinat Partitions of the integer 6 sage: list(e) # optional - sage.combinat [3, 2, 1]
Check classcalls:
sage: class Foo(CombinatorialElement): ....: @staticmethod ....: def __classcall__(cls, x): ....: return x sage: Foo(17) 17
- class sage.combinat.combinat.CombinatorialObject(l, copy=True)#
Bases:
SageObject
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.
See also
CombinatorialElement
if you want a combinatorial object which is an element of a parent.Warning
This class is slowly being deprecated. Use
ClonableList
instead.INPUT:
l
– a list or any object that can be converted to a list by callinglist()
.copy
– (boolean, defaultTrue
) ifFalse
, thenl
must be alist
, which is assigned toself._list
without copying.
EXAMPLES:
sage: c = CombinatorialObject([1,2,3]) sage: c == loads(dumps(c)) True sage: c._list [1, 2, 3] sage: c._hash is None True
For efficiency, you can specify
copy=False
if you know what you are doing:sage: from sage.combinat.combinat import CombinatorialObject sage: x = [3, 2, 1] sage: C = CombinatorialObject(x, copy=False) sage: C [3, 2, 1] sage: x[0] = 5 sage: C [5, 2, 1]
- 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)#
Bases:
CombinatorialClass
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.
- 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() # optional - sage.combinat 1
- class sage.combinat.combinat.InfiniteAbstractCombinatorialClass(category=None)#
Bases:
CombinatorialClass
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()#
Count the elements of the combinatorial class.
EXAMPLES:
sage: R = InfiniteAbstractCombinatorialClass() doctest:warning... DeprecationWarning: this class is deprecated, do not use See https://github.com/sagemath/sage/issues/31545 for details. sage: R.cardinality() +Infinity
- list()#
Return 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, *, is_injective=True)#
Bases:
ImageSubobject
,CombinatorialClass
The image of a combinatorial class through a function.
INPUT:
is_injective
– boolean (default:True
) whether to assume thatf
is injective.
See
CombinatorialClass.map()
for examplesEXAMPLES:
sage: R = SymmetricGroup(10).map(attrcall('reduced_word')) # optional - sage.groups sage: R.an_element() # optional - sage.groups [9, 8, 7, 6, 5, 4, 3, 2] sage: R.cardinality() # optional - sage.groups 3628800 sage: i = iter(R) # optional - sage.groups sage: next(i), next(i), next(i) # optional - sage.groups ([], [1, 2, 3, 4, 5, 6, 7, 8, 9], [1])
- class sage.combinat.combinat.Permutations_CC(n)#
Bases:
CombinatorialClass
A testing class for
CombinatorialClass
sincePermutations
no longer inherits fromCombinatorialClass
in github issue #14772.
- class sage.combinat.combinat.UnionCombinatorialClass(left_cc, right_cc, name=None)#
Bases:
CombinatorialClass
A UnionCombinatorialClass is a union of two other combinatorial classes.
- 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.bell_number(n, algorithm='flint', **options)#
Return the \(n\)-th Bell number.
This is the number of ways to partition a set of \(n\) elements into pairwise disjoint nonempty subsets.
INPUT:
n
– a positive integeralgorithm
– (Default:'flint'
) any one of the following:'dobinski'
– Use Dobinski’s formula implemented in Sage'flint'
– Wrap FLINT’sarith_bell_number
'gap'
– Wrap GAP’sBell
'mpmath'
– Wrap mpmath’sbell
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 \geq 5\) and let \(k_0\) be the smallest positive integer such 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.
If \(k > k_0\), then we have \(\frac{k^n}{k!} < \frac{1}{2^{k-k_0}}\). We show this by induction: let \(c_k = \frac{k^n}{k!}\), if \(k > n\) then
\[\frac{c_{k+1}}{c_k} = \frac{(1+k^{-1})^n}{k+1} < \frac{(1+n^{-1})^n}{n} < \frac{1}{2}.\]The last inequality can easily be checked numerically for \(n \geq 5\).
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 for any \(q > 0\)
\[\sum_{k=0}^{k_0} \frac{k^n}{k!} = \frac{1}{q} \sum_{k=0}^{k_0} \left\lfloor \frac{q k^n}{k!} \right\rfloor + \frac{E_3}{q}\]where \(0 \leq E_3 \leq k_0 + 1 \leq 2n + 1\). Let \(E_4 = \frac{E_3}{q}\) and let \(q = 2n + 1\). We find \(0 \leq E_4 \leq 1\). These two bounds give:
\[\begin{split}\begin{aligned} B_n & = \frac{e^{-1}}{q} \sum_{k=0}^{k_0} \left\lfloor \frac{q k^n}{k!} \right\rfloor + e^{-1} E_4 + E_2 \\ & = \frac{e^{-1}}{q} \sum_{k=0}^{k_0} \left\lfloor \frac{q k^n}{k!} \right\rfloor + E_5 \end{aligned}\end{split}\]where
\[0 < E_5 = e^{-1} E_4 + E_2 \leq e^{-1} + e^{-1} < \frac{3}{4}.\]It follows that
\[B_n = \left\lceil \frac{e^{-1}}{q} \sum_{k=0}^{k_0} \left\lfloor \frac{q k^n}{k!} \right\rfloor \right\rceil.\]Now define
\[b = \sum_{k=0}^{k_0} \left\lfloor \frac{q k^n}{k!} \right\rfloor.\]This \(b\) can be computed exactly using integer arithmetic. To avoid the costly integer division by \(k!\), we collect more terms and do only one division, for example with 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)!}\]In the implementation, we collect \(\sqrt{n}/2\) terms.
To actually compute \(B_n\) from \(b\), we let \(p = \lfloor \log_2(b) \rfloor + 1\) such that \(b < 2^p\) and we compute with \(p\) bits of precision. This implies that \(b\) (and \(q < b\)) can be represented exactly.
We compute \(\frac{e^{-1}}{q} b\), rounding down, and we must have an absolute error of at most \(1/4\) (given that \(E_5 < 3/4\)). This means that we need a relative error of at most
\[\frac{e q}{4 b} > \frac{(e q)/4}{2^p} > \frac{7}{2^p}\](assuming \(n \geq 5\)). With a precision of \(p\) bits and rounding down, every rounding has a relative error of at most \(2^{1-p} = 2/2^p\). Since we do 3 roundings (\(b\) and \(q\) do not require rounding), we get a relative error of at most \(6/2^p\). All this implies that the precision of \(p\) bits is sufficient.
EXAMPLES:
sage: bell_number(10) # optional - sage.libs.flint 115975 sage: bell_number(2) # optional - sage.libs.flint 2 sage: bell_number(-10) # optional - sage.libs.flint Traceback (most recent call last): ... ArithmeticError: Bell numbers not defined for negative indices sage: bell_number(1) # optional - sage.libs.flint 1 sage: bell_number(1/3) # optional - sage.libs.flint 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.
sage: k = bell_number(30, 'mpmath'); k # optional - mpmath 846749014511809332450147 sage: k == bell_number(30) # optional - mpmath sage.libs.flint 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 # optional - mpmath 846749014511809332450147 sage: k == k2 # optional - mpmath True
Warning
Running mpmath with the precision set too low can result in incorrect results:
sage: k = bell_number(30, 'mpmath', prec=15); k # optional - mpmath 846749014511809388871680 sage: k == bell_number(30) # optional - mpmath sage.libs.flint False
AUTHORS:
Robert Gerbicz
Jeroen Demeyer: improved implementation of Dobinski formula with more accurate error estimates (github issue #17157)
REFERENCES:
- sage.combinat.combinat.bell_polynomial(n, k)#
Return the Bell Polynomial
\[B_{n,k}(x_0, x_1, \ldots, x_{n-k}) = \sum_{\sum{j_i}=k, \sum{(i+1) j_i}=n} \frac{n!}{j_0!j_1!\cdots j_{n-k}!} \left(\frac{x_0}{(0+1)!}\right)^{j_0} \left(\frac{x_1}{(1+1)!}\right)^{j_1} \cdots \left(\frac{x_{n-k}}{(n-k+1)!}\right)^{j_{n-k}}.\]INPUT:
n
– integerk
– integer
OUTPUT:
a polynomial in \(n-k+1\) variables over \(\ZZ\)
EXAMPLES:
sage: bell_polynomial(6,2) # optional - sage.combinat 10*x2^2 + 15*x1*x3 + 6*x0*x4 sage: bell_polynomial(6,3) # optional - sage.combinat 15*x1^3 + 60*x0*x1*x2 + 15*x0^2*x3
REFERENCES:
AUTHORS:
Blair Sutton (2009-01-26)
Thierry Monteil (2015-09-29): the result must always be a polynomial.
- sage.combinat.combinat.bernoulli_polynomial(x, n)#
Return the
n
-th Bernoulli polynomial evaluated atx
.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) # optional - sage.libs.flint y^5 - 5/2*y^4 + 5/3*y^3 - 1/6*y sage: bernoulli_polynomial(y, 5)(12) # optional - sage.libs.flint 199870 sage: bernoulli_polynomial(12, 5) # optional - sage.libs.flint 199870 sage: bernoulli_polynomial(y^2 + 1, 5) # optional - sage.libs.flint y^10 + 5/2*y^8 + 5/3*y^6 - 1/6*y^2 sage: P.<t> = ZZ[] sage: p = bernoulli_polynomial(t, 6) # optional - sage.libs.flint sage: p.parent() # optional - sage.libs.flint 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) # optional - sage.libs.flint True
REFERENCES:
- sage.combinat.combinat.catalan_number(n)#
Return the \(n\)-th Catalan number.
The \(n\)-th Catalan number is given directly in terms of binomial coefficients by
\[C_n = \frac{1}{n+1}\binom{2n}{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 returns the limit value \(-1/2\). 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: x = (QQ[['x']].0).O(8) sage: (-1/2)*sqrt(1 - 4*x) -1/2 + x + x^2 + 2*x^3 + 5*x^4 + 14*x^5 + 42*x^6 + 132*x^7 + O(x^8) sage: [catalan_number(i) for i in range(-7,7)] [0, 0, 0, 0, 0, 0, -1/2, 1, 1, 2, 5, 14, 42, 132] 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.euler_number(n, algorithm='flint')#
Return the \(n\)-th Euler number.
INPUT:
n
– a positive integeralgorithm
– (Default:'flint'
) any one of the following:'maxima'
– Wraps Maxima’seuler
.'flint'
– Wrap FLINT’sarith_euler_number
EXAMPLES:
sage: [euler_number(i) for i in range(10)] # optional - sage.libs.flint [1, 0, -1, 0, 5, 0, -61, 0, 1385, 0] sage: x = PowerSeriesRing(QQ, 'x').gen().O(10) sage: 2/(exp(x)+exp(-x)) # optional - sage.symbolic 1 - 1/2*x^2 + 5/24*x^4 - 61/720*x^6 + 277/8064*x^8 + O(x^10) sage: [euler_number(i)/factorial(i) for i in range(11)] # optional - sage.libs.flint [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.eulerian_number(k, algorithm='recursive')#
Return the Eulerian number of index
(n, k)
.This is the coefficient of \(t^k\) in the Eulerian polynomial \(A_n(t)\).
INPUT:
n
– integerk
– integer between0
andn - 1
algorithm
–"recursive"
(default) or"formula"
OUTPUT:
an integer
See also
EXAMPLES:
sage: from sage.combinat.combinat import eulerian_number sage: [eulerian_number(5,i) for i in range(5)] [1, 26, 66, 26, 1]
- sage.combinat.combinat.eulerian_polynomial(algorithm='derivative')#
Return the Eulerian polynomial of index
n
.This is the generating polynomial counting permutations in the symmetric group \(S_n\) according to their number of descents.
INPUT:
n
– an integeralgorithm
–"derivative"
(default) or"coeffs"
OUTPUT:
polynomial in one variable
t
See also
EXAMPLES:
sage: from sage.combinat.combinat import eulerian_polynomial sage: eulerian_polynomial(5) t^4 + 26*t^3 + 66*t^2 + 26*t + 1
REFERENCES:
- sage.combinat.combinat.fibonacci(n, algorithm='pari')#
Return 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
– a string:"pari"
- (default) use the PARI C library’s pari: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 does not.
EXAMPLES:
sage: fibonacci(10) # optional - sage.libs.pari 55 sage: fibonacci(10, algorithm='gap') # optional - sage.libs.gap 55
sage: fibonacci(-100) # optional - sage.libs.pari -354224848179261915075 sage: fibonacci(100) # optional - sage.libs.pari 354224848179261915075
sage: fibonacci(0) # optional - sage.libs.pari 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)#
Return 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 valuestop
– stopping valuealgorithm
– (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)]; fibs # optional - sage.libs.pari [55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
sage: sum([i for i in fibonacci_sequence(100, 110)]) # optional - sage.libs.pari 69919376923075308730013
See also
AUTHORS:
Bobby Moretti
- sage.combinat.combinat.fibonacci_xrange(start, stop=None, algorithm='pari')#
Return 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)] # optional - sage.libs.pari sage: len(fibs_in_some_range) # optional - sage.libs.pari 4 sage: fibs_in_some_range # optional - sage.libs.pari [14930352, 24157817, 39088169, 63245986]
sage: fibs = [i for i in fibonacci_xrange(10, 100)]; fibs # optional - sage.libs.pari [13, 21, 34, 55, 89]
sage: list(fibonacci_xrange(13, 34)) # optional - sage.libs.pari [13, 21]
A solution to the second Project Euler problem:
sage: sum([i for i in fibonacci_xrange(10^6) if is_even(i)]) # optional - sage.libs.pari 1089154
See also
AUTHORS:
Bobby Moretti
- sage.combinat.combinat.lucas_number1(n, P, Q)#
Return 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 \cdot L^{(1)}_{n+1} - Q \cdot L^{(1)}_n\).
Wraps GAP’s
Lucas(...)[1]
.\(P=1\), \(Q=-1\) gives the Fibonacci sequence.
INPUT:
n
– integerP, Q
– integer or rational numbers
OUTPUT: integer or rational number
EXAMPLES:
sage: lucas_number1(5,1,-1) # optional - sage.libs.gap 5 sage: lucas_number1(6,1,-1) # optional - sage.libs.gap 8 sage: lucas_number1(7,1,-1) # optional - sage.libs.gap 13 sage: lucas_number1(7,1,-2) # optional - sage.libs.gap 43 sage: lucas_number1(5,2,3/5) # optional - sage.libs.gap 229/25 sage: lucas_number1(5,2,1.5) # optional - sage.libs.gap 1/4
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: def lucas(n): ....: return 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)] # optional - sage.libs.gap [[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)#
Return 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 \cdot L^{(2)}_{n+1} - Q \cdot L^{(2)}_n\).
Wraps GAP’s Lucas(…)[2].
INPUT:
n
- integerP, Q
- integer or rational numbers
OUTPUT: integer or rational number
EXAMPLES:
sage: [lucas_number2(i,1,-1) for i in range(10)] # optional - sage.libs.gap [2, 1, 3, 4, 7, 11, 18, 29, 47, 76] sage: [fibonacci(i-1)+fibonacci(i+1) for i in range(10)] # optional - sage.libs.pari [2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
sage: n = lucas_number2(5,2,3); n # optional - sage.libs.gap 2 sage: type(n) # optional - sage.libs.gap <class 'sage.rings.integer.Integer'> sage: n = lucas_number2(5,2,-3/9); n # optional - sage.libs.gap 418/9 sage: type(n) # optional - sage.libs.gap <class '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)] # optional - sage.libs.gap [2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
- sage.combinat.combinat.narayana_number(n, k)#
Return the Narayana number of index
(n, k)
.For every integer \(n \geq 1\), the sum of Narayana numbers \(\sum_k N_{n,k}\) is the Catalan number \(C_n\).
INPUT:
n
– an integerk
– an integer between0
andn - 1
OUTPUT:
an integer
EXAMPLES:
sage: from sage.combinat.combinat import narayana_number sage: [narayana_number(3, i) for i in range(3)] [1, 3, 1] sage: sum(narayana_number(7,i) for i in range(7)) == catalan_number(7) True
REFERENCES:
- sage.combinat.combinat.number_of_tuples(S, k, algorithm='naive')#
Return the size of
tuples(S, k)
when \(S\) is a set. More generally, return the size oftuples(set(S), k)
. (So, unliketuples()
, this method removes redundant entries from \(S\).)INPUT:
S
– the base setk
– the length of the tuplesalgorithm
– can be one of the following:'naive'
- (default) use the naive counting \(|S|^k\)'gap'
- wraps GAP’sNrTuples
Warning
When using
algorithm='gap'
,S
must be a list of objects that have string representations that can be interpreted by the GAP interpreter. IfS
consists of at all complicated Sage objects, this function might not do what you expect.EXAMPLES:
sage: S = [1,2,3,4,5] sage: number_of_tuples(S,2) 25 sage: number_of_tuples(S,2, algorithm="gap") # optional - sage.libs.gap 25 sage: S = [1,1,2,3,4,5] sage: number_of_tuples(S,2) 25 sage: number_of_tuples(S,2, algorithm="gap") # optional - sage.libs.gap 25 sage: number_of_tuples(S,0) 1 sage: number_of_tuples(S,0, algorithm="gap") # optional - sage.libs.gap 1
- sage.combinat.combinat.number_of_unordered_tuples(S, k, algorithm='naive')#
Return the size of
unordered_tuples(S, k)
when \(S\) is a set.INPUT:
S
– the base setk
– the length of the tuplesalgorithm
– can be one of the following:'naive'
- (default) use the naive counting \(\binom{|S|+k-1}{k}\)'gap'
- wraps GAP’sNrUnorderedTuples
Warning
When using
algorithm='gap'
,S
must be a list of objects that have string representations that can be interpreted by the GAP interpreter. IfS
consists of at all complicated Sage objects, this function might not do what you expect.EXAMPLES:
sage: S = [1,2,3,4,5] sage: number_of_unordered_tuples(S,2) 15 sage: number_of_unordered_tuples(S,2, algorithm="gap") # optional - sage.libs.gap 15 sage: S = [1,1,2,3,4,5] sage: number_of_unordered_tuples(S,2) 15 sage: number_of_unordered_tuples(S,2, algorithm="gap") # optional - sage.libs.gap 15 sage: number_of_unordered_tuples(S,0) 1 sage: number_of_unordered_tuples(S,0, algorithm="gap") # optional - sage.libs.gap 1
- sage.combinat.combinat.polygonal_number(s, n)#
Return the \(n\)-th \(s\)-gonal number.
Polygonal sequences are represented by dots forming a regular polygon. Two famous sequences are the triangular numbers (3rd column of Pascal’s Triangle) and the square numbers. The \(n\)-th term in a polygonal sequence is defined by
\[P(s, n) = \frac{n^2(s-2) - n(s-4)}{2},\]where \(s\) is the number of sides of the polygon.
INPUT:
s
– integer greater than 1; the number of sides of the polygonn
– integer; the index of the returned \(s\)-gonal number
OUTPUT: an integer
EXAMPLES:
The triangular numbers:
sage: [polygonal_number(3, n) for n in range(10)] [0, 1, 3, 6, 10, 15, 21, 28, 36, 45] sage: [polygonal_number(3, n) for n in range(-10, 0)] [45, 36, 28, 21, 15, 10, 6, 3, 1, 0]
The square numbers:
sage: [polygonal_number(4, n) for n in range(10)] [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
The pentagonal numbers:
sage: [polygonal_number(5, n) for n in range(10)] [0, 1, 5, 12, 22, 35, 51, 70, 92, 117]
The hexagonal numbers:
sage: [polygonal_number(6, n) for n in range(10)] [0, 1, 6, 15, 28, 45, 66, 91, 120, 153]
The input is converted into an integer:
sage: polygonal_number(3.0, 2.0) 3
A non-integer input returns an error:
sage: polygonal_number(3.5, 1) Traceback (most recent call last): ... TypeError: Attempt to coerce non-integral RealNumber to Integer
\(s\) must be greater than 1:
sage: polygonal_number(1, 4) Traceback (most recent call last): ... ValueError: s (=1) must be greater than 1
REFERENCES:
- sage.combinat.combinat.stirling_number1(n, k, algorithm='gap')#
Return the \(n\)-th Stirling number \(S_1(n,k)\) of the first kind.
This is the number of permutations of \(n\) points with \(k\) cycles.
See Wikipedia article Stirling_numbers_of_the_first_kind.
INPUT:
n
– nonnegative machine-size integerk
– nonnegative machine-size integeralgorithm
:"gap"
(default) – use GAP’sStirling1
function"flint"
– use flint’sarith_stirling_number_1u
function
EXAMPLES:
sage: stirling_number1(3,2) # optional - sage.libs.gap 3 sage: stirling_number1(5,2) # optional - sage.libs.gap 50 sage: 9*stirling_number1(9,5) + stirling_number1(9,4) # optional - sage.libs.gap 269325 sage: stirling_number1(10,5) # optional - sage.libs.gap 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)#
Return the \(n\)-th Stirling number \(S_2(n,k)\) of the second kind.
This is 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\).
See Wikipedia article Stirling_numbers_of_the_second_kind.
INPUT:
n
– nonnegative machine-size integerk
– nonnegative machine-size integeralgorithm
:None
(default) – use native implementation"flint"
– use flint’sarith_stirling_number_2
function"gap"
– use GAP’sStirling2
function"maxima"
– use Maxima’sstirling2
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)) 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
- sage.combinat.combinat.tuples(S, k, algorithm='itertools')#
Return a list of all \(k\)-tuples of elements of a given set
S
.This function accepts the set
S
in the form of any iterable (list, tuple or iterator), and returns a list of \(k\)-tuples. IfS
contains duplicate entries, then you should expect the method to return tuples multiple times!Recall that \(k\)-tuples are ordered (in the sense that two \(k\)-tuples differing in the order of their entries count as different) and can have repeated entries (even if
S
is a list with no repetition).INPUT:
S
– the base setk
– the length of the tuplesalgorithm
– can be one of the following:'itertools'
- (default) use python’s itertools'native'
- use a native Sage implementation
Note
The ordering of the list of tuples depends on the algorithm.
EXAMPLES:
sage: S = [1,2] sage: tuples(S,3) [(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)] sage: mset = ["s","t","e","i","n"] sage: tuples(mset, 2) [('s', 's'), ('s', 't'), ('s', 'e'), ('s', 'i'), ('s', 'n'), ('t', 's'), ('t', 't'), ('t', 'e'), ('t', 'i'), ('t', 'n'), ('e', 's'), ('e', 't'), ('e', 'e'), ('e', 'i'), ('e', 'n'), ('i', 's'), ('i', 't'), ('i', 'e'), ('i', 'i'), ('i', 'n'), ('n', 's'), ('n', 't'), ('n', 'e'), ('n', 'i'), ('n', 'n')]
sage: K.<a> = GF(4, 'a') # optional - sage.rings.finite_rings sage: mset = [x for x in K if x != 0] # optional - sage.rings.finite_rings sage: tuples(mset, 2) # optional - sage.rings.finite_rings [(a, a), (a, a + 1), (a, 1), (a + 1, a), (a + 1, a + 1), (a + 1, 1), (1, a), (1, a + 1), (1, 1)]
We check that the implementations agree (up to ordering):
sage: tuples(S, 3, 'native') [(1, 1, 1), (2, 1, 1), (1, 2, 1), (2, 2, 1), (1, 1, 2), (2, 1, 2), (1, 2, 2), (2, 2, 2)]
Lastly we check on a multiset:
sage: S = [1,1,2] sage: sorted(tuples(S, 3)) == sorted(tuples(S, 3, 'native')) True
AUTHORS:
Jon Hanke (2006-08)
- sage.combinat.combinat.unordered_tuples(S, k, algorithm='itertools')#
Return a list of all unordered tuples of length
k
of the setS
.An unordered tuple of length \(k\) of set \(S\) is a unordered selection with repetitions of \(S\) and is represented by a sorted list of length \(k\) containing elements from \(S\).
Unlike
tuples()
, the result of this method does not depend on how often an element appears in \(S\); only the set \(S\) is being used. For example,unordered_tuples([1, 1, 1], 2)
will return[(1, 1)]
. If you want it to return[(1, 1), (1, 1), (1, 1)]
, use Python’sitertools.combinations_with_replacement
instead.INPUT:
S
– the base setk
– the length of the tuplesalgorithm
– can be one of the following:'itertools'
- (default) use python’s itertools'gap'
- wraps GAP’sUnorderedTuples
Warning
When using
algorithm='gap'
,S
must be a list of objects that have string representations that can be interpreted by the GAP interpreter. IfS
consists of at all complicated Sage objects, this function might not do what you expect.EXAMPLES:
sage: S = [1,2] sage: unordered_tuples(S, 3) [(1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 2, 2)]
We check that this agrees with GAP:
sage: unordered_tuples(S, 3, algorithm='gap') # optional - sage.libs.gap [(1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 2, 2)]
We check the result on strings:
sage: S = ["a","b","c"] sage: unordered_tuples(S, 2) [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'b'), ('b', 'c'), ('c', 'c')] sage: unordered_tuples(S, 2, algorithm='gap') # optional - sage.libs.gap [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'b'), ('b', 'c'), ('c', 'c')]
Lastly we check on a multiset:
sage: S = [1,1,2] sage: unordered_tuples(S, 3) == unordered_tuples(S, 3, 'gap') # optional - sage.libs.gap True sage: unordered_tuples(S, 3) [(1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 2, 2)]
- sage.combinat.combinat.unshuffle_iterator(a, one=1)#
Iterate over the unshuffles of a list (or tuple)
a
, also yielding the signs of the respective permutations.If \(n\) and \(k\) are integers satisfying \(0 \leq k \leq n\), then a \((k, n-k)\)-unshuffle means a permutation \(\pi \in S_n\) such that \(\pi(1) < \pi(2) < \cdots < \pi(k)\) and \(\pi(k+1) < \pi(k+2) < \cdots < \pi(n)\). This method provides, for a list \(a = (a_1, a_2, \ldots, a_n)\) of length \(n\), an iterator yielding all pairs:
\[\Bigl( \bigl( (a_{\pi(1)}, a_{\pi(2)}, \ldots, a_{\pi(k)}), (a_{\pi(k+1)}, a_{\pi(k+2)}, \ldots, a_{\pi(n)}) \bigl), (-1)^{\pi} \Bigr)\]for all \(k \in \{0, 1, \ldots, n\}\) and all \((k, n-k)\)-unshuffles \(\pi\). The optional variable
one
can be set to a different value which results in the \((-1)^{\pi}\) component being multiplied by said value.The iterator does not yield these in order of increasing \(k\).
EXAMPLES:
sage: from sage.combinat.combinat import unshuffle_iterator sage: list(unshuffle_iterator([1, 3, 4])) [(((), (1, 3, 4)), 1), (((1,), (3, 4)), 1), (((3,), (1, 4)), -1), (((1, 3), (4,)), 1), (((4,), (1, 3)), 1), (((1, 4), (3,)), -1), (((3, 4), (1,)), 1), (((1, 3, 4), ()), 1)] sage: list(unshuffle_iterator([3, 1])) [(((), (3, 1)), 1), (((3,), (1,)), 1), (((1,), (3,)), -1), (((3, 1), ()), 1)] sage: list(unshuffle_iterator([8])) [(((), (8,)), 1), (((8,), ()), 1)] sage: list(unshuffle_iterator([])) [(((), ()), 1)] sage: list(unshuffle_iterator([3, 1], 3/2)) [(((), (3, 1)), 3/2), (((3,), (1,)), 3/2), (((1,), (3,)), -3/2), (((3, 1), ()), 3/2)]