Home       Trees       Indices       Help   
Package sage :: Package combinat :: Module combinat
[hide private]
[frames] | no frames]

Module combinat

source code


Combinatorial Functions.

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
        -- DJ (2006-09): bug fix for combinations, added permutations_iterator,
                      combinations_iterator from Python Cookbook, edited docs.
        -- DJ (2007-11): changed permutations, added hadamard_matrix
                      
This module implements some combinatorial functions, as listed
below. For a more detailed description, see the relevant docstrings.

Sequences:
\begin{itemize}
\item Bell numbers, \code{bell_number}

\item Bernoulli numbers, \code{bernoulli_number} (though PARI's bernoulli is 
  better)

\item Catalan numbers, \code{catalan_number} (not to be confused with the
  Catalan constant)

\item Eulerian/Euler numbers, \code{euler_number} (Maxima)

\item Fibonacci numbers, \code{fibonacci} (PARI) and \code{fibonacci_number} (GAP)
  The PARI version is better.

\item Lucas numbers, \code{lucas_number1}, \code{lucas_number2}.
 
\item Stirling numbers, \code{stirling_number1}, \code{stirling_number2}.
\end{itemize}
 
Set-theoretic constructions:
\begin{itemize}
\item Combinations of a multiset, \code{combinations}, \code{combinations_iterator},
and \code{number_of_combinations}. These are unordered selections without
repetition of k objects from a multiset S.

\item Arrangements of a multiset, \code{arrangements} and \code{number_of_arrangements}
  These are ordered selections without repetition of k objects from a 
  multiset S.

\item Derangements of a multiset, \code{derangements} and \code{number_of_derangements}.

\item Tuples of a multiset, \code{tuples} and \code{number_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. 

\item Unordered tuples of a set, \code{unordered_tuple} and \code{number_of_unordered_tuples}.
  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. 

\item Permutations of a multiset, \code{permutations}, \code{permutations_iterator},
\code{number_of_permutations}. A permutation is a list that contains exactly the same elements but 
possibly in different order.
\end{itemize}

Partitions:
\begin{itemize}
\item Partitions of a set, \code{partitions_set}, \code{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. 

\item Partitions of an integer, \code{partitions_list}, \code{number_of_partitions_list}.
  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$. 

\item Ordered partitions of an integer, \code{ordered_partitions}, 
  \code{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$. 

\item Restricted partitions of an integer, \code{partitions_restricted}, 
  \code{number_of_partitions_restricted}.
  An unordered restricted partition of n is an unordered sum 
  $n = p_1+p_2 +\ldots+ p_k$ of positive integers $p_i$ belonging to a
  given set $S$, 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$. 

\item \code{partitions_greatest}
   implements a special type of restricted partition.

\item \code{partitions_greatest_eq} is another type of restricted partition.

\item Tuples of partitions, \code{partition_tuples},
  \code{number_of_partition_tuples}.
  A $k$-tuple of partitions is represented by a list of all $k$-tuples 
  of partitions which together form a partition of $n$. 

\item Powers of a partition, \code{partition_power(pi, k)}.
  The power of a partition corresponds to the $k$-th power of a 
  permutation with cycle structure $\pi$.

\item Sign of a partition, \code{partition_sign( pi ) }
  This means the sign of a permutation with cycle structure given by the 
  partition pi.

\item Associated partition, \code{partition_associated( pi )}
  The ``associated'' (also called ``conjugate'' in the literature) 
  partition of the partition pi which is obtained by transposing the 
  corresponding Ferrers diagram.

\item Ferrers diagram, \code{ferrers_diagram}.
  Analogous to the Young diagram of an irredicible representation 
  of $S_n$.
  \end{itemize}

Related functions:

\begin{itemize}
\item Bernoulli polynomials, \code{bernoulli_polynomial}
\end{itemize}

Implemented in other modules (listed for completeness):

The \module{sage.rings.arith} module contains
the following combinatorial functions:
\begin{itemize}
 \item binomial
     the binomial coefficient (wrapped from PARI)
 \item factorial (wrapped from PARI)
 \item partition (from the Python Cookbook)
     Generator of the list of all the partitions of the integer $n$.
 \item \code{number_of_partitions} (wrapped from PARI)
     the *number* of partitions: 
 \item \code{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)}$.
 \item \code{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)}$.
 \item 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)}.
     $$
\end{itemize}

The \module{sage.groups.perm_gps.permgroup_elements} contains the following 
combinatorial functions:
\begin{itemize}
\item matrix method of PermutationGroupElement yielding the permutation
     matrix of the group element.
\end{itemize}     

\begin{verbatim}
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:
    * Rencontres numbers
      http://en.wikipedia.org/wiki/Rencontres_number
\end{verbatim}      

REFERENCES:
      \url{http://en.wikipedia.org/wiki/Twelvefold_way} (general reference)


Classes [hide private]
  CombinatorialObject
  CombinatorialClass
  FilteredCombinatorialClass
  UnionCombinatorialClass
Functions [hide private]
 
hadamard_matrix(n)
Returns an n x n Hadamard matrix of order $n$, if possible.		 source code
 
bell_number(n)
Returns the n-th Bell number (the number of ways to partition a set of n elements into pairwise disjoint nonempty subsets).		 source code
 
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 }n\ge 0.		 source code
 
euler_number(n)
Returns the n-th Euler number IMPLEMENTATION: Wraps Maxima's euler.		 source code
 
fibonacci(n, algorithm='pari')
Returns then n-th Fibonacci number.		 source code
 
lucas_number1(n, P, Q)
Returns then n-th Lucas number ``of the first kind'' (this is not standard terminology).		 source code
 
lucas_number2(n, P, Q)
Returns then n-th Lucas number ``of the second kind'' (this is not standard terminology).		 source code
 
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).		 source code
 
stirling_number2(n, k)
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).		 source code
 
hurwitz_zeta(s, x, N)
Returns the value of the $\zeta(s,x)$ to $N$ decimals, where s and x are real.		 source code
 
combinations(mset, k)
A {\it 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.		 source code
 
combinations_iterator(mset, n=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
Posted by Raymond Hettinger, 2006/03/23, to the Python Cookbook: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474124 Much faster than combinations.		 source code
 
number_of_combinations(mset, k)
Returns the size of combinations(mset,k).		 source code
 
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.		 source code
 
number_of_arrangements(mset, k)
Returns the size of arrangements(mset,k).		 source code
 
derangements(mset)
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.		 source code
 
number_of_derangements(mset)
Returns the size of derangements(mset).		 source code
 
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.		 source code
 
number_of_tuples(S, k)
Returns the size of tuples(S,k).		 source code
 
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.		 source code
 
number_of_unordered_tuples(S, k)
Returns the size of unordered_tuples(S,k).		 source code
 
permutations(mset)
A {\it permutation} is represented by a list that contains exactly the same elements as mset, but possibly in different order.		 source code
 
permutations_iterator(mset, n=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
Do not use this function.		 source code
 
number_of_permutations(mset)
Do not use this function.		 source code
 
cyclic_permutations(mset)
Returns a list of all cyclic permutations of mset.		 source code
 
cyclic_permutations_iterator(mset)
Iterates over all cyclic permutations of mset in cycle notation.		 source code
 
fibonacci_sequence(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., algorithm=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
Returns an iterator over the Fibonacci sequence, for all fibonacci numbers $f_n$ from \code{n = start} up to (but not including) \code{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).		 source code
 
fibonacci_xrange(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., algorithm='pari')
Returns an iterator over all of the Fibonacci numbers in the given range, including \code{f_n = start} up to, but not including, \code{f_n = stop}.		 source code
 
bernoulli_polynomial(x, n)
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!}.		 source code
Function Details [hide private]

hadamard_matrix(n)

source code  

Returns an n x n Hadamard matrix of order $n$, if possible.

If the construction of this matrix is not implemented in GUAVA or there is
no such matrix, raises a NotImplementedError.

EXAMPLES:
    sage: hadamard_matrix(4)
    [ 1  1  1  1]
    [ 1 -1  1 -1]
    [ 1  1 -1 -1]
    [ 1 -1 -1  1]
    sage: hadamard_matrix(6)
    Traceback (most recent call last):
    ...
    NotImplementedError: Hadamard matrix of order 6 does not exist or is not implemented yet.

bell_number(n)

source code  

Returns 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$, returns $1$.

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 coercion of this rational to integer

catalan_number(n)

source code  

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 }n\ge 0.
  \]
  
  Consider the set $S = \{ 1, ..., n \}$. A {\it 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$.

EXAMPLES:
    sage: [catalan_number(i) for i in range(7)]
    [1, 1, 2, 5, 14, 42, 132]
    sage: maxima.eval("-(1/2)*taylor (sqrt (1-4*x^2), x, 0, 15)")
    '-1/2+x^2+x^4+2*x^6+5*x^8+14*x^10+42*x^12+132*x^14'
    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: Rational division by zero        

REFERENCES:
\begin{itemize}
  \item \url{http://en.wikipedia.org/wiki/Catalan_number}
  \item \url{http://www-history.mcs.st-andrews.ac.uk/~history/Miscellaneous/CatalanNumbers/catalan.html}
\end{itemize}

euler_number(n)

source code  

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:
    http://en.wikipedia.org/wiki/Euler_number

fibonacci(n, algorithm='pari')

source code  

Returns then 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.

For negative $n$, define $F_{n} = -F_{|n|}$.

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 coercion of this rational to integer

lucas_number1(n, P, Q)

source code  

Returns then 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 fives 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 implicit coercion of element to the rational numbers
    
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:(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?

lucas_number2(n, P, Q)

source code  

Returns then 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
{\bf 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]

stirling_number1(n, k)

source code  

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)$.

stirling_number2(n, k)

source code  

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$.)
Wraps GAP's Stirling2.

EXAMPLES:
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: n = stirling_number2(20,11); n
    1900842429486
    sage: type(n)
    <type 'sage.rings.integer.Integer'>

hurwitz_zeta(s, x, N)

source code  

Returns the value of the $\zeta(s,x)$ to $N$ decimals, where s and x are real.

The Hurwitz zeta function is one of the many zeta functions. It defined as
\[
\zeta(s,x) = \sum_{k=0}^\infty (k+x)^{-s}.
\]
When $x = 1$, this coincides with Riemann's zeta function. The Dirichlet L-functions 
may be expressed as a linear combination of Hurwitz zeta functions.

EXAMPLES:
    sage: hurwitz_zeta(3,1/2,6)
    8.41439000000000
    sage: hurwitz_zeta(1.1,1/2,6)
    12.1041000000000
    sage: hurwitz_zeta(1.1,1/2,50)
    12.103813495683744469025853545548130581952676591199

REFERENCES:
    http://en.wikipedia.org/wiki/Hurwitz_zeta_function

combinations(mset, k)

source code  

A {\it 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.

WARNING: Wraps GAP's Combinations.  Hence mset must be a list of
objects that have string representations that can be interpreted by
the GAP intepreter.  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,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)
     ['add', 'adi', 'adv', 'aiv', 'ddi', 'ddv', 'div']

NOTE: For large lists, this raises a string error.

combinations_iterator(mset, n=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

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

Much faster than combinations.

EXAMPLES:
    sage: X = combinations_iterator([1,2,3,4,5],3)
    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]]

number_of_combinations(mset, k)

source code  

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


NOTE: mset must be a list of integers or strings (i.e., this is very restricted).

EXAMPLES:
    sage: mset = [1,1,2,3,4,4,5]
    sage: number_of_combinations(mset,2)
    12

arrangements(mset, k)

source code  

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.

\code{arrangements} returns the set of arrangements of the
multiset mset that contain k elements.

IMPLEMENTATION: Wraps GAP's Arrangements.
    
WARNING: Wraps GAP -- hence mset must be a list of objects that
have string representations that can be interpreted by the GAP
intepreter.  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,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 )
     ['ac', 'at', 'ca', 'ct', 'ta', 'tc']
     sage: arrangements( ["c","a","t"], 3 )
     ['act', 'atc', 'cat', 'cta', 'tac', 'tca']

number_of_arrangements(mset, k)

source code  

Returns the size of arrangements(mset,k).
Wraps GAP's NrArrangements.

EXAMPLES:
    sage: mset = [1,1,2,3,4,4,5]
    sage: number_of_arrangements(mset,2)
    22

derangements(mset)

source code  

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
intepreter.  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']

number_of_derangements(mset)

source code  

Returns the size of derangements(mset).
Wraps GAP's NrDerangements.

EXAMPLES:
    sage: mset = [1,2,3,4]
    sage: number_of_derangements(mset)
    9

tuples(S, k)

source code  

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]]

AUTHOR: Jon Hanke (2006-08?)

number_of_tuples(S, k)

source code  

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

unordered_tuples(S, k)

source code  

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
intepreter.  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']

number_of_unordered_tuples(S, k)

source code  

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

permutations(mset)

source code  

A {\it 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 {\it 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)]]

permutations_iterator(mset, n=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

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
    [1, 2, 2]
    [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]]

number_of_permutations(mset)

source code  

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).count().

If you insist on using this now:

Returns the size of permutations(mset).

AUTHOR: Robert L. Miller

EXAMPLES:
    sage: mset = [1,1,2,2,2]
    sage: number_of_permutations(mset)
    10

cyclic_permutations(mset)

source code  

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.

AUTHOR: Emily Kirkman

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']
    
Note that lists with repeats are not handled intuitively:
    sage: cyclic_permutations([1,1,1])
    [[1, 1, 1], [1, 1, 1]]

cyclic_permutations_iterator(mset)

source code  

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.

AUTHOR: Emily Kirkman

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']
    
Note that lists with repeats are not handled intuitively:
    sage: cyclic_permutations([1,1,1])
    [[1, 1, 1], [1, 1, 1]]

fibonacci_sequence(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., algorithm=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

Returns an iterator over the Fibonacci sequence, for all fibonacci numbers
$f_n$ from \code{n = start} up to (but not including) \code{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

SEE ALSO: fibonacci_xrange

AUTHOR:
    Bobby Moretti

fibonacci_xrange(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., algorithm='pari')

source code  

Returns an iterator over all of the Fibonacci numbers in the given range,
including \code{f_n = start} up to, but not including, \code{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: fibonacci_sequence

AUTHOR:
    Bobby Moretti

bernoulli_polynomial(x, n)

source code  

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!}. 
\]

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
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

REFERENCES:
    http://en.wikipedia.org/wiki/Bernoulli_polynomials

   Home       Trees       Indices       Help   
Generated by Epydoc 3.0beta1 on Thu Jul 17 04:23:25 2008 http://epydoc.sourceforge.net