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.
- Combinations of a multiset, combinations(), combinations_iterator(), and number_of_combinations(). These are unordered selections without repetition of k objects from a multiset S.
- Arrangements of a multiset, arrangements() and number_of_arrangements() These are ordered selections without repetition of k objects from a multiset S.
- 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.
Partitions:
Related functions:
Implemented in other modules (listed for completeness):
The sage.rings.arith module contains the following combinatorial functions:
The sage.groups.perm_gps.permgroup_elements contains the following combinatorial functions:
Todo
REFERENCES:
AUTHORS:
Bases: sage.structure.parent.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, 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
alias of CombinatorialObject
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
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'>
Returns the combinatorial subclass of f which consists of the elements x of self such that f(x) is True.
EXAMPLES:
sage: P = Permutations(3).filter(lambda x: x.avoids([1,2]))
sage: P.list()
[[3, 2, 1]]
Default implementation for first which uses iterator.
EXAMPLES:
sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.first() # indirect doctest
1
Returns whether self is finite or not.
EXAMPLES:
sage: Partitions(5).is_finite()
True
sage: Permutations().is_finite()
False
Default implementation for first which uses iterator.
EXAMPLES:
sage: C = CombinatorialClass()
sage: C.list = lambda: [1,2,3]
sage: C.last() # indirect doctest
3
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]
Returns the image of this combinatorial
class by
, as a combinatorial class.
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'))
sage: R == loads(dumps(R))
True
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
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
Deprecated. Use self.random_element() instead.
EXAMPLES:
sage: C = CombinatorialClass()
sage: C.random()
Traceback (most recent call last):
...
NotImplementedError: Deprecated: use random_element() instead
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
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
Returns the combinatorial class representing the union of self and right_cc.
EXAMPLES:
sage: P = Permutations(2).union(Permutations(1))
sage: P.list()
[[1, 2], [2, 1], [1]]
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
Bases: sage.structure.sage_object.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.
INPUT:
list
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
EXAMPLES:
sage: c = CombinatorialObject([1,2,3])
sage: c.index(1)
0
sage: c.index(3)
2
Bases: sage.combinat.combinat.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.
TESTS:
sage: Permutations(3).filter(lambda x: x.avoids([1,2]))
Filtered sublass of Standard permutations of 3
EXAMPLES:
sage: P = Permutations(3).filter(lambda x: x.avoids([1,2]))
sage: P.cardinality()
1
Bases: sage.combinat.combinat.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.
Counts the elements of the combinatorial class.
Returns an error since self is an infinite combinatorial class.
Bases: sage.combinat.combinat.CombinatorialClass
A MapCombinatorialClass models the image of a combinatorial class through a function which is assumed to be injective
See CombinatorialClass.map for examples
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]
Returns the cardinality of this combinatorial class
EXAMPLES:
sage: R = Permutations(10).map(attrcall('reduced_word'))
sage: R.cardinality()
3628800
Bases: sage.combinat.combinat.CombinatorialClass
A UnionCombinatorialClass is a union of two other combinatorial classes.
TESTS:
sage: P = Permutations(3).union(Permutations(2))
sage: P == loads(dumps(P))
True
EXAMPLES:
sage: P = Permutations(3).union(Permutations(2))
sage: P.cardinality()
8
EXAMPLES:
sage: P = Permutations(3).union(Permutations(2))
sage: P.first()
[1, 2, 3]
EXAMPLES:
sage: P = Permutations(3).union(Permutations(2))
sage: P.last()
[2, 1]
EXAMPLES:
sage: P = Permutations(3).union(Permutations(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]]
EXAMPLES:
sage: P = Permutations(3).union(Permutations(2))
sage: P.rank(Permutation([2,1]))
7
sage: P.rank(Permutation([1,2,3]))
0
EXAMPLES:
sage: P = Permutations(3).union(Permutations(2))
sage: P.unrank(7)
[2, 1]
sage: P.unrank(0)
[1, 2, 3]
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:
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()
instead. See http://trac.sagemath.org/13821 for details.
[[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']]
Returns the n-th Bell number (the number of ways to partition a set of n elements into pairwise disjoint nonempty subsets).
If , returns
.
Wraps GAP’s Bell.
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
This function returns the Bell Polynomial
INPUT:
OUTPUT:
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:
AUTHORS:
Return the nth Bernoulli polynomial evaluated at x.
The generating function for the Bernoulli polynomials is
and they are given directly by
One has , where
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:
Returns the n-th Catalan number
Catalan numbers: The -th Catalan number is given
directly in terms of binomial coefficients by
Consider the set . A noncrossing
partition of
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.
is the number of noncrossing partitions of the set
. There are many other interpretations (see
REFERENCES).
When , this function raises a ZeroDivisionError; for
other
it returns
.
INPUT:
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:
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:
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()
instead. See http://trac.sagemath.org/13821 for details.
[[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)]]
An iterator for combinations of the elements of a multiset mset.
INPUT:
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)
doctest:...: DeprecationWarning: Use Combinations(mset,k) instead.
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]]
Returns 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.
AUTHORS:
EXAMPLES:
sage: from sage.combinat.combinat import cyclic_permutations, cyclic_permutations_iterator
sage: cyclic_permutations(range(4))
[[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]]
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.
AUTHORS:
EXAMPLES:
sage: from sage.combinat.combinat import cyclic_permutations, cyclic_permutations_iterator
sage: cyclic_permutations(range(4))
[[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]]
A derangement is a fixed point free permutation of list and is represented by a list that contains exactly the same elements as mset, but possibly in different order. Derangements returns the set of all derangements of a multiset.
Wraps GAP’s Derangements.
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: mset = [1,2,3,4]
sage: derangements(mset)
[[2, 1, 4, 3],
[2, 3, 4, 1],
[2, 4, 1, 3],
[3, 1, 4, 2],
[3, 4, 1, 2],
[3, 4, 2, 1],
[4, 1, 2, 3],
[4, 3, 1, 2],
[4, 3, 2, 1]]
sage: derangements(["c","a","t"])
['atc', 'tca']
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:
Returns the n-th Fibonacci number. The Fibonacci sequence
is defined by the initial conditions
and the recurrence relation
. For negative
we
define
, which is consistent with
the recurrence relation.
INPUT:
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
Returns an iterator over the Fibonacci sequence, for all fibonacci
numbers from n = start up to (but
not including) n = stop
INPUT:
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
See also
AUTHORS:
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
See also
AUTHORS:
Returns the value of the to
decimals, where s and x are real.
The Hurwitz zeta function is one of the many zeta functions. It defined as
When , this coincides with Riemann’s zeta function.
The Dirichlet L-functions may be expressed as a linear combination
of Hurwitz zeta functions.
Note that if you use floating point inputs, then the results may be slightly off.
EXAMPLES:
sage: hurwitz_zeta(3,1/2,6)
8.41439000000000
sage: hurwitz_zeta(11/10,1/2,6)
12.1041000000000
sage: hurwitz_zeta(11/10,1/2,50)
12.10381349568375510570907741296668061903364861809
REFERENCES:
Returns the n-th Lucas number “of the first kind” (this is not
standard terminology). The Lucas sequence is
defined by the initial conditions
,
and the recurrence relation
.
Wraps GAP’s Lucas(...)[1].
P=1, Q=-1 gives the Fibonacci sequence.
INPUT:
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 defined by
,
,
, has the property that
prime implies
that
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?
Returns the n-th Lucas number “of the second kind” (this is not
standard terminology). The Lucas sequence is
defined by the initial conditions
,
and the recurrence relation
.
Wraps GAP’s Lucas(...)[2].
INPUT:
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]
Returns the size of arrangements(mset,k).
EXAMPLES:
sage: mset = [1,1,2,3,4,4,5]
sage: number_of_arrangements(mset,2)
doctest:1: DeprecationWarning: Use Arrangements(mset,k).cardinality() instead.
See http://trac.sagemath.org/14138 for details.
22
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)
doctest:1: DeprecationWarning: Use Combinations(mset,k).cardinality() instead.
See http://trac.sagemath.org/14138 for details.
12
Returns the size of derangements(mset). Wraps GAP’s NrDerangements.
EXAMPLES:
sage: mset = [1,2,3,4]
sage: number_of_derangements(mset)
9
Do not use this function. It will be deprecated in future version of Sage and eventually removed. Use Permutations instead; instead of
number_of_permutations(mset)
use
Permutations(mset).cardinality().
If you insist on using this now:
Returns the size of permutations(mset).
AUTHORS:
EXAMPLES:
sage: mset = [1,1,2,2,2]
sage: number_of_permutations(mset)
doctest:1: DeprecationWarning: Use the Permutations object instead.
See http://trac.sagemath.org/14138 for details.
10
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
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
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 such permutations.
Otherwise if the first elements appears
times, the
second element appears
times and so on, the number
of permutations is
, which
is sometimes called a multinomial coefficient.
permutations returns the set of all permutations of a multiset. Calls a function written by Mike Hansen, not GAP.
EXAMPLES:
sage: mset = [1,1,2,2,2]
sage: permutations(mset)
[[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: permutations(A.rows())
[[(1, 0), (1, 1)], [(1, 1), (1, 0)]]
Do not use this function. It will be deprecated in future version of Sage and eventually removed. Use Permutations instead; 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)
[[1, 2, 2], [2, 1, 2], [2, 2, 1]]
sage: for p in permutations_iterator(mset): print p
doctest:1: 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]]
Returns the n-th Stilling number 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, .
Returns the n-th Stirling number 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,
.)
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 :
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
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:
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']