gh_Zz      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxy z{|}~z{|}~z{|}~"8A binary tree with leaves and internal nodes decorated  with types a and b, respectively. .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. &  !"!    !"!  !"1#;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. *Returns n2, where the input is a permutation of the numbers [1..n] +,-.This is compatible with Maple's  convert(perm,'disjcyc'). /01Plus 1 or minus 1. 239Action 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. 4The list should be of length n. 5*Multiplies two permutations together. See 3 for our  conventions. 6The inverse permutation 7A synonym for 9 89Permutations of [1..n]* in lexicographic order, naive algorithm. :;# = n! <A synonym for @. =>A synonym for A. ?@,Generates a uniformly random permutation of [1..n].  Durstenfeld's algorithm (see  *http://en.wikipedia.org/wiki/Knuth_shuffle). AGenerates a uniformly random cyclic permutation of [1..n].  Sattolo's algorithm (see  *http://en.wikipedia.org/wiki/Knuth_shuffle). B,Generates all permutations of a multiset. - The order is lexicographic. A synonym for D C# = \frac { (sum_i n_i) ! } { \prod_i (n_i !) } D*Generates all permutations of a multiset  (based on " algorithm L"& in Knuth; somewhat less efficient). ! The order is lexicographic. "#$%&'()*+,-./0123456789:;<=>?@ABCD"$#%&'()*+,.-/0123456789:;<=>?@ABCD"#$%&'()*+,-./0123456789:;<=>?@ABCDE;The additional invariant enforced here is that partitions ; are monotone decreasing sequences of positive integers. FSorts the input. G&Assumes that the input is decreasing. H)Checks whether the input is a partition. IJK#The first element of the sequence. LThe length of the sequence. MNThe weight of the partition 5 (that is, the sum of the corresponding sequence). O#The dual (or conjugate) partition. PQ;Partitions of d, fitting into a given rectangle, as lists. (height,width) d RSPartitions of d, fitting into a given rectangle. The order is again lexicographic. (height,width) d STPartitions of d, as lists UPartitions of d. VW/All partitions fitting into a given rectangle. (height,width) X%All partitions up to a given degree. Y# = \binom { h+w } { h } ZEFGHIJKLMNOPQRSTUVWXYZEHGFIJKLMNPOQRSTUVWXYZEFGHIJKLMNOPQRSTUVWXYZ [\]^_`abcd*Standard Young tableaux of a given shape. " Adapted from John Stembridge,   ?http://www.math.lsa.umich.edu/~jrs/software/SFexamples/tableaux. ehook-length formula [\]^_`abcde [\]^_`abcde [\]^_`abcdefCCombinations 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 gh-All combinations fitting into a given shape. i Combinations of a given length. length sum j# = \binom { len+d-1 } { len-1 } k)Positive combinations of a given length. length sum lfghijklfghijklfghijkl m"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]] n positive "tuples" fitting into a give shape. o# = \prod_i (m_i + 1) p# = \ prod_i m_i qlength (width) maximum (height) rlength (width) maximum (height) s# = (m+1) ^ len t# = m ^ len u mnopqrstu mnopqrstu mnopqrstuv4Sublists of a list having given number of elements. w# = binom { n } { k }. xAll sublists of a list. y# = 2^n. vwxyvxwyvwxy  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxy    !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ -.Ocombinat-0.2.1 Math.CombinatMath.Combinat.TreesMath.Combinat.PermutationsMath.Combinat.PartitionsMath.Combinat.TableauxMath.Combinat.CombinationsMath.Combinat.TuplesMath.Combinat.SetsMath.Combinat.Helper factorialbinomialParen RightParen LeftParenBinTree'Leaf'Branch'BinTreeLeafBranchleafforgetNodeDecorationsparenthesesToStringstringToParenthesesforestToNestedParenthesesforestToBinaryTreenestedParenthesesToForestnestedParenthesesToForestUnsafenestedParenthesesToBinaryTree#nestedParenthesesToBinaryTreeUnsafebinaryTreeToNestedParenthesesbinaryTreeToForestnestedParenthesesrandomNestedParenthesesnthNestedParenthesescountNestedParenthesesfasc4A_algorithm_Pfasc4A_algorithm_Wfasc4A_algorithm_U binaryTreescountBinaryTreesbinaryTreesNaiverandomBinaryTreefasc4A_algorithm_RDisjointCycles PermutationfromPermutationpermutationArraytoPermutationUnsafe isPermutation toPermutationpermutationSizefromDisjointCyclesdisjointCyclesUnsafedisjointCyclesToPermutationpermutationToDisjointCyclesisEvenPermutationisOddPermutationsignOfPermutationisCyclicPermutationpermute permuteListmultiplyinverse permutations _permutationspermutationsNaive_permutationsNaivecountPermutationsrandomPermutation_randomPermutationrandomCyclicPermutation_randomCyclicPermutationrandomPermutationDurstenfeldrandomCyclicPermutationSattolopermuteMultisetcountPermuteMultisetfasc2B_algorithm_L Partition mkPartitiontoPartitionUnsafe toPartition isPartition fromPartitionheightwidth heightWidthweight dualPartition_dualPartition _partitions' partitions'countPartitions' _partitions partitionscountPartitionsallPartitions' allPartitionscountAllPartitions'countAllPartitionsTableau_shapeshape dualTableauhooksrowWordrowWordToTableau columnWordcolumnWordToTableaustandardYoungTableauxcountStandardYoungTableaux combinations'countCombinations'allCombinations' combinationscountCombinations combinations1countCombinations1tuples'tuples1' countTuples' countTuples1'tuplestuples1 countTuples countTuples1 binaryTuples kSublistscountKSublistssublists countSublistsdebugswapcountfromJustnestreverseOrderingreverseCompare intToBool boolToIntunfold1unfold unfoldEitherunfoldM mapAccumM parenToCharcontainers-0.3.0.0 Data.Tree subForest rootLabelNodeTreeForestSameSizeCyclicPermutationCyclic fromCyclicNatfromNatElem#randomPermutationDurstenfeldSattolo naturalSetsameSize