—      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuv w x y z { | } ~   "Tuples"A fitting into a give shape. The order is lexicographic, that is,  ( sort ts == ts where ts = tuples' shape  Example:  tuples' [2,3] = M [[0,0],[0,1],[0,2],[0,3],[1,0],[1,1],[1,2],[1,3],[2,0],[2,1],[2,2],[2,3]]  positive "tuples" fitting into a give shape. # = \prod_i (m_i + 1) # = \ prod_i m_i length (width) maximum (height) length (width) maximum (height) # = (m+1) ^ len # = m ^ len      (-1)^k  A000142.  A006882.  A007318. Catalan numbers. OEIS:A000108. Catalan's triangle. OEIS:A009766.  Note: " catalanTriangle n n == catalan n G catalanTriangle n k == countStandardYoungTableaux (toPartition [n,k]) CRows of (signed) Stirling numbers of the first kind. OEIS:A008275.  Coefficients of the polinomial (x-1)*(x-2)*...*(x-n+1). + This function uses the recursion formula. ;(Signed) Stirling numbers of the first kind. OEIS:A008275.  This function uses signedStirling1stArray, so it shouldn' t be used  to compute many Stirling numbers. =(Unsigned) Stirling numbers of the first kind. OEIS:A008275.  This function uses signedStirling1stArray, so it shouldn' t be used  to compute many Stirling numbers. 3Stirling numbers of the second kind. OEIS:A008277. ) This function uses an explicit formula. Bernoulli numbers. bernoulli 1 == -1%2 and bernoulli k == 0 for  k>2 and odd<. This function uses the formula involving Stirling numbers A of the second kind. Numerators: A027641, denominators: A027642.   All possible ways to choose k elements from a list, without  repetitions. "Antisymmetric power" for lists. Synonym for  kSublists. All possible ways to choose k elements from a list, with repetitions.  "Symmetric power" for lists. See also Math.Combinat.Combinations.  TODO: better name? " Tensor power" for lists.  See also Math.Combinat.Tuples.  TODO: better name? 4Sublists of a list having given number of elements. # = binom { n } { k }. All sublists of a list. # = 2^n. CCombinations fitting into a given shape and having a given degree. ) The order is lexicographic, that is, 0 sort cs == cs where cs = combinations' shape k shape sum -All combinations fitting into a given shape.  Combinations of a given length. length sum # = \binom { len+d-1 } { len-1 } )Positive combinations of a given length. length sum ! ! ! !";The additional invariant enforced here is that partitions ; are monotone decreasing sequences of positive integers. #Sorts the input. $&Assumes that the input is decreasing. %)Checks whether the input is a partition. &'(#The first element of the sequence. )The length of the sequence. *+The weight of the partition 5 (that is, the sum of the corresponding sequence). ,#The dual (or conjugate) partition. -./0;Partitions of d, fitting into a given rectangle, as lists. (height,width) d 1SPartitions of d, fitting into a given rectangle. The order is again lexicographic. (height,width) d 23Partitions of d, as lists 4Partitions of d. 56/All partitions fitting into a given rectangle. (height,width) 7%All partitions up to a given degree. 8# = \binom { h+w } { h } 9"#$%&'()*+,-./0123456789"%$#&'()*+-,/.0123456789"#$%&'()*+,-./0123456789%:;Disjoint cycle notation for permutations. Internally it is [[Int]]. ;NStandard notation for permutations. Internally it is an array of the integers [1..n]. <=>7Assumes that the input is a permutation of the numbers [1..n]. ?9Checks whether the input is a permutation of the numbers [1..n]. @Checks the input. AReturns n2, where the input is a permutation of the numbers [1..n] BCDEThis is compatible with Maple's  convert(perm,'disjcyc'). FGHPlus 1 or minus 1. IJ9Action of a permutation on a set. If our permutation is  encoded with the sequence  [p1,p2,...,pn], then in the  two-line notation we have   ( 1 2 3 ... n )  ( p1 p2 p3 ... pn ) .We adopt the convention that permutations act  on the left 5 (as opposed to Knuth, where they act on the right).  Thus,  C permute pi1 (permute pi2 set) == permute (pi1 `multiply` pi2) set 3The second argument should be an array with bounds (1,n). ' The function checks the array bounds. KThe list should be of length n. L*Multiplies two permutations together. See J for our  conventions. MThe inverse permutation NA synonym for P OPPermutations of [1..n]* in lexicographic order, naive algorithm. QR# = n! SA synonym for W. TUA synonym for X. VW,Generates a uniformly random permutation of [1..n].  Durstenfeld's algorithm (see  *http://en.wikipedia.org/wiki/Knuth_shuffle). XGenerates a uniformly random cyclic permutation of [1..n].  Sattolo's algorithm (see  *http://en.wikipedia.org/wiki/Knuth_shuffle). Y,Generates all permutations of a multiset. - The order is lexicographic. A synonym for [ Z# = \frac { (sum_i n_i) ! } { \prod_i (n_i !) } [*Generates all permutations of a multiset  (based on " algorithm L"& in Knuth; somewhat less efficient). ! The order is lexicographic. ":;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[";:<=>?@ABCEDFGHIJKLMNOPQRSTUVWXYZ[":;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`a An element (i,j)2 of the resulting tableau (which has shape of the F given partition) means that the vertical part of the hook has length i,  and the horizontal part j. The  hook length is thus i+j-1.  Example: - > mapM_ print $ hooks $ toPartition [5,4,1] ! [(3,5),(2,4),(2,3),(2,2),(1,1)]  [(2,4),(1,3),(1,2),(1,1)]  [(1,1)] bcdefg*Standard Young tableaux of a given shape. " Adapted from John Stembridge,   ?http://www.math.lsa.umich.edu/~jrs/software/SFexamples/tableaux. hhook-length formula i,Semistandard Young tableaux of given shape, "naive" algorithm jStanley'$s hook formula (cf. Fulton page 55) \]^_`abcdefghij\]^_`abcdefghij\]^_`abcdefghijkSet of (i,j) pairs with i>=j>=1. lmnTriangular arrays opqrsGenerates all tableaux of size k. Effective for k<=6. tu \klmnopqrstu \klmnpostuqr klmlmnopqrstu "vwxy8A binary tree with leaves and internal nodes decorated  with types a and b, respectively. z{|.A binary tree with leaves decorated with type a. }~ Synonym for .  Synonym for .  Synonym for . <Generates all sequences of nested parentheses of length 2n. > Order is lexigraphic (when right parentheses are considered  smaller then left ones).  Based on " Algorithm P") in Knuth, but less efficient because of  the " idiomatic" code. NGenerates a uniformly random sequence of nested parentheses of length 2n.  Based on " Algorithm W" in Knuth. 2Nth sequence of nested parentheses of length 2n.  The order is the same as in .  Based on " Algorithm U" in Knuth. n N; should satisfy 1 <= N <= C(n) *Generates all binary trees with n nodes. $ At the moment just a synonym for . # = Catalan(n) = \frac { 1 } { n+1 } \binom { 2n } { n }. GThis is also the counting function for forests and nested parentheses. >Generates all binary trees with n nodes. The naive algorithm. 1Generates an uniformly random binary tree, using . 'Grows a uniformly random binary tree.  " Algorithm R" (Remy's procudere) in Knuth. J Nodes are decorated with odd numbers, leaves with even numbers (from the  set [0..2n]#). Uses mutable arrays internally. &vwxyz{|}~!|~}y{zvxw!vxwwxy{zz{|~}}~   !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijvwxyz{|}~   !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwwxyz{|}~          .FG combinat-0.2.2Math.Combinat.TuplesMath.Combinat.NumbersMath.Combinat.SetsMath.Combinat.CombinationsMath.Combinat.PartitionsMath.Combinat.PermutationsMath.Combinat.TableauxMath.Combinat.Tableaux.KostkaMath.Combinat.TreesMath.Combinat.Helper Math.Combinattuples'tuples1' countTuples' countTuples1'tuplestuples1 countTuples countTuples1 binaryTuples paritySign factorialdoubleFactorialbinomialcatalancatalanTrianglesignedStirling1stArraysignedStirling1stunsignedStirling1st stirling2nd bernoullichoosecombinetuplesFromList kSublistscountKSublistssublists countSublists combinations'countCombinations'allCombinations' combinationscountCombinations combinations1countCombinations1 Partition mkPartitiontoPartitionUnsafe toPartition isPartition fromPartitionheightwidth heightWidthweight dualPartition_dualPartitionelements _elements _partitions' partitions'countPartitions' _partitions partitionscountPartitionsallPartitions' allPartitionscountAllPartitions'countAllPartitionsDisjointCycles PermutationfromPermutationpermutationArraytoPermutationUnsafe isPermutation toPermutationpermutationSizefromDisjointCyclesdisjointCyclesUnsafedisjointCyclesToPermutationpermutationToDisjointCyclesisEvenPermutationisOddPermutationsignOfPermutationisCyclicPermutationpermute permuteListmultiplyinverse permutations _permutationspermutationsNaive_permutationsNaivecountPermutationsrandomPermutation_randomPermutationrandomCyclicPermutation_randomCyclicPermutationrandomPermutationDurstenfeldrandomCyclicPermutationSattolopermuteMultisetcountPermuteMultisetfasc2B_algorithm_LTableau_shapeshape dualTableaucontenthooks hookLengthsrowWordrowWordToTableau columnWordcolumnWordToTableaustandardYoungTableauxcountStandardYoungTableauxsemiStandardYoungTableauxcountSemiStandardYoungTableauxTriunTriTriangularArraytriangularArrayUnsafefromTriangularArray kostkaContent_kostkaContentkostkaTableaux_kostkaTableauxcountKostkaTableauxParen RightParen LeftParenBinTree'Leaf'Branch'BinTreeLeafBranchleafforgetNodeDecorationsparenthesesToStringstringToParenthesesforestToNestedParenthesesforestToBinaryTreenestedParenthesesToForestnestedParenthesesToForestUnsafenestedParenthesesToBinaryTree#nestedParenthesesToBinaryTreeUnsafebinaryTreeToNestedParenthesesbinaryTreeToForestnestedParenthesesrandomNestedParenthesesnthNestedParenthesescountNestedParenthesesfasc4A_algorithm_Pfasc4A_algorithm_Wfasc4A_algorithm_U binaryTreescountBinaryTreesbinaryTreesNaiverandomBinaryTreefasc4A_algorithm_RdebugswapequatingreverseOrderingreverseCompare groupSortBynubOrdcountfromJust intToBool boolToIntnestunfold1unfold unfoldEitherunfoldM mapAccumM#randomPermutationDurstenfeldSattoloReverseHoleTableauReverseTableauHolebinom2index'deIndex'toHolenextHolereverseTableau normalize normalize' startHole enumHoleshelper newLines'newLinessizes' parenToCharcontainers-0.3.0.0 Data.Tree subForest rootLabelNodeTreeForest