# source:sage/combinat/combinat.py@1321:645da9620309

Revision 1321:645da9620309, 44.1 KB checked in by wdj@…, 7 years ago (diff)

significant additions to linear-code and piecewise
many smaller changes and bug fixes to the other files.

Line
1r"""
2Combinatorial Functions.
3
4AUTHORS:
5        -- David Joyner (2006-07), initial implementation.
6        -- William Stein (2006-07), editing of docs and code; many optimizations,
7                      refinements, and bug fixes in corner cases
8        -- DJ (2006-09): bug fix for combinations, added permutations_iterator,
9                      combinations_iterator from Python Cookbook, edited docs.
10
11This module implements some combinatorial functions, as listed
12below. For a more detailed description, see the relevant docstrings.
13
14Sequences:
15\begin{itemize}
16\item Bell numbers, \code{bell_number}
17
18\item Bernoulli numbers, \code{bernoulli_number} (though PARI's bernoulli is
19  better)
20
21\item Catalan numbers, \code{catalan_number} (not to be confused with the
22  Catalan constant)
23
24\item Eulerian/Euler numbers, \code{euler_number} (Maxima)
25
26\item Fibonacci numbers, \code{fibonacci} (PARI) and \code{fibonacci_number} (GAP)
27  The PARI version is better.
28
29\item Lucas numbers, \code{lucas_number1}, \code{lucas_number2}.
30
31\item Stirling numbers, \code{stirling_number1}, \code{stirling_number2}.
32\end{itemize}
33
34Set-theoretic constructions:
35\begin{itemize}
36\item Combinations of a multiset, \code{combinations}, \code{combinations_iterator},
37and \code{number_of_combinations}. These are unordered selections without
38repetition of k objects from a multiset S.
39
40\item Arrangements of a multiset, \code{arrangements} and \code{number_of_arrangements}
41  These are ordered selections without repetition of k objects from a
42  multiset S.
43
44\item Derangements of a multiset, \code{derangements} and \code{number_of_derangements}.
45
46\item Tuples of a multiset, \code{tuples} and \code{number_of_tuples}.
47  An ordered tuple of length k of set S is a ordered selection with
48  repetitions of S and is represented by a sorted list of length k
49  containing elements from S.
50
51\item Unordered tuples of a set, \code{unordered_tuple} and \code{number_of_unordered_tuples}.
52  An unordered tuple of length k of set S is a unordered selection with
53  repetitions of S and is represented by a sorted list of length k
54  containing elements from S.
55
56\item Permutations of a multiset, \code{permutations, \code{permutations_iterator},
57\code{number_of_permutations. A permutation is a list that contains exactly the same elements but
58possibly in different order.
59\end{itemize}
60
61Partitions:
62\begin{itemize}
63\item Partitions of a set, \code{partitions_set}, \code{number_of_partitions_set}.
64  An unordered partition of set S is a set of pairwise disjoint
65  nonempty sets with union S and is represented by a sorted list of
66  such sets.
67
68\item Partitions of an integer, \code{partitions_list}, \code{number_of_partitions_list}.
69  An unordered partition of n is an unordered sum
70  $n = p_1+p_2 +\ldots+ p_k$ of positive integers and is represented by
71  the list $p = [p_1,p_2,\ldots,p_k]$, in nonincreasing order, i.e.,
72  $p1\geq p_2 ...\geq p_k$.
73
74\item Ordered partitions of an integer, \code{ordered_partitions},
75  \code{number_of_ordered_partitions}.
76  An ordered partition of n is an ordered sum $n = p_1+p_2 +\ldots+ p_k$
77  of positive integers and is represented by
78  the list $p = [p_1,p_2,\ldots,p_k]$, in nonincreasing order, i.e.,
79  $p1\geq p_2 ...\geq p_k$.
80
81\item Restricted partitions of an integer, \code{partitions_restricted},
82  \code{number_of_partitions_restricted}.
83  An unordered restricted partition of n is an unordered sum
84  $n = p_1+p_2 +\ldots+ p_k$ of positive integers $p_i$ belonging to a
85  given set $S$, and is represented by the list $p = [p_1,p_2,\ldots,p_k]$,
86  in nonincreasing order, i.e., $p1\geq p_2 ...\geq p_k$.
87
88\item \code{partitions_greatest}
89   implements a special type of restricted partition.
90
91\item \code{partitions_greatest_eq} is another type of restricted partition.
92
93\item Tuples of partitions, \code{partition_tuples},
94  \code{number_of_partition_tuples}.
95  A $k$-tuple of partitions is represented by a list of all $k$-tuples
96  of partitions which together form a partition of $n$.
97
98\item Powers of a partition, \code{partition_power(pi, k)}.
99  The power of a partition corresponds to the $k$-th power of a
100  permutation with cycle structure $\pi$.
101
102\item Sign of a partition, \code{partition_sign( pi ) }
103  This means the sign of a permutation with cycle structure given by the
104  partition pi.
105
106\item Associated partition, \code{partition_associated( pi )}
107  The associated'' (also called conjugate'' in the literature)
108  partition of the partition pi which is obtained by transposing the
109  corresponding Ferrers diagram.
110
111\item Ferrers diagram, \code{ferrers_diagram}.
112  Analogous to the Young diagram of an irredicible representation
113  of $S_n$.
114  \end{itemize}
115
116Related functions:
117
118\begin{itemize}
119\item Bernoulli polynomials, \code{bernoulli_polynomial}
120\end{itemize}
121
122Implemented in other modules (listed for completeness):
123
124The \module{sage.rings.arith} module contains
125the following combinatorial functions:
126\begin{itemize}
127 \item binomial
128     the binomial coefficient (wrapped from PARI)
129 \item factorial (wrapped from PARI)
130 \item partition (from the Python Cookbook)
131     Generator of the list of all the partitions of the integer $n$.
132 \item \code{number_of_partitions} (wrapped from PARI)
133     the *number* of partitions:
134 \item \code{falling_factorial}
135     Definition: for integer $a \ge 0$ we have $x(x-1) \cdots (x-a+1)$.
136     In all other cases we use the GAMMA-function:
137     $\frac {\Gamma(x+1)} {\Gamma(x-a+1)}$.
138 \item \code{rising_factorial}
139     Definition: for integer $a \ge 0$ we have $x(x+1) \cdots (x+a-1)$.
140     In all other cases we use the GAMMA-function:
141     $\frac {\Gamma(x+a)} {\Gamma(x)}$.
142 \item gaussian_binomial
143     the gaussian binomial
144     $$145 \binom{n}{k}_q = \frac{(1-q^m)(1-q^{m-1})\cdots (1-q^{m-r+1})} 146 {(1-q)(1-q^2)\cdots (1-q^r)}. 147$$
148\end{itemize}
149
150The \module{sage.groups.perm_gps.permgroup_elements} contains the following
151combinatorial functions:
152\begin{itemize}
153\item matrix method of PermutationGroupElement yielding the permutation
154     matrix of the group element.
155\end{itemize}
156
157\begin{verbatim}
158TODO:
159   GUAVA commands:
160    * MOLS returns a list of n Mutually Orthogonal Latin Squares (MOLS).
162    * VandermondeMat
163    * GrayMat returns a list of all different vectors of length n over
164      the field F, using Gray ordering.
165   Not in GAP:
166    * Rencontres numbers
167      http://en.wikipedia.org/wiki/Rencontres_number
168\end{verbatim}
169
170REFERENCES:
171      \url{http://en.wikipedia.org/wiki/Twelvefold_way} (general reference)
172
173"""
174
175#*****************************************************************************
176#       Copyright (C) 2006 David Joyner <wdjoyner@gmail.com>,
177#                     2006 William Stein <wstein@gmail.com>
178#
180#
181#    This code is distributed in the hope that it will be useful,
182#    but WITHOUT ANY WARRANTY; without even the implied warranty of
183#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
184#    General Public License for more details.
185#
186#  The full text of the GPL is available at:
187#
189#*****************************************************************************
190
191from sage.interfaces.all import gap, maxima
192from sage.rings.all import QQ, RR, ZZ
193from sage.rings.arith import binomial
194from sage.misc.sage_eval import sage_eval
195from sage.libs.all import pari
196
197######### combinatorial sequences
198
199def bell_number(n):
200    r"""
201    Returns the n-th Bell number (the number of ways to partition a
202    set of n elements into pairwise disjoint nonempty subsets).
203
204    If $n\leq 1$, returns $1$.
205
206    Wraps GAP's Bell.
207
208    EXAMPLES:
209        sage: bell_number(10)
210        115975
211        sage: bell_number(2)
212        2
213        sage: bell_number(-10)
214        1
215        sage: bell_number(1)
216        1
217        sage: bell_number(1/3)
218        Traceback (most recent call last):
219        ...
220        TypeError: Unable to coerce rational (=1/3) to an Integer.
221    """
222    ans=gap.eval("Bell(%s)"%ZZ(n))
223    return eval(ans)
224
225## def bernoulli_number(n):
226##     r"""
227##     Returns the n-th Bernoulli number $B_n$; $B_n/n!$ is the
228##     coefficient of $x^n$ in the power series of $x/(e^x-1)$.
229##     Wraps GAP's Bernoulli.
230##     EXAMPLES:
231##         sage: bernoulli_number(50)
232##         495057205241079648212477525/66
233##     """
234##     ans=gap.eval("Bernoulli(%s)"%n)
235##     return QQ(ans)   ## use QQ, not eval, here
236
237def catalan_number(n):
238    r"""
239    Returns the n-th Catalan number
240
241      Catalan numbers: The $n$-th Catalan number is given directly in terms of
242      binomial coefficients by
243      $244 C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} 245 \qquad\mbox{ for }n\ge 0. 246$
247
248      Consider the set $S = \{ 1, ..., n \}$. A {\it noncrossing partition} of $S$
249      is a partition in which no two blocks "cross" each other, i.e., if a
250      and b belong to one block and x and y to another, they are not arranged
251      in the order axby. $C_n$ is the number of noncrossing partitions of the set $S$.
252      There are many other interpretations (see REFERENCES).
253
254    When $n=-1$, this function raises a ZeroDivisionError; for other $n<0$ it
255    returns $0$.
256
257    EXAMPLES:
258        sage: [catalan_number(i) for i in range(7)]
259        [1, 1, 2, 5, 14, 42, 132]
260        sage: maxima.eval("-(1/2)*taylor (sqrt (1-4*x^2), x, 0, 15)")
261        '-1/2 + x^2 + x^4 + 2*x^6 + 5*x^8 + 14*x^10 + 42*x^12 + 132*x^14'
262        sage: [catalan_number(i) for i in range(-7,7) if i != -1]
263        [0, 0, 0, 0, 0, 0, 1, 1, 2, 5, 14, 42, 132]
264        sage: catalan_number(-1)
265        Traceback (most recent call last):
266        ...
267        ZeroDivisionError: Rational division by zero
268
269    REFERENCES:
270    \begin{itemize}
271      \item \url{http://en.wikipedia.org/wiki/Catalan_number}
272      \item \url{http://www-history.mcs.st-andrews.ac.uk/~history/Miscellaneous/CatalanNumbers/catalan.html}
273    \end{itemize}
274
275    """
276    n = ZZ(n)
277    return binomial(2*n,n)/(n+1)
278
279def euler_number(n):
280    """
281    Returns the n-th Euler number
282
283    IMPLEMENTATION: Wraps Maxima's euler.
284
285    EXAMPLES:
286        sage: [euler_number(i) for i in range(10)]
287        [1, 0, -1, 0, 5, 0, -61, 0, 1385, 0]
288        sage: maxima.eval("taylor (2/(exp(x)+exp(-x)), x, 0, 10)")
289        '1 - x^2/2 + 5*x^4/24 - 61*x^6/720 + 277*x^8/8064 - 50521*x^10/3628800'
290        sage: [euler_number(i)/factorial(i) for i in range(11)]
291        [1, 0, -1/2, 0, 5/24, 0, -61/720, 0, 277/8064, 0, -50521/3628800]
292        sage: euler_number(-1)
293        Traceback (most recent call last):
294        ...
295        ValueError: n (=-1) must be a nonnegative integer
296
297    REFERENCES:
298        http://en.wikipedia.org/wiki/Euler_number
299    """
300    n = ZZ(n)
301    if n < 0:
302        raise ValueError, "n (=%s) must be a nonnegative integer"%n
303    return ZZ(maxima.eval("euler(%s)"%n))
304
305def fibonacci(n, algorithm="pari"):
306    """
307    Returns then n-th Fibonacci number. The Fibonacci sequence $F_n$
308    is defined by the initial conditions $F_1=F_2=1$ and the
309    recurrence relation $F_{n+2} = F_{n+1} + F_n$. For negative $n$ we
310    define $F_n = (-1)^{n+1}F_{-n}$, which is consistent with the
311    recurrence relation.
312
313    For negative $n$, define $F_{n} = -F_{|n|}$.
314
315    INPUT:
316        algorithm -- string:
317                     "pari" -- (default) -- use the PARI C library's fibo function.
318                     "gap" -- use GAP's Fibonacci function
319
320    NOTE: PARI is tens to hundreds of times faster than GAP here;
321          moreover, PARI works for every large input whereas GAP
322          doesn't.
323
324    EXAMPLES:
325        sage: fibonacci(10)
326        55
327        sage: fibonacci(10, algorithm='gap')
328        55
329
330        sage: fibonacci(-100)
331        -354224848179261915075
332        sage: fibonacci(100)
333        354224848179261915075
334
335        sage: fibonacci(0)
336        0
337        sage: fibonacci(1/2)
338        Traceback (most recent call last):
339        ...
340        TypeError: Unable to coerce rational (=1/2) to an Integer.
341    """
342    n = ZZ(n)
343    if algorithm == 'pari':
344        return ZZ(pari(n).fibonacci())
345    elif algorithm == 'gap':
346        return ZZ(gap.eval("Fibonacci(%s)"%n))
347    else:
348        raise ValueError, "no algorithm %s"%algorithm
349
350def lucas_number1(n,P,Q):
351    """
352    Returns then n-th Lucas number of the first kind'' (this is not
353    standard terminology). The Lucas sequence $L^{(1)}_n$ is defined
354    by the initial conditions $L^{(1)}_1=0$, $L^{(1)}_2=1$ and the recurrence
355    relation $L^{(1)}_{n+2} = P*L^{(1)}_{n+1} - Q*L^{(1)}_n$.
356
357    Wraps GAP's Lucas(...)[1].
358
359    P=1, Q=-1 fives the Fibonacci sequence.
360
361    INPUT:
362        n -- integer
363        P, Q -- integer or rational numbers
364
365    OUTPUT:
366        integer or rational number
367
368    EXAMPLES:
369        sage: lucas_number1(5,1,-1)
370        5
371        sage: lucas_number1(6,1,-1)
372        8
373        sage: lucas_number1(7,1,-1)
374        13
375        sage: lucas_number1(7,1,-2)
376        43
377
378        sage: lucas_number1(5,2,3/5)
379        229/25
380        sage: lucas_number1(5,2,1.5)
381        Traceback (most recent call last):
382        ...
383        TypeError
384
385    There was a conjecture that the sequence $L_n$ defined by
386    $L_{n+2} = L_{n+1} + L_n$, $L_1=1$, $L_2=3$, has the property
387    that $n$ prime implies that $L_n$ is prime.
388
389        sage: lucas = lambda n:(5/2)*lucas_number1(n,1,-1)+(1/2)*lucas_number2(n,1,-1)
390        sage: [[lucas(n),is_prime(lucas(n)),n+1,is_prime(n+1)] for n in range(15)]
391        [[1, False, 1, False],
392         [3, True, 2, True],
393         [4, False, 3, True],
394         [7, True, 4, False],
395         [11, True, 5, True],
396         [18, False, 6, False],
397         [29, True, 7, True],
398         [47, True, 8, False],
399         [76, False, 9, False],
400         [123, False, 10, False],
401         [199, True, 11, True],
402         [322, False, 12, False],
403         [521, True, 13, True],
404         [843, False, 14, False],
405         [1364, False, 15, False]]
406
407    Can you use SAGE to find a counterexample to the conjecture?
408    """
409    ans=gap.eval("Lucas(%s,%s,%s)[1]"%(QQ._coerce_(P),QQ._coerce_(Q),ZZ(n)))
410    return sage_eval(ans)
411
412def lucas_number2(n,P,Q):
413    r"""
414    Returns then n-th Lucas number of the second kind'' (this is not
415    standard terminology). The Lucas sequence $L^{(2)}_n$ is defined
416    by the initial conditions $L^{(2)}_1=2$, $L^{(2)}_2=P$ and the recurrence
417    relation $L^{(2)}_{n+2} = P*L^{(2)}_{n+1} - Q*L^{(2)}_n$.
418
419    Wraps GAP's Lucas(...)[2].
420
421    INPUT:
422        n -- integer
423        P, Q -- integer or rational numbers
424
425    OUTPUT:
426        integer or rational number
427
428    EXAMPLES:
429        sage: [lucas_number2(i,1,-1) for i in range(10)]
430        [2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
431        sage: [fibonacci(i-1)+fibonacci(i+1) for i in range(10)]
432        [2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
433
434        sage: n = lucas_number2(5,2,3); n
435        2
436        sage: type(n)
437        <type 'integer.Integer'>
438        sage: n = lucas_number2(5,2,-3/9); n
439        418/9
440        sage: type(n)
441        <type 'rational.Rational'>
442
443    The case P=1, Q=-1 is the Lucas sequence in Brualdi's
444    {\bf Introductory Combinatorics}, 4th ed., Prentice-Hall, 2004:
445        sage: [lucas_number2(n,1,-1) for n in range(10)]
446        [2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
447    """
448    ans=gap.eval("Lucas(%s,%s,%s)[2]"%(QQ._coerce_(P),QQ._coerce_(Q),ZZ(n)))
449    return sage_eval(ans)
450
451def stirling_number1(n,k):
452    """
453    Returns the n-th Stilling number $S_1(n,k)$ of the first kind (the number of
454    permutations of n points with k cycles).
455    Wraps GAP's Stirling1.
456
457    EXAMPLES:
458        sage: stirling_number1(3,2)
459        3
460        sage: stirling_number1(5,2)
461        50
462        sage: 9*stirling_number1(9,5)+stirling_number1(9,4)
463        269325
464        sage: stirling_number1(10,5)
465        269325
466
467    Indeed, $S_1(n,k) = S_1(n-1,k-1) + (n-1)S_1(n-1,k)$.
468    """
469    return ZZ(gap.eval("Stirling1(%s,%s)"%(ZZ(n),ZZ(k))))
470
471def stirling_number2(n,k):
472    """
473    Returns the n-th Stirling number $S_2(n,k)$ of the second kind (the
474    number of ways to partition a set of n elements into k pairwise
475    disjoint nonempty subsets). (The n-th Bell number is the sum of
476    the $S_2(n,k)$'s, $k=0,...,n$.)
477    Wraps GAP's Stirling2.
478
479    EXAMPLES:
480    Stirling numbers satisfy $S_2(n,k) = S_2(n-1,k-1) + kS_2(n-1,k)$:
481
482        sage: 5*stirling_number2(9,5) + stirling_number2(9,4)
483        42525
484        sage: stirling_number2(10,5)
485        42525
486
487        sage: n = stirling_number2(20,11); n
488        1900842429486
489        sage: type(n)
490        <type 'integer.Integer'>
491    """
492    return ZZ(gap.eval("Stirling2(%s,%s)"%(ZZ(n),ZZ(k))))
493
494#### combinatorial sets/lists
495
496def combinations(mset,k):
497    r"""
498    A {\it combination} of a multiset (a list of objects which may
499    contain the same object several times) mset is an unordered
500    selection without repetitions and is represented by a sorted
501    sublist of mset.  Returns the set of all combinations of the
502    multiset mset with k elements.
503
504    WARNING: Wraps GAP's Combinations.  Hence mset must be a list of
505    objects that have string representations that can be interpreted by
506    the GAP intepreter.  If mset consists of at all complicated SAGE
507    objects, this function does *not* do what you expect.  A proper
508    function should be written! (TODO!)
509
510    EXAMPLES:
511        sage: mset = [1,1,2,3,4,4,5]
512        sage: combinations(mset,2)
513        [[1, 1],
514         [1, 2],
515         [1, 3],
516         [1, 4],
517         [1, 5],
518         [2, 3],
519         [2, 4],
520         [2, 5],
521         [3, 4],
522         [3, 5],
523         [4, 4],
524         [4, 5]]
525         sage: mset = ["d","a","v","i","d"]
526         sage: combinations(mset,3)
528
529    NOTE: For large lists, this raises a string error.
530    """
531    ans=gap.eval("Combinations(%s,%s)"%(mset,ZZ(k))).replace("\n","")
532    return eval(ans)
533
534def combinations_iterator(mset,n=None):
535    """
536    Posted by Raymond Hettinger, 2006/03/23, to the Python Cookbook:
537    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474124
538
539    Much faster than combinations.
540
541    EXAMPLES:
542        sage: X = combinations_iterator([1,2,3,4,5],3)
543        sage: [x for x in X]
544        [[1, 2, 3],
545         [1, 2, 4],
546         [1, 2, 5],
547         [1, 3, 4],
548         [1, 3, 5],
549         [1, 4, 5],
550         [2, 3, 4],
551         [2, 3, 5],
552         [2, 4, 5],
553         [3, 4, 5]]
554    """
555    items = mset
556    if n is None:
557        n = len(items)
558    for i in range(len(items)):
559        v = items[i:i+1]
560        if n == 1:
561            yield v
562        else:
563            rest = items[i+1:]
564            for c in combinations_iterator(rest, n-1):
565                yield v + c
566
567
568def number_of_combinations(mset,k):
569    """
570    Returns the size of combinations(mset,k).
571    IMPLEMENTATION: Wraps GAP's NrCombinations.
572
573
574    NOTE: mset must be a list of integers or strings (i.e., this is very restricted).
575
576    EXAMPLES:
577        sage: mset = [1,1,2,3,4,4,5]
578        sage: number_of_combinations(mset,2)
579        12
580    """
581    return ZZ(gap.eval("NrCombinations(%s,%s)"%(mset,ZZ(k))))
582
583def arrangements(mset,k):
584    r"""
585    An arrangement of mset is an ordered selection without repetitions
586    and is represented by a list that contains only elements from
587    mset, but maybe in a different order.
588
589    \code{arrangements} returns the set of arrangements of the
590    multiset mset that contain k elements.
591
592    IMPLEMENTATION: Wraps GAP's Arrangements.
593
594    WARNING: Wraps GAP -- hence mset must be a list of objects that
595    have string representations that can be interpreted by the GAP
596    intepreter.  If mset consists of at all complicated SAGE objects,
597    this function does *not* do what you expect.  A proper function
598    should be written! (TODO!)
599
600    EXAMPLES:
601        sage: mset = [1,1,2,3,4,4,5]
602        sage: arrangements(mset,2)
603        [[1, 1],
604         [1, 2],
605         [1, 3],
606         [1, 4],
607         [1, 5],
608         [2, 1],
609         [2, 3],
610         [2, 4],
611         [2, 5],
612         [3, 1],
613         [3, 2],
614         [3, 4],
615         [3, 5],
616         [4, 1],
617         [4, 2],
618         [4, 3],
619         [4, 4],
620         [4, 5],
621         [5, 1],
622         [5, 2],
623         [5, 3],
624         [5, 4]]
625         sage: arrangements( ["c","a","t"], 2 )
626         ['ac', 'at', 'ca', 'ct', 'ta', 'tc']
627         sage: arrangements( ["c","a","t"], 3 )
628         ['act', 'atc', 'cat', 'cta', 'tac', 'tca']
629    """
630    ans=gap.eval("Arrangements(%s,%s)"%(mset,k))
631    return eval(ans)
632
633def number_of_arrangements(mset,k):
634    """
635    Returns the size of arrangements(mset,k).
636    Wraps GAP's NrArrangements.
637
638    EXAMPLES:
639        sage: mset = [1,1,2,3,4,4,5]
640        sage: number_of_arrangements(mset,2)
641        22
642    """
643    return ZZ(gap.eval("NrArrangements(%s,%s)"%(mset,ZZ(k))))
644
645def derangements(mset):
646    """
647    A derangement is a fixed point free permutation of list and is
648    represented by a list that contains exactly the same elements as
649    mset, but possibly in different order.  Derangements returns the
650    set of all derangements of a multiset.
651
652    Wraps GAP's Derangements.
653
654    WARNING: Wraps GAP -- hence mset must be a list of objects that
655    have string representations that can be interpreted by the GAP
656    intepreter.  If mset consists of at all complicated SAGE objects,
657    this function does *not* do what you expect.  A proper function
658    should be written! (TODO!)
659
660    EXAMPLES:
661        sage: mset = [1,2,3,4]
662        sage: derangements(mset)
663        [[2, 1, 4, 3],
664         [2, 3, 4, 1],
665         [2, 4, 1, 3],
666         [3, 1, 4, 2],
667         [3, 4, 1, 2],
668         [3, 4, 2, 1],
669         [4, 1, 2, 3],
670         [4, 3, 1, 2],
671         [4, 3, 2, 1]]
672         sage: derangements(["c","a","t"])
673         ['atc', 'tca']
674
675    """
676    ans=gap.eval("Derangements(%s)"%mset)
677    return eval(ans)
678
679def number_of_derangements(mset):
680    """
681    Returns the size of derangements(mset).
682    Wraps GAP's NrDerangements.
683
684    EXAMPLES:
685        sage: mset = [1,2,3,4]
686        sage: number_of_derangements(mset)
687        9
688    """
689    ans=gap.eval("NrDerangements(%s)"%mset)
690    return ZZ(ans)
691
692def tuples(S,k):
693    """
694    An ordered tuple of length k of set is an ordered selection with
695    repetition and is represented by a list of length k containing
696    elements of set.
697    tuples returns the set of all ordered tuples of length k of the set.
698
699    EXAMPLES:
700        sage: S = [1,2]
701        sage: tuples(S,3)
702        [[1, 1, 1], [2, 1, 1], [1, 2, 1], [2, 2, 1], [1, 1, 2], [2, 1, 2], [1, 2, 2], [2, 2, 2]]
703        sage: mset = ["s","t","e","i","n"]
704        sage: tuples(mset,2)
705        [['s', 's'], ['t', 's'], ['e', 's'], ['i', 's'], ['n', 's'], ['s', 't'], ['t', 't'],
706         ['e', 't'], ['i', 't'], ['n', 't'], ['s', 'e'], ['t', 'e'], ['e', 'e'], ['i', 'e'],
707         ['n', 'e'], ['s', 'i'], ['t', 'i'], ['e', 'i'], ['i', 'i'], ['n', 'i'], ['s', 'n'],
708         ['t', 'n'], ['e', 'n'], ['i', 'n'], ['n', 'n']]
709        sage: mset = [x for x in GF(4) if x!=0]
710        sage: tuples(mset,2)
711        [[1, 1],
712         [a, 1],
713         [a + 1, 1],
714         [1, a],
715         [a, a],
716         [a + 1, a],
717         [1, a + 1],
718         [a, a + 1],
719         [a + 1, a + 1]]
720
721    AUTHOR: Jon Hanke (2006-08?)
722    """
723    import copy
724    if k<=0:
725        return [[]]
726    if k==1:
727        return [[x] for x in S]
728    ans = []
729    for s in S:
730        for x in tuples(S,k-1):
731            y = copy.copy(x)
732            y.append(s)
733            ans.append(y)
734    return ans
735    ## code wrapping GAP's Tuples:
736    #ans=gap.eval("Tuples(%s,%s)"%(S,k))
737    #return eval(ans)
738
739
740def number_of_tuples(S,k):
741    """
742    Returns the size of tuples(S,k).
743    Wraps GAP's NrTuples.
744
745    EXAMPLES:
746        sage: S = [1,2,3,4,5]
747        sage: number_of_tuples(S,2)
748        25
749        sage: S = [1,1,2,3,4,5]
750        sage: number_of_tuples(S,2)
751        25
752
753    """
754    ans=gap.eval("NrTuples(%s,%s)"%(S,ZZ(k)))
755    return ZZ(ans)
756
757def unordered_tuples(S,k):
758    """
759    An unordered tuple of length k of set is a unordered selection
760    with repetitions of set and is represented by a sorted list of
761    length k containing elements from set.
762
763    unordered_tuples returns the set of all unordered tuples of length k
764    of the set.
765    Wraps GAP's UnorderedTuples.
766
767    WARNING: Wraps GAP -- hence mset must be a list of objects that
768    have string representations that can be interpreted by the GAP
769    intepreter.  If mset consists of at all complicated SAGE objects,
770    this function does *not* do what you expect.  A proper function
771    should be written! (TODO!)
772
773    EXAMPLES:
774        sage: S = [1,2]
775        sage: unordered_tuples(S,3)
776        [[1, 1, 1], [1, 1, 2], [1, 2, 2], [2, 2, 2]]
777        sage: unordered_tuples(["a","b","c"],2)
778        ['aa', 'ab', 'ac', 'bb', 'bc', 'cc']
779
780    """
781    ans=gap.eval("UnorderedTuples(%s,%s)"%(S,ZZ(k)))
782    return eval(ans)
783
784def number_of_unordered_tuples(S,k):
785    """
786    Returns the size of unordered_tuples(S,k).
787    Wraps GAP's NrUnorderedTuples.
788
789    EXAMPLES:
790        sage: S = [1,2,3,4,5]
791        sage: number_of_unordered_tuples(S,2)
792        15
793    """
794    ans=gap.eval("NrUnorderedTuples(%s,%s)"%(S,ZZ(k)))
795    return ZZ(ans)
796
797def permutations(mset):
798    """
799    A {\it permutation} is represented by a list that contains exactly the same
800    elements as mset, but possibly in different order. If mset is a
801    proper set there are $|mset| !$ such permutations. Otherwise if the
802    first elements appears $k_1$ times, the second element appears $k_2$ times
803    and so on, the number of permutations is $|mset|! / (k_1! k_2! \ldots)$,
804    which is sometimes called a {\it multinomial coefficient}.
805
806    permutations returns the set of all permutations of a multiset.
807    Wraps GAP's PermutationsList.
808
809    WARNING: Wraps GAP -- hence mset must be a list of objects that
810    have string representations that can be interpreted by the GAP
811    intepreter.  If mset consists of at all complicated SAGE objects,
812    this function does *not* do what you expect.  A proper function
813    should be written! (TODO!)
814
815    EXAMPLES:
816        sage: mset = [1,1,2,2,2]
817        sage: permutations(mset)
818        [[1, 1, 2, 2, 2],
819         [1, 2, 1, 2, 2],
820         [1, 2, 2, 1, 2],
821         [1, 2, 2, 2, 1],
822         [2, 1, 1, 2, 2],
823         [2, 1, 2, 1, 2],
824         [2, 1, 2, 2, 1],
825         [2, 2, 1, 1, 2],
826         [2, 2, 1, 2, 1],
827         [2, 2, 2, 1, 1]]
828
829    """
830    ans=gap.eval("PermutationsList(%s)"%mset)
831    return eval(ans)
832
833def permutations_iterator(mset,n=None):
834    """
835    Posted by Raymond Hettinger, 2006/03/23, to the Python Cookbook:
836    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474124
837
838    EXAMPLES:
839        sage: X = permutations_iterator(range(3),2)
840        sage: [x for x in X]
841        [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]
842    """
843    items = mset
844    if n is None:
845        n = len(items)
846    for i in range(len(items)):
847        v = items[i:i+1]
848        if n == 1:
849            yield v
850        else:
851            rest = items[:i] + items[i+1:]
852            for p in permutations_iterator(rest, n-1):
853                yield v + p
854
855def number_of_permutations(mset):
856    """
857    Returns the size of permutations(mset).
858    Wraps GAP's NrPermutationsList.
859
860    EXAMPLES:
861        sage: mset = [1,1,2,2,2]
862        sage: number_of_permutations(mset)
863        10
864
865    """
866    ans=gap.eval("NrPermutationsList(%s)"%mset)
867    return ZZ(ans)
868
869#### partitions
870
871def partitions_set(S,k=None):
872    r"""
873    An {\it unordered partition} of a set $S$ is a set of pairwise disjoint
874    nonempty subsets with union $S$ and is represented by a sorted
875    list of such subsets.
876
877    partitions_set returns the set of all unordered partitions of the
878    list $S$ of increasing positive integers into k pairwise disjoint
879    nonempty sets. If k is omitted then all partitions are returned.
880
881    The Bell number $B_n$, named in honor of Eric Temple Bell, is
882    the number of different partitions of a set with n elements.
883
884    WARNING: Wraps GAP -- hence S must be a list of objects that have
885    string representations that can be interpreted by the GAP
886    intepreter.  If mset consists of at all complicated SAGE objects,
887    this function does *not* do what you expect.  A proper function
888    should be written! (TODO!)
889
890    Wraps GAP's PartitionsSet.
891
892    EXAMPLES:
893        sage: S = [1,2,3,4]
894        sage: partitions_set(S,2)
895        [[[1], [2, 3, 4]],
896         [[1, 2], [3, 4]],
897         [[1, 2, 3], [4]],
898         [[1, 2, 4], [3]],
899         [[1, 3], [2, 4]],
900         [[1, 3, 4], [2]],
901         [[1, 4], [2, 3]]]
902
903    REFERENCES:
904       http://en.wikipedia.org/wiki/Partition_of_a_set
905    """
906    if k==None:
907        ans=gap.eval("PartitionsSet(%s)"%S)
908    else:
909        ans=gap.eval("PartitionsSet(%s,%s)"%(S,k))
910    return eval(ans)
911
912def number_of_partitions_set(S,k):
913    r"""
914    Returns the size of \code{partitions_set(S,k)}.  Wraps GAP's
915    NrPartitionsSet.
916
917    The Stirling number of the second kind is the number of partitions
918    of a set of size n into k blocks.
919
920    EXAMPLES:
921        sage: mset = [1,2,3,4]
922        sage: number_of_partitions_set(mset,2)
923        7
924        sage: stirling_number2(4,2)
925        7
926
927    REFERENCES
928        http://en.wikipedia.org/wiki/Partition_of_a_set
929
930    """
931    if k==None:
932        ans=gap.eval("NrPartitionsSet(%s)"%S)
933    else:
934        ans=gap.eval("NrPartitionsSet(%s,%s)"%(S,ZZ(k)))
935    return ZZ(ans)
936
937def partitions_list(n,k=None):
938    r"""
939    An {\it unordered partition of $n$} is an unordered sum
940    $n = p_1+p_2 +\ldots+ p_k$ of positive integers and is represented by
941    the list $p = [p_1,p_2,\ldots,p_k]$, in nonincreasing order, i.e.,
942    $p1\geq p_2 ...\geq p_k$.
943
944    \code{partitions_list(n,k)} returns the list of all (unordered)
945    partitions of the positive integer n into sums with k summands. If
946    k is omitted then all partitions are returned.
947
948    Do not call partitions_list with an n much larger than 40, in
949    which case there are 37338 partitions, since the list will simply
950    become too large.
951
952    Wraps GAP's Partitions.
953
954    The function \code{partitions} (a wrapper for the corresponding
955    PARI function) returns not a list but rather a generator for a
956    list. It is also a function of only one argument.
957
958    EXAMPLES:
959        sage: partitions_list(10,2)
960        [[5, 5], [6, 4], [7, 3], [8, 2], [9, 1]]
961        sage: partitions_list(5)
962        [[1, 1, 1, 1, 1], [2, 1, 1, 1], [2, 2, 1], [3, 1, 1], [3, 2], [4, 1], [5]]
963
964    However, partitions(5) returns <generator object at ...>''.
965    """
966    if k==None:
967        ans=gap.eval("Partitions(%s)"%(n))
968    else:
969        ans=gap.eval("Partitions(%s,%s)"%(n,k))
970    return eval(ans.replace('\n',''))
971
972def number_of_partitions_list(n,k=None):
973    r"""
974    Returns the size of partitions_list(n,k).
975
976    Wraps GAP's NrPartitions.
977
978    It is possible to associate with every partition of the integer n
979    a conjugacy class of permutations in the symmetric group on n
980    points and vice versa.  Therefore p(n) = NrPartitions(n) is the
981    number of conjugacy classes of the symmetric group on n points.
982
983    \code{number_of_partitions(n)} is also available in PARI, however
984    the speed seems the same until $n$ is in the thousands (in which
985    case PARI is faster).
986
987    EXAMPLES:
988        sage: number_of_partitions_list(10,2)
989        5
990        sage: number_of_partitions_list(10)
991        42
992
993    A generating function for p(n) is given by the reciprocal of Euler's function:
994    $995 \sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right). 996$
997    SAGE verifies that the first several coefficients do instead agree:
998
999        sage: q = PowerSeriesRing(QQ,'q').gen()
1000        sage: prod((1-q^k)^(-1) for k in range(1,20))  ## partial product of
1001        1 + q + 2*q^2 + 3*q^3 + 5*q^4 + 7*q^5 + 11*q^6 + 15*q^7 + 22*q^8 + 30*q^9 + 42*q^10
1002        + 56*q^11 + 77*q^12 + 101*q^13 + 135*q^14 + 176*q^15 + 231*q^16 + 297*q^17 + 385*q^18
1003        + 490*q^19 + O(q^20)
1004        sage: [number_of_partitions_list(k) for k in range(2,10)]
1005        [2, 3, 5, 7, 11, 15, 22, 30]
1006
1007    REFERENCES:
1008        http://en.wikipedia.org/wiki/Partition_%28number_theory%29
1009
1010    """
1011    if k==None:
1012        ans=gap.eval("NrPartitions(%s)"%(ZZ(n)))
1013    else:
1014        ans=gap.eval("NrPartitions(%s,%s)"%(ZZ(n),ZZ(k)))
1015    return ZZ(ans)
1016
1017def ferrers_diagram(pi):
1018    """
1019    Return the Ferrers diagram of pi.
1020
1021    INPUT:
1022        pi -- a partition, given as a list of integers.
1023
1024    EXAMPLES:
1025        sage: print ferrers_diagram([5,5,2,1])
1026        *****
1027        *****
1028        **
1029        *
1030        sage: pi = partitions_list(10)[30] ## [6,1,1,1,1]
1031        sage: print ferrers_diagram(pi)
1032        ******
1033        *
1034        *
1035        *
1036        *
1037        sage: pi = partitions_list(10)[33] ## [6, 3, 1]
1038        sage: print ferrers_diagram(pi)
1039        ******
1040        ***
1041        *
1042    """
1043    return '\n'.join(['*'*p for p in pi])
1044
1045
1046def ordered_partitions(n,k=None):
1047    r"""
1048    An {\it ordered partition of $n$} is an ordered sum
1049    $$1050 n = p_1+p_2 + \cdots + p_k 1051$$
1052    of positive integers and is represented by the list $p = [p_1,p_2,\cdots ,p_k]$.
1053    If $k$ is omitted then all ordered partitions are returned.
1054
1055    \code{ordered_partitions(n,k)} returns the set of all (ordered)
1056    partitions of the positive integer n into sums with k summands.
1057
1058    Do not call \code{ordered_partitions} with an n much larger than
1059    15, since the list will simply become too large.
1060
1061    Wraps GAP's OrderedPartitions.
1062
1063    The number of ordered partitions $T_n$ of $\{ 1, 2, ..., n \}$ has the
1064    generating function is
1065    $1066 \sum_n {T_n \over n!} x^n = {1 \over 2-e^x}. 1067$
1068
1069    EXAMPLES:
1070        sage: ordered_partitions(10,2)
1071        [[1, 9], [2, 8], [3, 7], [4, 6], [5, 5], [6, 4], [7, 3], [8, 2], [9, 1]]
1072
1073        sage: ordered_partitions(4)
1074        [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]
1075
1076    REFERENCES:
1077        http://en.wikipedia.org/wiki/Ordered_partition_of_a_set
1078
1079    """
1080    if k==None:
1081        ans=gap.eval("OrderedPartitions(%s)"%(ZZ(n)))
1082    else:
1083        ans=gap.eval("OrderedPartitions(%s,%s)"%(ZZ(n),ZZ(k)))
1084    return eval(ans.replace('\n',''))
1085
1086def number_of_ordered_partitions(n,k=None):
1087    """
1088    Returns the size of ordered_partitions(n,k).
1089    Wraps GAP's NrOrderedPartitions.
1090
1091    It is possible to associate with every partition of the integer n a conjugacy
1092    class of permutations in the symmetric group on n points and vice versa.
1093    Therefore p(n) = NrPartitions(n) is the number of conjugacy classes of the
1094    symmetric group on n points.
1095
1096
1097    EXAMPLES:
1098        sage: number_of_ordered_partitions(10,2)
1099        9
1100        sage: number_of_ordered_partitions(15)
1101        16384
1102    """
1103    if k==None:
1104        ans=gap.eval("NrOrderedPartitions(%s)"%(n))
1105    else:
1106        ans=gap.eval("NrOrderedPartitions(%s,%s)"%(n,k))
1107    return ZZ(ans)
1108
1109def partitions_greatest(n,k):
1110    """
1111    Returns the set of all (unordered) restricted'' partitions of the integer n having
1112    parts less than or equal to the integer k.
1113
1114    Wraps GAP's PartitionsGreatestLE.
1115
1116    EXAMPLES:
1117        sage: partitions_greatest(10,2)
1118        [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
1119         [2, 1, 1, 1, 1, 1, 1, 1, 1],
1120         [2, 2, 1, 1, 1, 1, 1, 1],
1121         [2, 2, 2, 1, 1, 1, 1],
1122         [2, 2, 2, 2, 1, 1],
1123         [2, 2, 2, 2, 2]]
1124    """
1125    return eval(gap.eval("PartitionsGreatestLE(%s,%s)"%(ZZ(n),ZZ(k))))
1126
1127def partitions_greatest_eq(n,k):
1128    """
1129    Returns the set of all (unordered) restricted'' partitions of the
1130    integer n having at least one part equal to the integer k.
1131
1132    Wraps GAP's PartitionsGreatestEQ.
1133
1134    EXAMPLES:
1135        sage: partitions_greatest_eq(10,2)
1136        [[2, 1, 1, 1, 1, 1, 1, 1, 1],
1137         [2, 2, 1, 1, 1, 1, 1, 1],
1138         [2, 2, 2, 1, 1, 1, 1],
1139         [2, 2, 2, 2, 1, 1],
1140         [2, 2, 2, 2, 2]]
1141
1142    """
1143    ans = gap.eval("PartitionsGreatestEQ(%s,%s)"%(n,k))
1144    return eval(ans)
1145
1146def partitions_restricted(n,S,k=None):
1147    r"""
1148    A {\it restricted partition} is, like an ordinary partition, an
1149    unordered sum $n = p_1+p_2+\ldots+p_k$ of positive integers and is
1150    represented by the list $p = [p_1,p_2,\ldots,p_k]$, in nonincreasing
1151    order. The difference is that here the $p_i$ must be elements
1152    from the set $S$, while for ordinary partitions they may be
1153    elements from $[1..n]$.
1154
1155    Returns the set of all restricted partitions of the positive integer
1156    n into sums with k summands with the summands of the partition coming
1157    from the set $S$. If k is not given all restricted partitions for all
1158    k are returned.
1159
1160    Wraps GAP's RestrictedPartitions.
1161
1162    EXAMPLES:
1163        sage: partitions_restricted(8,[1,3,5,7])
1164        [[1, 1, 1, 1, 1, 1, 1, 1],
1165         [3, 1, 1, 1, 1, 1],
1166         [3, 3, 1, 1],
1167         [5, 1, 1, 1],
1168         [5, 3],
1169         [7, 1]]
1170        sage: partitions_restricted(8,[1,3,5,7],2)
1171        [[5, 3], [7, 1]]
1172    """
1173    if k==None:
1174        ans=gap.eval("RestrictedPartitions(%s,%s)"%(n,S))
1175    else:
1176        ans=gap.eval("RestrictedPartitions(%s,%s,%s)"%(n,S,k))
1177    return eval(ans)
1178
1179def number_of_partitions_restricted(n,S,k=None):
1180    """
1181    Returns the size of partitions_restricted(n,S,k).
1182    Wraps GAP's NrRestrictedPartitions.
1183
1184    EXAMPLES:
1185        sage: number_of_partitions_restricted(8,[1,3,5,7])
1186        6
1187        sage: number_of_partitions_restricted(8,[1,3,5,7],2)
1188        2
1189
1190    """
1191    if k==None:
1192        ans=gap.eval("NrRestrictedPartitions(%s,%s)"%(ZZ(n),S))
1193    else:
1194        ans=gap.eval("NrRestrictedPartitions(%s,%s,%s)"%(ZZ(n),S,ZZ(k)))
1195    return ZZ(ans)
1196
1197def partitions_tuples(n,k):
1198    """
1199    partition_tuples( n, k ) returns the list of all k-tuples of partitions
1200    which together form a partition of n.
1201
1202    k-tuples of partitions describe the classes and the characters of
1203    wreath products of groups with k conjugacy classes with the symmetric
1204    group $S_n$.
1205
1206    Wraps GAP's PartitionTuples.
1207
1208    EXAMPLES:
1209        sage: partitions_tuples(3,2)
1210        [[[1, 1, 1], []],
1211         [[1, 1], [1]],
1212         [[1], [1, 1]],
1213         [[], [1, 1, 1]],
1214         [[2, 1], []],
1215         [[1], [2]],
1216         [[2], [1]],
1217         [[], [2, 1]],
1218         [[3], []],
1219         [[], [3]]]
1220    """
1221    ans=gap.eval("PartitionTuples(%s,%s)"%(ZZ(n),ZZ(k)))
1222    return eval(ans)
1223
1224def number_of_partitions_tuples(n,k):
1225    r"""
1226    number_of_partition_tuples( n, k ) returns the number of partition_tuples(n,k).
1227
1228    Wraps GAP's NrPartitionTuples.
1229
1230    EXAMPLES:
1231        sage: number_of_partitions_tuples(3,2)
1232        10
1233        sage: number_of_partitions_tuples(8,2)
1234        185
1235
1236    Now we compare that with the result of the following GAP
1237    computation:
1238 \begin{verbatim}
1239        gap> S8:=Group((1,2,3,4,5,6,7,8),(1,2));
1240        Group([ (1,2,3,4,5,6,7,8), (1,2) ])
1241        gap> C2:=Group((1,2));
1242        Group([ (1,2) ])
1243        gap> W:=WreathProduct(C2,S8);
1244        <permutation group of size 10321920 with 10 generators>
1245        gap> Size(W);
1246        10321920     ## = 2^8*Factorial(8), which is good:-)
1247        gap> Size(ConjugacyClasses(W));
1248        185
1249\end{verbatim}
1250    """
1251    ans=gap.eval("NrPartitionTuples(%s,%s)"%(ZZ(n),ZZ(k)))
1252    return ZZ(ans)
1253
1254def partition_power(pi,k):
1255    """
1256    partition_power( pi, k ) returns the partition corresponding to the
1257    $k$-th power of a permutation with cycle structure pi
1258    (thus describes the powermap of symmetric groups).
1259
1260    Wraps GAP's PowerPartition.
1261
1262    EXAMPLES:
1263        sage: partition_power([5,3],1)
1264        [5, 3]
1265        sage: partition_power([5,3],2)
1266        [5, 3]
1267        sage: partition_power([5,3],3)
1268        [5, 1, 1, 1]
1269        sage: partition_power([5,3],4)
1270        [5, 3]
1271
1272     Now let us compare this to the power map on $S_8$:
1273
1274        sage: G = SymmetricGroup(8)
1275        sage: g = G([(1,2,3,4,5),(6,7,8)])
1276        sage: g
1277        (1,2,3,4,5)(6,7,8)
1278        sage: g^2
1279        (1,3,5,2,4)(6,8,7)
1280        sage: g^3
1281        (1,4,2,5,3)
1282        sage: g^4
1283        (1,5,4,3,2)(6,7,8)
1284
1285    """
1286    ans=gap.eval("PowerPartition(%s,%s)"%(pi,ZZ(k)))
1287    return eval(ans)
1288
1289def partition_sign(pi):
1290    r"""
1291    partition_sign( pi ) returns the sign of a permutation with cycle structure
1292    given by the partition pi.
1293
1294    This function corresponds to a homomorphism from the symmetric group
1295    $S_n$ into the cyclic group of order 2, whose kernel is exactly the
1296    alternating group $A_n$. Partitions of sign $1$ are called {\it even partitions}
1297    while partitions of sign $-1$ are called {\it odd}.
1298
1299    Wraps GAP's SignPartition.
1300
1301    EXAMPLES:
1302        sage: partition_sign([5,3])
1303        1
1304        sage: partition_sign([5,2])
1305        -1
1306
1307    {\it Zolotarev's lemma} states that the Legendre symbol
1308    $\left(\frac{a}{p}\right)$ for an integer $a \pmod p$ ($p$ a prime number),
1309    can be computed as sign(p_a), where sign denotes the sign of a permutation
1310    and p_a the permutation of the residue classes $\pmod p$ induced by
1311    modular multiplication by $a$, provided $p$ does not divide $a$.
1312
1313    We verify this in some examples.
1314
1315        sage: F = GF(11)
1316        sage: a = F.multiplicative_generator();a
1317        2
1318        sage: plist = [int(a*F(x)) for x in range(1,11)]; plist
1319        [2, 4, 6, 8, 10, 1, 3, 5, 7, 9]
1320
1321    This corresponds ot the permutation (1, 2, 4, 8, 5, 10, 9, 7, 3, 6)
1322    (acting the set $\{1,2,...,10\}$) and to the partition [10].
1323
1324        sage: p = PermutationGroupElement('(1, 2, 4, 8, 5, 10, 9, 7, 3, 6)')
1325        sage: p.sign()
1326        -1
1327        sage: partition_sign([10])
1328        -1
1329        sage: kronecker_symbol(11,2)
1330        -1
1331
1332    Now replace $2$ by $3$:
1333
1334        sage: plist = [int(F(3*x)) for x in range(1,11)]; plist
1335        [3, 6, 9, 1, 4, 7, 10, 2, 5, 8]
1336        sage: range(1,11)
1337        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
1338        sage: p = PermutationGroupElement('(3,4,8,7,9)')
1339        sage: p.sign()
1340        1
1341        sage: kronecker_symbol(3,11)
1342        1
1343        sage: partition_sign([5,1,1,1,1,1])
1344        1
1345
1346    In both cases, Zolotarev holds.
1347
1348    REFERENCES:
1349        http://en.wikipedia.org/wiki/Zolotarev's_lemma
1350    """
1351    ans=gap.eval("SignPartition(%s)"%(pi))
1352    return sage_eval(ans)
1353
1354def partition_associated(pi):
1355    """
1356    partition_associated( pi ) returns the associated'' (also called
1357    conjugate'' in the literature) partition of the partition pi which is
1358    obtained by transposing the corresponding Ferrers diagram.
1359
1360    Wraps GAP's AssociatedPartition.
1361
1362    EXAMPLES:
1363        sage: partition_associated([2,2])
1364        [2, 2]
1365        sage: partition_associated([6,3,1])
1366        [3, 2, 2, 1, 1, 1]
1367        sage: print ferrers_diagram([6,3,1])
1368        ******
1369        ***
1370        *
1371        sage: print ferrers_diagram([3,2,2,1,1,1])
1372        ***
1373        **
1374        **
1375        *
1376        *
1377        *
1378    """
1379    ans=gap.eval("AssociatedPartition(%s)"%(pi))
1380    return eval(ans)
1381
1382## related functions
1383
1384def bernoulli_polynomial(x,n):
1385    r"""
1386    The generating function for the Bernoulli polynomials is
1387    $1388 \frac{t e^{xt}}{e^t-1}= \sum_{n=0}^\infty B_n(x) \frac{t^n}{n!}. 1389$
1390
1391    One has $B_n(x) = - n\zeta(1 - n,x)$, where $\zeta(s,x)$ is the
1392    Hurwitz zeta function.  Thus, in a certain sense, the Hurwitz zeta
1393    generalizes the Bernoulli polynomials to non-integer values of n.
1394
1395    EXAMPLES:
1396        sage: y = QQ['y'].0
1397        sage: bernoulli_polynomial(y,5)
1398        y^5 - 5/2*y^4 + 5/3*y^3 - 1/6*y
1399
1400    REFERENCES:
1401        http://en.wikipedia.org/wiki/Bernoulli_polynomials
1402    """
1403    return sage_eval(maxima.eval("bernpoly(x,%s)"%n), {'x':x})
1404
1405
1406#def hurwitz_zeta(s,x,N):
1407#    """
1408#    Returns the value of the $\zeta(s,x)$ to $N$ decimals, where s and x are real.
1409#
1410#    The Hurwitz zeta function is one of the many zeta functions. It defined as
1411#    $1412# \zeta(s,x) = \sum_{k=0}^\infty (k+x)^{-s}. 1413#$
1414#    When $x = 1$, this coincides with Riemann's zeta function. The Dirichlet L-functions
1415#    may be expressed as a linear combination of Hurwitz zeta functions.
1416#
1417#    EXAMPLES:
1418#        sage: hurwitz_zeta(3,1/2,6)
1419#        '8.41439b0'
1420#        sage: hurwitz_zeta(1.1,1/2,6)
1421#        'Warning:Floattobigfloatconversionof12.1040625294406841.21041b1'
1422#
1423#    "b0" can be ignored, but "b1" means that the decimal point was shifted
1424#    1 to the left (so the answer is not 1.21041b1 but 12.10406).
1425#
1426#    REFERENCES:
1427#        http://en.wikipedia.org/wiki/Hurwitz_zeta_function
1428#
1429#    """