y      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijk l m n o p q r s t u v w x y z { | } ~        !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                        #Safe ,Integer vectors. The indexing starts from 1. +Vector partitions. Basically a synonym for .jGenerates all vector partitions ("algorithm M" in Knuth). The order is decreasing lexicographic.     SafeNPartitions of a multiset. Internally, this uses the vector partition algorithmSafeGenerates graphviz .dot file from a forest. The first argument tells whether to make the individual trees clustered subgraphs; the second is the name of the graph.Generates graphviz .dot@ file from a tree. The first argument is the name of the graph.-make the individual trees clustered subgraphs#reverse the direction of the arrowsname of the graph"reverse the direction of the arrowname of the graphSafe2Infinite list of primes, using the TMWE algorithm.YA relatively simple but still quite fast implementation of list of primes. By Will Ness Ghttp://www.haskell.org/pipermail/haskell-cafe/2009-November/068441.html?List of primes, using tree merge with wheel. Code by Will Ness.TGroups integer factors. Example: from [2,2,2,3,3,5] we produce [(2,3),(3,2),(5,1)] #The naive trial division algorithm. Largest integer k such that 2^k is smaller or equal to n!Smallest integer k such that 2^k is larger or equal to n#Integer square root (largest integer whose square is smaller or equal to the input) using Newton's method, with a faster (for large numbers) inital guess based on bit shifts.$=Smallest integer whose square is larger or equal to the input%*We also return the excess residue; that is (a,r) = integerSquareRoot' n means that "a*a + r = n a*a <= n < (a+1)*(a+1)&xNewton's method without an initial guess. For very small numbers (<10^10) it is somewhat faster than the above version.'Efficient powers modulo m. powerMod a k m == (a^k) `mod` m(eMiller-Rabin Primality Test (taken from Haskell wiki). We test the primality of the first argument n by using the second argument a' as a candidate witness. If it returs False, then n is composite. If it returns True, then n is either prime or composite.A random choice between 2 and (n-2) is a good choice for a.)nFor very small numbers, we use trial division, for larger numbers, we apply the Miller-Rabin primality test log4(n)B times, with candidate witnesses derived deterministically from n) using a pseudo-random sequence (which  should be: based on a cryptographic hash function, but isn't, yet). Thus the candidate witnesses should behave essentially like random, but the resulting function is still a deterministic, pure function.8TODO: implement the hash sequence, at the moment we use !" instead...*A more exhaustive version of )r, this one tests candidate witnesses both the first log4(n) prime numbers and then log4(n) pseudo-random numbersGiven an integer nK, we initialize a system random generator with using a seed derived from nt (note that this uses at most 32 or 64 bits), and generate an infinite sequence of pseudo-random integers between 0..n-1(, generated by that random generator. JNote that this is not really a preferred way of generating such sequences! !"#$%&'()* !"#$%&'()* !"#$%&'()* !"#$%&'()*Safe +,ADOT+/Hide the type parameter of a functor. Example:  Some Braid4Uses the value inside a +5Monadic version of 46ZGiven a polymorphic value, we select at run time the one specified by the second argument7Monadic version of 68Combination of 6 and 4R: we make a temporary structure of the given size, but we immediately consume it.9(Half-)monadic version of 8+,-./0123456789+,-./0123456789-./0123+,456789+,-./0123456789None+DI:The Rand monad transformer<,A simple random monad to make life suck lessLThe boolean argument will True only for the last elementO8extend lines with spaces so that they have the same linecThis may be occasionally usefuld9Puts a standard-conforming random function into the monad.:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefg.:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefg.=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_<`a:;bcdefg-:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefg Safe<=?k Number of cycles (of partitions)mNumber of leaves (of trees)oNumber of nodes (of trees)q"Shape (of tableaux, skew tableaux)s&Duality (of partitions, tableaux, etc)u%Weight (of partitions, tableaux, etc){Number of parts} Emptynessklmnopqrstuvwxyz{|}~klmnopqrstuvwxyz{|}~}~{|yzwxuvstqropmnkl klmnopqrstuvwxyz{|}~ None-Order of elements in a matrixVertical separatorempty separatorn spaces$some custom list of characters, eg. " - "5 (the characters are interpreted as below each other)Horizontal separatorempty separatorn spacessome custom string, eg. " | "Vertical alignmentHorizontal alignment1A type class to have a simple way to draw things nThe type of a (rectangular) ASCII figure. Internally it is a list of lines of the same length plus the size.LNote: The Show instance is pretty-printing, so that it's convenient in ghci.An empty (0x0) rectangle4Horizontal append, centrally aligned, no separation.2Vertical append, centrally aligned, no separation.4Horizontal concatenation, top-aligned, no separation7Horizontal concatenation, bottom-aligned, no separation3Vertical concatenation, left-aligned, no separation4Vertical concatenation, right-aligned, no separation General horizontal concatenationGeneral vertical concatenation@Horizontally pads with the given number of spaces, on both sidesCVertically pads with the given number of empty lines, on both sidesAPads by single empty lines vertically and two spaces horizontallyExtends an ASCII figure with spaces horizontally to the given width. Note: the alignment is the alignment of the original picture in the new bigger picture!Extends an ASCII figure with spaces vertically to the given height. Note: the alignment is the alignment of the original picture in the new bigger picture!4Extend horizontally with the given number of spaces.7Extend vertically with the given number of empty lines.Horizontal indentationVertical indentation[Cuts the given number of columns from the picture. The alignment is the alignment of the picture, not the cuts.%This should be the (left) inverse of .XCuts the given number of rows from the picture. The alignment is the alignment of the picture, not the cuts.%This should be the (left) inverse of .Pastes the first ASCII graphics onto the second, keeping the second one's dimension (that is, overlapping parts of the first one are ignored). The offset is relative to the top-left corner of the second picture. Spaces at treated as transparent.Example: tabulate (HCenter,VCenter) (HSepSpaces 2, VSepSpaces 1) [ [ caption (show (x,y)) $ pasteOnto (x,y) (filledBox '@' (4,3)) (asciiBox (7,5)) | x <- [-4..7] ] | y <- [-3..5] ]Pastes the first ASCII graphics onto the second, keeping the second one's dimension. The first argument specifies the transparency condition (on the first picture). The offset is relative to the top-left corner of the second picture. A version of X where we can specify the corner of the second picture to which the offset is relative: &pasteOntoRel (HLeft,VTop) == pasteOnto0Tabulates the given matrix of pictures. Example: tabulate (HCenter, VCenter) (HSepSpaces 2, VSepSpaces 1) [ [ asciiFromLines [ "x=" ++ show x , "y=" ++ show y ] | x<-[7..13] ] | y<-[98..102] ])Automatically tabulates ASCII rectangles.4Adds a caption to the bottom, with default settings."Adds a caption to the bottom. The BoolL flag specifies whether to add an empty between the caption and the figure&An ASCII border box of the given size /An "rounded" ASCII border box of the given size,A box simply filled with the given characterA box of spaces An integerHtransparency condition<offset relative to the top-left corner of the second picturepicture to pastepicture to paste ontoAwhether to use row-major or column-major ordering of the elements (Right x) creates x columns, while (Left y) creates y rowslist of ASCII rectanglesGH5 NoneH"Tuples" fitting into a give shape. The order is lexicographic, that is, &sort ts == ts where ts = tuples' shape Example: \tuples' [2,3] = [[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# = (m+1) ^ len # = m ^ len length (width)maximum (height)length (width)maximum (height) Safe+1 or -1+Negate the second argument if the first is  if even,  if odd (-1)^k.Negate the second argument if the first is odd   NoneA000142.A006882. A007318. Note: This is zero for n<0 or k<0 ; see also  below.hThe extension of the binomial function to negative inputs. This should satisfy the following properties: for n,k >=0 : signedBinomial n k == binomial n k for any n,k : signedBinomial n k == signedBinomial n (n-k) for k >= 0 : signedBinomial (-n) k == (-1)^k * signedBinomial (n+k-1) k,Note: This is compatible with Mathematica's Binomial function.A given row of the Pascal triangle; equivalent to a sequence of binomial numbers, but much more efficient. You can also left-fold over it. +pascalRow n == [ binomial n k | k<-[0..n] ]Catalan numbers. OEIS:A000108.(Catalan's triangle. OEIS:A009766. Note: fcatalanTriangle n n == catalan n 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.O(Signed) Stirling numbers of the first kind. OEIS:A008275. This function uses &, so it shouldn't be used to compute many Stirling numbers.Argument order: signedStirling1st n k3(Unsigned) Stirling numbers of the first kind. See .[Stirling numbers of the second kind. OEIS:A008277. This function uses an explicit formula.Argument order: stirling2nd n kBernoulli numbers. bernoulli 1 == -1%2 and bernoulli k == 0 for k>2 and odd|. This function uses the formula involving Stirling numbers of the second kind. Numerators: A027641, denominators: A027642.PBell numbers (Sloane's A000110) from B(0) up to B(n). B(0)=B(1)=1, B(2)=2, etc. %The Bell numbers count the number of set partitions of a set of size nSee (http://en.wikipedia.org/wiki/Bell_numberiThe n-th Bell number B(n), using the Stirling numbers of the second kind. This may be slower than using .NoneOT choose_ k n' returns all possible ways of choosing k disjoint elements from [1..n] choose_ k n == choose k [1..n]All possible ways to choose kZ elements from a list, without repetitions. "Antisymmetric power" for lists. Synonym for . A version of * which also returns the complementer sets. choose k = map fst . choose' kAnother variation of . This satisfies Dchoose'' k == map (\(xs,ys) -> (map fst xs, map snd ys)) . choose' kAnother variation on Q which tags the elements based on whether they are part of the selected subset ( ) or not (): &choose k = map rights . chooseTagged kAll possible ways to choose k elements from a list, with repetitions*. "Symmetric power" for lists. See also Math.Combinat.Compositions. TODO: better name?A synonym for .*"Tensor power" for lists. Special case of : 2tuplesFromList k xs == listTensor (replicate k xs) See also Math.Combinat.Tuples. TODO: better name?"Tensor product" for lists.@Sublists of a list having given number of elements. Synonym for .# = binom { n } { k }.All sublists of a list. # = 2^n. randomChoice k n& returns a uniformly random choice of k elements from the set [1..n]Example: Zdo cs <- replicateM 10000 (getStdRandom (randomChoice 3 7)) mapM_ print $ histogram cs?From a list of $k$ numbers, where the first is in the interval [1..n], the second in [1..n-1], the third in [1..n-2], we create a size k subset of n.1Knuth's method. The first argument is the number n.?From a list of $k$ numbers, where the first is in the interval [1..n], the second in [1..n-1], the third in [1..n-2], we create a size k subset of n.        None  A  composition of an integer n into k parts is an ordered kB-tuple of nonnegative (sometimes positive) integers whose sum is n. kCompositions fitting into a given shape and having a given degree. The order is lexicographic, that is, .sort cs == cs where cs = compositions' shape kbAll positive compositions of a given number (filtrated by the length). Total number of these is 2^(n-1),All compositions fitting into a given shape.+Nonnegative compositions of a given length. # = \binom { len+d-1 } { len-1 }(Positive compositions of a given length.randomComposition k n8 returns a uniformly random composition of the number n as an (ordered) sum of k  nonnegative numbersrandomComposition1 k n8 returns a uniformly random composition of the number n as an (ordered) sum of k positive numbers   shapesum lengthsumlengthsum            None:IT3;Disjoint cycle notation for permutations. Internally it is [[Int]].4The cycles are to be understood as follows: a cycle [c1,c2,...,ck] means the permutation '( c1 c2 c3 ... ck ) ( c2 c3 c4 ... c1 )CA permutation. Internally it is an (unboxed) array of the integers [1..n]#, with indexing range also being (1,n). If this array of integers is [p1,p2,...,pn]?, then in two-line notations, that represents the permutation '( 1 2 3 ... n ) ( p1 p2 p3 ... pn )That is, it is the permutation sigma! whose (right) action on the set [1..n] is  sigma(1) = p1 sigma(2) = p2 ...((NOTE: this changed at version 0.2.8.0!)Note: this is slower than 7Assumes that the input is a permutation of the numbers [1..n].Note: Indexing starts from 1.9Checks whether 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]#:Checks whether the permutation is the identity permutation$ Synonym for &&The standard two-line notation, moving the element indexed by the top row into the place indexed by the corresponding element in the bottom row.'The inverse two-line notation, where the it's the bottom line which is in standard order. The columns of this are a permutation of the columns &.Remark: the top row of inverseTwoLineNotation perm$ is the same as the bottom row of twoLineNotation (inverse perm).((Two-line notation for any set of numbers,#Convert to disjoint cycle notation. This is compatible with Maple's convert(perm,'disjcyc') and also with Mathematica's PermutationCycles[perm]6Note however, that for example Mathematica uses the top row/ to represent a permutation, while we use the  bottom row8 - thus even though this function looks identical, the meaning, of both the input and output is different!0Plus 1 or minus 1.2An  inversion of a permutation sigma is a pair (i,j) such that i<j and sigma(i) > sigma(j).6This functions returns the inversion of a permutation.3!Returns the number of inversions: 2numberOfInversions perm = length (inversions perm) Synonym for 44RReturns the number of inversions, using the merge-sort algorithm. This should be  O(n*log(n))5BReturns the number of inversions, using the definition, thus it's O(n^2).6NBubble sorts breaks a permutation into the product of adjacent transpositions: BmultiplyMany' n (map (transposition n) $ bubbleSort2 perm) == permcNote that while this is not unique, the number of transpositions equals the number of inversions.7)Another version of bubble sort. An entry i1 in the return sequence means the transposition (i,i+1): ImultiplyMany' n (map (adjacentTransposition n) $ bubbleSort perm) == perm8The permutation [n,n-1,n-2,...,2,1](. Note that it is the inverse of itself.9OChecks whether the permutation is the reverse permutation @[n,n-1,n-2,...,2,1].:)A transposition (swapping two elements). transposition n (i,j) is the permutation of size n which swaps i'th and j 'th elements.;Product of transpositions. Mtranspositions n list == multiplyMany [ transposition n pair | pair <- list ]<adjacentTransposition n k swaps the elements k and (k+1).=#Product of adjacent transpositions. [adjacentTranspositions n list == multiplyMany [ adjacentTransposition n idx | idx <- list ]>5The permutation which cycles a list left by one step: ,permuteList (cycleLeft 5) "abcde" == "bcdea"Or in two-line notation: ( 1 2 3 4 5 ) ( 2 3 4 5 1 )?6The permutation which cycles a list right by one step: -permuteList (cycleRight 5) "abcde" == "eabcd"Or in two-line notation: ( 1 2 3 4 5 ) ( 5 1 2 3 4 )@&Multiplies two permutations together: p @ q, means the permutation when we first apply p , and then q& (that is, the natural action is the right action) See also E for our conventions. AThe inverse permutation.B&The identity (or trivial) permutation.CMultiply together a  non-empty list of permutations (the reason for requiring the list to be non-empty is that we don't know the size of the result). See also D.DQMultiply together a (possibly empty) list of permutations, all of which has size nERightU action 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 right (as in Knuth): Apermute pi2 (permute pi1 set) == permute (pi1 `multiply` pi2) set Synonym to GF"Right action on lists. Synonym to permuteListRightG5The right (standard) action of permutations on sets.  PpermuteRight pi2 (permuteRight pi1 set) == permuteRight (pi1 `multiply` pi2) set3The second argument should be an array with bounds (1,n)(. The function checks the array bounds.HDThe right (standard) action on a list. The list should be of length n. 4fromPermutation perm == permuteRightList perm [1..n]I4The left (opposite) action of the permutation group. MpermuteLeft pi2 (permuteLeft pi1 set) == permuteLeft (pi2 `multiply` pi1) setIt is related to I via: ipermuteLeft pi arr == permuteRight (inverse pi) arr permuteRight pi arr == permuteLeft (inverse pi) arrJCThe left (opposite) action on a list. The list should be of length n. xpermuteLeftList perm set == permuteList (inverse perm) set fromPermutation (inverse perm) == permuteLeftList perm [1..n]KA synonym for MMAll permutations of [1..n]) in lexicographic order, naive algorithm.O# = n!PA synonym for T.RA synonym for U.T,Generates a uniformly random permutation of [1..n] . Durstenfeld's algorithm (see  *http://en.wikipedia.org/wiki/Knuth_shuffle).UGenerates a uniformly random cyclic permutation of [1..n]. Sattolo's algorithm (see  *http://en.wikipedia.org/wiki/Knuth_shuffle).VYGenerates all permutations of a multiset. The order is lexicographic. A synonym for XW3# = \frac { (sum_i n_i) ! } { \prod_i (n_i !) } XGenerates all permutations of a multiset (based on "algorithm L" in Knuth; somewhat less efficient). The order is lexicographic. K !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_Ql !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXD !")*,+l#9-./01:;<=>?8235467BA@CDEFIGJH$%&'(KLMNOPQRSTUVWXI !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_@7NoneT/fbWhich orientation to draw the Ferrers diagrams. For example, the partition [5,4,1] corrsponds to:In standard English notation:  @@@@@ @@@@ @<In English notation rotated by 90 degrees counter-clockwise: @ @@ @@ @@ @@@And in French notation:  @ @@@@ @@@@@gEnglish notationh7English notation rotated by 90 degrees counterclockwisei:French notation (mirror of English notation to the x axis)l|A partition of an integer. The additional invariant enforced here is that partitions are monotone decreasing sequences of positive integers. The Ord instance is lexicographical.n3Sorts the input, and cuts the nonpositive elements.o%Assumes that the input is decreasing.pBChecks whether the input is an integer partition. See the note at q!q This returns True. if the input is non-increasing sequence of positive integers (possibly empty); False otherwise.u"The first element of the sequence.v:The length of the sequence (that is, the number of parts).xQThe weight of the partition (that is, the sum of the corresponding sequence).y"The dual (or conjugate) partition.{IA simpler, but bit slower (about twice?) implementation of dual partition|From a sequence  [a1,a2,..,an]' computes the sequence of differences [a1-a2,a2-a3,...,an-0]}Example: telements (toPartition [5,4,1]) == [ (1,1), (1,2), (1,3), (1,4), (1,5) , (2,1), (2,2), (2,3), (2,4) , (3,1) ]-We convert a partition to exponential form. (i,e) mean (i^e); for example  [(1,4),(2,3)] corresponds to (1^4)(2^3) = [2,2,2,1,1,1,1]. Another example: NtoExponentialForm (Partition [5,5,3,2,2,2,2,1,1]) == [(1,2),(2,4),(3,1),(5,2)]DComputes the number of "automorphisms" of a given integer partition.Partitions of d.Partitions of d , as listsNumber of partitions of n This uses , and thus is slow)Infinite list of number of partitions of  0,1,2,...zThis uses the infinite product formula the generating function of partitions, recursively expanding it; it is quite fast. /partitionCountList == map countPartitions [0..]/Naive infinite list of number of partitions of  0,1,2,... 9partitionCountListNaive == map countPartitionsNaive [0..]:This is much slower than the power series expansion above.kAll integer partitions up to a given degree (that is, all integer partitions whose sum is less or equal to d)kAll integer partitions up to a given degree (that is, all integer partitions whose sum is less or equal to d), grouped by weight6All integer partitions fitting into a given rectangle.IAll integer partitions fitting into a given rectangle, grouped by weight.# = \binom { h+w } { h }Integer partitions of d+, fitting into a given rectangle, as lists.RPartitions of d, fitting into a given rectangle. The order is again lexicographic.0Uniformly random partition of the given weight. ,NOTE: This algorithm is effective for small n-s (say n up to a few hundred / one thousand it should work nicely), and the first time it is executed may be slower (as it needs to build the table  first)+Algorithm of Nijenhuis and Wilf (1975); see+Knuth Vol 4A, pre-fascicle 3B, exercise 47;VNijenhuis and Wilf: Combinatorial Algorithms for Computers and Calculators, chapter 101Generates several uniformly random partitions of nT at the same time. Should be a little bit faster then generating them individually.q `dominates` p returns True if q >= p] in the dominance order of partitions (this is partial ordering on the set of partitions of n).See ,http://en.wikipedia.org/wiki/Dominance_order+Lists all partitions of the same weight as lambda and also dominated by lambda0 (that is, all partial sums are less or equal): UdominatedPartitions lam == [ mu | mu <- partitions (weight lam), lam `dominates` mu ]+Lists all partitions of the sime weight as mu and also dominating mu3 (that is, all partial sums are greater or equal): VdominatingPartitions mu == [ lam | lam <- partitions (weight mu), lam `dominates` mu ]Lists partitions of n into k parts. Xsort (partitionsWithKParts k n) == sort [ p | p <- partitions n , numberOfParts p == k ]Naive recursive algorithm.Partitions of n with only odd partsPartitions of n with distinct parts.Note: Klength (partitionsWithDistinctParts d) == length (partitionsWithOddParts d)Returns Truef of the first partition is a subpartition (that is, fit inside) of the second. This includes equality7This is provided for convenience/completeness only, as: .isSuperPartitionOf q p == isSubPartitionOf p q:Sub-partitions of a given partition with the given weight: Psort (subPartitions d q) == sort [ p | p <- partitions d, isSubPartitionOf p q ]'All sub-partitions of a given partition<Super-partitions of a given partition with the given weight: Rsort (superPartitions d p) == sort [ q | q <- partitions d, isSubPartitionOf p q ]The Pieri rule computes s[lambda]*h[n] as a sum of s[mu]-s (each with coefficient 1).See for example ,http://en.wikipedia.org/wiki/Pieri's_formulaThe dual Pieri rule computes s[lambda]*e[n] as a sum of s[mu]-s (each with coefficient 1) Synonym for (asciiFerrersDiagram' EnglishNotation '@'Try for example: HautoTabulate RowMajor (Right 8) (map asciiFerrersDiagram $ partitions 9)Kfghijklmnopqrstuvwxyz{|}~(height,width)(height,width)(height,width)d(height,width)d number of partitions to generatethe weight of the partitionsk = number of partsn = the integer we partitionk = number of partsn = the integer we partitionDfghijklmnopqrstuvwxyz{|}~Klmnopqrstuvwxyjkz{|}~fghiFfghijklmnopqrstuvwxyz{|}~#NoneDfghijklmnopqrstuvwxyz{|}~None9;<=3A tableau is simply represented as a list of lists.ASCII diagram of a tableauThe shape of a tableauNumber of entriesAThe dual of the tableau is the mirror image to the main diagonal.The content of a tableau is the list of its entries. The ordering is from the left to the right and then from the top to the bottom An element (i,j)x of the resulting tableau (which has shape of the 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: m> 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)]The row wordl of a tableau is the list of its entry read from the right to the left and then from the top to the bottom. Semistandard3 tableaux can be reconstructed from their row wordsThe  column wordj of a tableau is the list of its entry read from the bottom to the top and then from the left to the rightStandardD tableaux can be reconstructed from either their column or row words4Checks whether a sequence of positive integers is a  lattice wordF, which means that in every initial part of the sequence any number i) occurs at least as often as the number i+1 A tableau is  semistandardV if its entries are weekly increasing horizontally and strictly increasing verticallyASemistandard Young tableaux of given shape, "naive" algorithm +Stanley's hook formula (cf. Fulton page 55) A tableau is standard2 if it is semistandard and its content is exactly [1..n] , where n is the weight.OStandard Young tableaux of a given shape. Adapted from John Stembridge,  ?http://www.math.lsa.umich.edu/~jrs/software/SFexamples/tableaux.hook-length formulaNone9;Set of (i,j) pairs with i>=j>=1.Triangular arraysGenerates all tableaux of size k. Effective for k<=6.;Note: This is slow (it actually generates all the tableaux)<We can flip the numbers in the tableau so that the interval [1..c] becomes [c..1][. This way we a get a maybe more familiar form, when each row and each column is strictly  decreasing" (to the right and to the bottom).# NoneHA plane partition encoded as a tablaeu (the "Z" heights are the numbers)9Throws an exception if the input is not a plane partitionDThe XY projected shape of a plane partition, as an integer partition!The Z height of a plane partitionoStacks layers of partitions into a plane partition. Throws an exception if they do not form a plane partition.Stacks layers of partitions into a plane partition. This is unsafe in the sense that we don't check that the partitions fit on the top of each other.0The "layers" of a plane partition (in direction Z). We should have ,unsafeStackLayers (planePartLayers pp) == pp"Plane partitions of a given weight NoneIMThe series [1,0,0,0,0,...], which is the neutral element for the convolution.Constant zero series-Power series representing a constant function9The power series representation of the identity function x#The power series representation of x^nConvolution of series (that is, multiplication of power series). The result is always an infinite list. Warning: This is slow!3Convolution (= product) of many series. Still slow!GGiven a power series, we iteratively compute its multiplicative inverse#Given a power series starting with 1?, we can compute its multiplicative inverse without divisions. g `composeSeries` f" is the power series expansion of g(f(x)). This is a synonym for flip substitute.%We require that the constant term of f is zero. substitute f g& is the power series corresponding to g(f(x))Y. Equivalently, this is the composition of univariate functions (in the "wrong" order).yNote: for this to be meaningful in general (not depending on convergence properties), we need that the constant term of f is zero. &Coefficients of the Lagrange inversion $We expect the input series to match (0:1:_)H. The following is true for the result (at least with exact arithmetic): substitute f (integralLagrangeInversion f) == (0 : 1 : repeat 0) substitute (integralLagrangeInversion f) f == (0 : 1 : repeat 0) $We expect the input series to match (0:a1:_)X. with a1 nonzero The following is true for the result (at least with exact arithmetic): qsubstitute f (lagrangeInversion f) == (0 : 1 : repeat 0) substitute (lagrangeInversion f) f == (0 : 1 : repeat 0)Power series expansion of exp(x)Power series expansion of cos(x)Power series expansion of sin(x)Power series expansion of cosh(x)Power series expansion of sinh(x)Power series expansion of log(1+x)Power series expansion of (1-Sqrt[1-4x])/(2x)+ (the coefficients are the Catalan numbers)Power series expansion of  /1 / ( (1-x^k_1) * (1-x^k_2) * ... * (1-x^k_n) )Example:(coinSeries [2,3,5])!!k is the number of ways to pay k3 dollars with coins of two, three and five dollars.TODO: better name?BGeneralization of the above to include coefficients: expansion of <1 / ( (1-a_1*x^k_1) * (1-a_2*x^k_2) * ... * (1-a_n*x^k_n) ) Convolution of many G, that is, the expansion of the reciprocal of a product of polynomialsThe same, with coefficients.bThis is the most general function in this module; all the others are special cases of this one. The power series expansion of -1 / (1 - x^k_1 - x^k_2 - x^k_3 - ... - x^k_n)!Convolve with (the expansion of) -1 / (1 - x^k_1 - x^k_2 - x^k_3 - ... - x^k_n)The expansion of =1 / (1 - a_1*x^k_1 - a_2*x^k_2 - a_3*x^k_3 - ... - a_n*x^k_n) !Convolve with (the expansion of) =1 / (1 - a_1*x^k_1 - a_2*x^k_2 - a_3*x^k_3 - ... - a_n*x^k_n)"!Convolve with (the expansion of)  21 / (1 +- x^k_1 +- x^k_2 +- x^k_3 +- ... +- x^k_n)Should be faster than using   . Note:  corresponds to the coefficient -1 in 8 (since there is a minus sign in the definition there)!*      !"*      !"*      !"*      !"None ,/ADOQRT3#3Sometimes we want to hide the type-level parameter nT, for example when dynamically creating braids whose size is known only at runtime.%The braid group B_n on n strands. The number n: is encoded as a type level natural in the type parameter.OBraids are represented as words in the standard generators and their inverses.''A standard Artin generator of a braid: Sigma i- represents twisting the neighbour strands i and (i+1), such that strand i goes under strand (i+1).Note: The strands are numbered 1..n.(i goes under (i+1))i goes above (i+1)*OThe strand (more precisely, the first of the two strands) the generator twistes- The inverse of a braid generator."The number of strands in the braid5:Embeds a smaller braid group into a bigger braid group 6@Apply "free reduction" to the word, that is, iteratively remove sigma_i sigma_i^-1C pairs. The resulting braid is clearly equivalent to the original.7The braid generator sigma_i as a braid8The braid generator  sigma_i^(-1) as a braid9doubleSigma s t (for s<t)is the generator  sigma_{s,t}@ in Birman-Ko-Lee's "new presentation". It twistes the strands s and t* while going over all other strands. For t==s+1 we get back sigma s:positiveWord [2,5,1] is shorthand for the word sigma_2*sigma_5*sigma_1.;GThe (positive) half-twist of all the braid strands, usually denoted by Delta.<The untyped version of ;= Synonym for ;>"The inner automorphism defined by tau(X) = Delta^-1 X Delta , where Delta is the positive half-twist.This sends each generator sigma_j to  sigma_(n-j).?The involution tau% on permutations (permutation braids)@The trivial braidA|The inverse of a braid. Note: we do not perform reduction here, as a word is reduced if and only if its inverse is reduced.BMComposes two braids, doing free reduction on the result (that is, removing (sigma_k * sigma_k^-1) pairs@)D0Composes two braids without doing any reduction.E-A braid is pure if its permutation is trivialFWReturns the left-to-right permutation associated to the braid. We follow the strands from the left to the rightf (or from the top to the bottom), and return the permutation taking the left side to the right side.This is compatible with right) (standard) action of the permutations: 'permuteRight (braidPermutationRight b1)D corresponds to the left-to-right permutation of the strands; also: \(braidPermutation b1) `multiply` (braidPermutation b2) == braidPermutation (b1 `compose` b2)vWriting the right numbering of the strands below the left numbering, we got the two-line notation of the permutation.GThis is an untyped version of FH.A positive braid word contains only positive (Sigma ) generators.IA permutation braidC is a positive braid where any two strands cross at most one, and  positively. JUntyped version of I for positive words.K-For any permutation this functions returns a permutation braidx realizing that permutation. Note that this is not unique, so we make an arbitrary choice (except for the permutation  [n,n-1..1]O reversing the order, in which case the result must be the half-twist braid).4The resulting braid word will have a length at most  choose n 26 (and will have that length only for the permutation  [n,n-1..1]) kbraidPermutationRight (permutationBraid perm) == perm isPermutationBraid (permutationBraid perm) == TrueLUntyped version of KM\Returns the individual "phases" of the a permutation braid realizing the given permutation.N<We compute the linking numbers between all pairs of strands: 7linkingMatrix braid ! (i,j) == strandLinking braid i j OUntyped version of NP0The linking number between two strands numbered i and j (numbered such on the left side).QMBronfman's recursive formula for the reciprocial of the growth function of positive braids. It was already known (by Deligne) that these generating functions are reciprocials of polynomials; Bronfman [1] gave a recursive formula for them. let count n l = length $ nub $ [ braidNormalForm w | w <- allPositiveBraidWords n l ] let convertPoly (1:cs) = zip (map negate cs) [1..] pseries' (convertPoly $ bronfmanH n) == expandBronfmanH n == [ count n l | l <- [0..] ] J[1] Aaron Bronfman: Growth functions of a class of monoids. Preprint, 2001R5An infinite list containing the Bronfman polynomials: !bronfmanH n = bronfmanHsList !! nSExpands the reciprocial of H(n)V into an infinite power series, giving the growth function of the positive braids on n strands.TeHorizontal braid diagram, drawn from left to right, with strands numbered from the bottom to the topUyHorizontal braid diagram, drawn from left to right. The boolean flag indicates whether to flip the strands vertically ( means bottom-to-top,  means top-to-bottom) V,All positive braid words of the given lengthW#All braid words of the given lengthXUntyped version of VYUntyped version of WZ%Random braid word of the given length[Random positive braid word of the given length\+Given a braid word, we perturb it randomly mf times using the braid relations, so that the resulting new braid word is equivalent to the original.Useful for testing.]This version of Z0 may be convenient to avoid the type level stuff^This version of [0 may be convenient to avoid the type level stuff_Untyped version of Z`Untyped version of [?#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]number of strandslength of the random word^number of strandslength of the random word_number of strandslength of the random word`number of strandslength of the random worda>#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`?'()*+,-%&.#$/0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSaTUVWXYZ[\]^_`;#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`aNone,ADOTFTemporary data structure to be used during the normal form computation Delta^k Sigma_j L_j = Delta * sigma_j^-1 tau(L_j)f,A unique normal form for braids, called the left-greedy normal form. It looks like  Delta^i*P, where Delta is the positive half-twist, i is an integer, and P> is a positive word, which can be further decomposed into non-Delta permutation wordsM; these words themselves are not unique, but the permutations they realize are unique.aThis will solve the word problem relatively fast, though it is not the fastest known algorithm.hthe exponent of Deltaithe permutationsj/A braid word representing the given normal formkaComputes the normal form of a braid. We apply free reduction first, it should be faster that way.lLThis function does not apply free reduction before computing the normal formmRThis one uses the naive inverse replacement method. Probably somewhat slower than l.Replaces groups of  sigma_i^-1 generators by (Delta^-1 * P) , where P is a positive word.TThis should be more clever (resulting in shorter words) than the naive version below Replaces  sigma_i^-1 generators by (Delta^-1 * L_i).We move the all Delta's to the left Expands a positive$ "X-word" into a positive braid word<Expands an "X-word" into a braid word. Useful for debugging.posL k (denoted as L_k) is a  positive word which satisfies Delta = L_k * sigma_k, or: 6(inverse halfTwist) `compose` (posL k) ~=~ sigmaInv k@<Thus we can replace any word with a positive word plus some Delta^-1'sposR k n (denoted as R_k) is a permutation braid which satisfies Delta = sigma_k * R_k 6(posR k) `compose` (inverse halfTwist) ~=~ sigmaInv k@<Thus we can replace any word with a positive word plus some Delta^-1'sThe permutation posL k :: Braid n is realizingThe permutation posR k :: Braid n is realizing+We recognize left-greedy factors which are Delta4-s (easy, since they are the only ones with length  (n choose 2)), and move them to the left, returning their summed exponent and the filtered new factors. We also filter trivial permutations (which should only happen for the trivial braid, but it happens there?)nThe  starting set( of a positive braid P is the subset of [1..n-1] defined by VS(P) = [ i | P = sigma_i * Q , Q is positive ] = [ i | (sigma_i^-1 * P) is positive ] KThis function returns the starting set a positive word, assuming it is a permutation braid (see Lemma 2.4 in [2])oThe  finishing set( of a positive braid P is the subset of [1..n-1] defined by VF(P) = [ i | P = Q * sigma_i , Q is positive ] = [ i | (P * sigma_i^-1) is positive ] AThis function returns the finishing set, assuming the input is a permutation braidpThis satisfies GpermutationStartingSet p == permWordStartingSet n (_permutationBraid p)qThis satisfies IpermutationFinishingSet p == permWordFinishingSet n (_permutationBraid p)qReturns the list of permutations failing Lemma 2.5 in [2] (so an empty list means the implementaton is correct)CGiven factors defined as permutation braids, we normalize them to left-canonical form by ensuring thatfor each consecutive pair (P,Q)6 the finishing set F(P) contains the starting set S(Q)all DeltaC-s (corresponding to the reverse permutation) are moved to the left$all trivial factors are filtered outFUnfortunately, it seems that we may need multiple sweeps to do that...wDoes 1 sweep of the above normalization process. Unfortunately, it seems that we may need to do this multiple times... Given a positiveS word, we apply left-greedy factorization of that word into subwords representing permutation braids.$Example 5.1 from the above handbook: JleftGreedyFactors 7 [1,3,2,2,1,3,3,2,3,2] == [[1,3,2],[2,1,3],[3,2,3],[2]] fghijklm nopq fghijklmnopq fghijklmnopqfghijklm nopq None wA skew partition  lambda/mu' is internally represented by the list &[ (mu_i , lambda_i-mu_i) | i<-[1..n] ]ymkSkewPartition (lambda,mu) creates the skew partition  lambda/mu. Throws an error if mu is not a sub-partition of lambda.zReturns   if mu is not a sub-partition of lambda.{The weight of a skew partition is the weight of the outer partition minus the the weight of the inner partition (that is, the number of boxes present).|FThis function "cuts off" the "uninteresting parts" of a skew partition}HReturns the outer and inner partition of a skew partition, respectively: )mkSkewPartition . fromSkewPartition == id~The lambda part of  lambda/muThe mu part of  lambda/muHThe dual skew partition (that is, the mirror image to the main diagonal)LLists all skew partitions with the given outer shape and given (skew) weightJLists all skew partitions with the given outer shape and any (skew) weightLLists all skew partitions with the given inner shape and given (skew) weightwxyz{|}~wxyz{|}~wxyz{|}~wxyz{|}~None<=T >A skew tableau is represented by a list of offsets and entriesThe shape of a skew tableau LThe weight of a tableau is the weight of its shape, or the number of entriesJThe dual of a skew tableau, that is, its mirror image to the main diagonal A tableau is  semistandardV if its entries are weekly increasing horizontally and strictly increasing vertically A tableau is standard2 if it is semistandard and its content is exactly [1..n] , where n is the weight.8All semi-standard skew tableaux filled with the numbers [1..n]<ASCII drawing of a skew tableau (using the English notation)/The reversed (right-to-left) rows, concatenated2The reversed (bottom-to-top) columns, concatenated7Fills a skew partition with content, in row word order :Fills a skew partition with content, in column word order ZIf the skew tableau's row word is a lattice word, we can make a partition from its contentBstring representing the elements of the inner (unfilled) partition orientationNoneT A Gelfand-Tstetlin tableauHKostka numbers (via counting Gelfand-Tsetlin patterns). See for example *http://en.wikipedia.org/wiki/Kostka_numberK(lambda,mu)==0 unless lambda dominates mu: [[ mu | mu <- partitions (weight lam) , kostkaNumber lam mu > 0 ] == dominatedPartitions lamFVery naive (and slow) implementation of Kostka numbers, for reference.$Lists all (positive) Kostka numbers  K(lambda,mu) with the given lambda: xkostkaNumbersWithGivenLambda lambda == Map.fromList [ (mu , kostkaNumber lambda mu) | mu <- dominatedPartitions lambda ]_It's much faster than computing the individual Kostka numbers, but not as fast as it could be.$Lists all (positive) Kostka numbers  K(lambda,mu) with the given mu: ukostkaNumbersWithGivenMu mu == Map.fromList [ (lambda , kostkaNumber lambda mu) | lambda <- dominatingPartitions mu ]CThis function uses the iterated Pieri rule, and is relatively fast.MGenerates all Kostka-Gelfand-Tsetlin tableau, that is, triangular arrays like /[ 3 ] [ 3 , 2 ] [ 3 , 1 , 0 ] [ 2 , 0 , 0 , 0 ]_with both rows and column non-increasing such that the top diagonal read lambda (in this case  lambda=[3,2]>) and the diagonal sums are partial sums of mu (in this case  mu=[2,1,1,1])BThe number of such GT tableaux is the Kostka number K(lambda,mu).-This returns the corresponding Kostka number: ^countKostkaGelfandTsetlinPatterns lambda mu == length (kostkaGelfandTsetlinPatterns lambda mu) Computes the Schur expansion of h[n1]*h[n2]*h[n3]*...*h[nk]n via iterating the Pieri rule. Note: the coefficients are actually the Kostka numbers; the following is true: vMap.toList (iteratedPieriRule (fromPartition mu)) == [ (lam, kostkaNumber lam mu) | lam <- dominatingPartitions mu ]KThis should be faster than individually computing all these Kostka numbers.AIterating the Pieri rule, we can compute the Schur expansion of %h[lambda]*h[n1]*h[n2]*h[n3]*...*h[nk] Computes the Schur expansion of e[n1]*e[n2]*e[n3]*...*e[nk]n via iterating the Pieri rule. Note: the coefficients are actually the Kostka numbers; the following is true: Map.toList (iteratedDualPieriRule (fromPartition mu)) == [ (dualPartition lam, kostkaNumber lam mu) | lam <- dominatingPartitions mu ]jThis should be faster than individually computing all these Kostka numbers. It is a tiny bit slower than .AIterating the Pieri rule, we can compute the Schur expansion of %e[lambda]*e[n1]*e[n2]*e[n3]*...*e[nk]None @A diagram is a set of boxes in a skew shape (in the right order) 'A filling is a pair consisting a shape nu and a lattice permutation lpNaive (very slow) reference implementation of the Littlewood-Richardson rule, based on the definition "count the semistandard skew tableaux whose row content is a lattice word"lrRule3 computes the expansion of a skew Schur function  s[lambda/mu]$ via the Littlewood-Richardson rule.-Adapted from John Stembridge's Maple code: >http://www.math.lsa.umich.edu/~jrs/software/SFexamples/LR_rule lrRule (mkSkewPartition (lambda,nu)) == Map.fromList list where muw = weight lambda - weight nu list = [ (mu, coeff) | mu <- partitions muw , let coeff = lrCoeff lambda (mu,nu) , coeff /= 0 ] _lrRule lambda mu4 computes the expansion of the skew Schur function  s[lambda/mu]$ via the Littlewood-Richardson rule.Note: we use reverse ordering in Diagrams compared the Stembridge's code. Also, for performance reasons, we need the length of the diagramlrCoeff lam (mu,nu)a computes the coressponding Littlewood-Richardson coefficients. This is also the coefficient of  s[lambda] in the product  s[mu]*s[nu]%Note: This is much slower than using  or 3 to compute several coefficients at the same time!lrCoeff (lam/nu) mua computes the coressponding Littlewood-Richardson coefficients. This is also the coefficient of s[mu] in the product  s[lam/nu]%Note: This is much slower than using  or 3 to compute several coefficients at the same time!!lrScalar (lambda/mu) (alpha/beta)> computes the scalar product of the two skew Schur functions  s[lambda/mu] and  s[alpha/beta]$ via the Littlewood-Richardson rule.+Adapted from John Stembridge Maple code: >http://www.math.lsa.umich.edu/~jrs/software/SFexamples/LR_ruleNote: we use reverse ordering in Diagrams compared the Stembridge's code. Also, for performance reasons, we need the length of the diagram;Computes the expansion of the product of Schur polynomials  s[mu]*s[nu]U using the Littlewood-Richardson rule. Note: this is symmetric in the two arguments.Based on the wikipedia article 8https://en.wikipedia.org/wiki/Littlewood-Richardson_rule lrMult mu nu == Map.fromList list where lamw = weight nu + weight mu list = [ (lambda, coeff) | lambda <- partitions lamw , let coeff = lrCoeff lambda (mu,nu) , coeff /= 0 ] dThis basically lists all the outer shapes (with multiplicities) which can be result from the LR ruleAdds a full row of (length pcols) boxes containing to a partition, with pcols being the upper bounds of the columns, respectively. We also return the newly added columnsReturns the (row,column) pairs of the new boxes which can be added to the given partition with the given column bounds and the 1-Rieri rule Adds a box to a partition'Safe head defaulting to zero ]Computes the sequence of differences from a partition (including the last difference to zero)    None9;DA binary tree with leaves and internal nodes decorated with types a and b, respectively..A binary tree with leaves decorated with type a.*The monadic join operation of binary treesBEnumerates the leaves a tree, starting from 0, ignoring old labelsWEnumerates the leaves a tree, starting from zero, and also returns the number of leaves0Enumerates the leaves a tree, starting from zero+Convert a binary tree to a rose tree (from  Data.Tree)8Generates all sequences of nested parentheses of length 2n in lexigraphic order. Synonym for . Synonym for . Synonym for .Generates all sequences of nested parentheses of length 2n. Order is lexicographical (when right parentheses are considered smaller then left ones). Based on "Algorithm P" in Knuth, but less efficient because of the "idiomatic" code.oGenerates a uniformly random sequence of nested parentheses of length 2n. Based on "Algorithm W" in Knuth.ONth sequence of nested parentheses of length 2n. The order is the same as in #. Based on "Algorithm U" in Knuth. Generates all binary trees with n- nodes. At the moment just a synonym for .9# = Catalan(n) = \frac { 1 } { n+1 } \binom { 2n } { n }.FThis 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. Nodes are decorated with odd numbers, leaves with even numbers (from the set [0..2n]"). Uses mutable arrays internally.3Draws a binary tree in ASCII, ignoring node labels.Example: FautoTabulate RowMajor (Right 5) $ map asciiBinaryTree_ $ binaryTrees 43n!N; should satisfy 1 <= N <= C(n) 4np/pn-None9;!]A lattice path is a path using only the allowed steps, never going below the zero level line y=0. nNote that if you rotate such a path by 45 degrees counterclockwise, you get a path which uses only the steps (1,0) and (0,1)Z, and stays above the main diagonal (hence the name, we just use a different convention).A step in a lattice path the step (1,1) the step (1,-1)5Draws the path into a list of lines. For example try: =autotabulate RowMajor (Right 5) (map asciiPath $ dyckPaths 4)=A lattice path is called "valid", if it never goes below the y=0 line.;A Dyck path is a lattice path whose last point lies on the y=0 line Maximal height of a lattice path.Endpoint of a lattice path, which starts from (0,0).BReturns the coordinates of the path (excluding the starting point (0,0), but including the endpoint)Counts the up-stepsCounts the down-steps'Counts both the up-steps and down-steps2Number of peaks of a path (excluding the endpoint)-Number of points on the path which touch the y=00 zero level line (excluding the starting point (0,0)S, but including the endpoint; that is, for Dyck paths it this is always positive!).BNumber of points on the path which touch the level line at height h (excluding the starting point (0,0), but including the endpoint). dyckPaths m lists all Dyck paths from (0,0) to (2m,0). hRemark: Dyck paths are obviously in bijection with nested parentheses, and thus also with binary trees.!Order is reverse lexicographical: +sort (dyckPaths m) == reverse (dyckPaths m) dyckPaths m lists all Dyck paths from (0,0) to (2m,0).  .sort (dyckPathsNaive m) == sort (dyckPaths m) *Naive recursive algorithm, order is ad-hocThe number of Dyck paths from (0,0) to (2m,0)# is simply the m'th Catalan number.The trivial bijection,The trivial bijection in the other directionboundedDyckPaths h m lists all Dyck paths from (0,0) to (2m,0) whose height is at most h. Synonym for .boundedDyckPathsNaive h m lists all Dyck paths from (0,0) to (2m,0) whose height is at most h. sort (boundedDyckPaths h m) == sort [ p | p <- dyckPaths m , pathHeight p <= h ] sort (boundedDyckPaths m m) == sort (dyckPaths m) <Naive recursive algorithm, resulting order is pretty ad-hoc. All lattice paths from (0,0) to (x,y). Clearly empty unless x-y is even. Synonym for   All lattice paths from (0,0) to (x,y). Clearly empty unless x-y is even. Note that 1sort (dyckPaths n) == sort (latticePaths (0,2*n))<Naive recursive algorithm, resulting order is pretty ad-hoc. ALattice paths are counted by the numbers in the Catalan triangle. touchingDyckPaths k m lists all Dyck paths from (0,0) to (2m,0)# which touch the zero level line y=0 exactly kI times (excluding the starting point, but including the endpoint; thus, k" should be positive). Synonym for  . touchingDyckPathsNaive k m lists all Dyck paths from (0,0) to (2m,0)# which touch the zero level line y=0 exactly kI times (excluding the starting point, but including the endpoint; thus, k should be positive). csort (touchingDyckPathsNaive k m) == sort [ p | p <- dyckPaths m , pathNumberOfZeroTouches p == k ]<Naive recursive algorithm, resulting order is pretty ad-hoc.DThere is a bijection from the set of non-empty Dyck paths of length 2n which touch the zero lines t times, to lattice paths from (0,0) to  (2n-t-1,t-1) (just remove all the down-steps just before touching the zero line, and also the very first up-step). This gives us a counting formula.peakingDyckPaths k m lists all Dyck paths from (0,0) to (2m,0) with exactly k peaks. Synonym for peakingDyckPathsNaive k m lists all Dyck paths from (0,0) to (2m,0) with exactly k peaks. [sort (peakingDyckPathsNaive k m) = sort [ p | p <- dyckPaths m , pathNumberOfPeaks p == k ]<Naive recursive algorithm, resulting order is pretty ad-hoc.Dyck paths of length 2m with k+ peaks are counted by the Narayana numbers &N(m,k) = binom{m}{k} binom{m}{k-1} / m'A uniformly random Dyck path of length 2m$h = the touch levelh = maximum heightm = half-lengthh = maximum heightm = half-length    k = number of zero-touchesm = half-length k = number of zero-touchesm = half-lengthk = number of zero-touchesm = half-lengthk = number of peaksm = half-lengthk = number of peaksm = half-lengthk = number of peaksm = half-length!     $     "     None29;b%#A completely unlabelled binary treeBA (strict) binary tree with labelled leaves (but unlabelled nodes)xA tree diagram, consisting of two binary trees with the same number of leaves, representing an element of the group F.<the width is the number of leaves, minus 1, of both diagrams "the top diagram correspond to the domain!&the bottom diagram corresponds to the range'%Creates a tree diagram from two trees(/Creates a tree diagram, but does not reduce it.,The generator x0-The generator x1.The generators x0, x1, x2 .../8The identity element in the group F 0A positive diagram< is a diagram whose bottom tree (the range) is a right vine.1Swaps the top and bottom of a tree diagram. This is the inverse in the group F. (Note: we don't do reduction here, as this operation keeps the reducedness)2^Decides whether two (possibly unreduced) tree diagrams represents the same group element in F.3LReduces a diagram. The result is a normal form of an element in the group F.4MList of carets at the bottom of the tree, indexed by their left edge position5dRemove the carets with the given indices (throws an error if there is no caret at the given index)6If diag1 corresponds to the PL function f, and diag2 to g, then compose diag1 diag2 will correspond to (g.f)D (note that the order is opposite than normal function composition!)*This is the multiplication in the group F.75Compose two tree diagrams without reducing the result8Given two binary trees, we return a pair of list of subtrees which, grafted the to leaves of the first (resp. the second) tree, results in the same extended tree.9-Returns the list of dyadic subdivision points:$Returns the list of dyadic intervals;*The monadic join operation of binary trees<A list version of ;A6The width of the tree is the number of leaves minus 1.B-Enumerates the leaves a tree, starting from 0CCEnumerates the leaves a tree, and also returns the number of leavesD "Right vine" of the given width E"Left vine" of the given width F Flips each node of a binary treeG and  are the same type, except that  is strict.rTODO: maybe unify these two types? Until that, you can convert between the two with these functions if necessary.I=Draws a binary tree, with all leaves at the same (bottom) rowJ.Draws a binary tree; when the boolean flag is True, we draw upside downKDraws a binary tree, with all leaves at the same (bottom) row, and labelling the leaves starting with 0 (continuing with letters after 9)L*When the flag is true, we draw upside downMDraws a tree diagram: !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR5 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLM: !RQ'()*+,-./0123456789:;<PON=>?@ABCDEFGH&%$#"IJKLM4 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRNone#ZA wordy, describing (non-uniquely) an element of a group. The identity element is represented (among others) by the empty word.[XA generator of a (free) group, indexed by which "copy" of the group we are dealing with.^The index of a generator_GThe sign of the (exponent of the) generator (that is, the generator is , the inverse is )a&keep the index, but return always the \ one.b'Generators are shown as small letters: a, b, c;, ... and their inverses are shown as capital letters, so A=a^-1, B=b^-1, etc.dThe inverse of a generatoreThe inverse of a wordf:Lists all words of the given length (total number will be (2g)^n'). The numbering of the generators is [1..g].gcLists all words of the given length which do not contain inverse generators (total number will be g^n'). The numbering of the generators is [1..g].h2A random group generator (or its inverse) between 1 and gi9A random group generator (but never its inverse) between 1 and gjA random word of length n using g generators (or their inverses)kA random word of length n using g$ generators (but not their inverses)lkMultiplication of the free group (returns the reduced result). It is true for any two words w1 and w2 that EmultiplyFree (reduceWordFree w1) (reduceWord w2) = multiplyFree w1 w2mLDecides whether two words represent the same group element in the free groupn6Reduces a word in a free group by repeatedly removing x*x^(-1) and x^(-1)*x pairs. The set of  reduced words^ forms the free group; the multiplication is obtained by concatenation followed by reduction.o=Naive (but canonical) reduction algorithm for the free groupsp%Counts the number of words of length n& which reduce to the identity element.Generating function is 9Gf_g(u) = \frac {2g-1} { g-1 + g \sqrt{ 1 - (8g-4)u^2 } }q%Counts the number of words of length n whose reduced form has length k (clearly n and k3 must have the same parity for this to be nonzero): ^countWordReductionsFree g n k == sum [ 1 | w <- allWords g n, k == length (reduceWordFree w) ]r'Multiplication in free products of Z2'ss'Multiplication in free products of Z3'st'Multiplication in free products of Zm'suQDecides whether two words represent the same group element in free products of Z2vQDecides whether two words represent the same group element in free products of Z3wQDecides whether two words represent the same group element in free products of Zmx%Reduces a word, where each generator x# satisfies the additional relation x^2=1" (that is, free products of Z2's)y%Reduces a word, where each generator x# satisfies the additional relation x^3=1" (that is, free products of Z3's)z%Reduces a word, where each generator x# satisfies the additional relation x^m=1" (that is, free products of Zm's){%Reduces a word, where each generator x# satisfies the additional relation x^2=1D (that is, free products of Z2's). Naive (but canonical) algorithm.|%Reduces a word, where each generator x# satisfies the additional relation x^3=1D (that is, free products of Z3's). Naive (but canonical) algorithm.}%Reduces a word, where each generator x# satisfies the additional relation x^m=1D (that is, free products of Zm's). Naive (but canonical) algorithm.~BCounts the number of words (without inverse generators) of length n= which reduce to the identity element, using the relations x^2=1.Generating function is 9Gf_g(u) = \frac {2g-2} { g-2 + g \sqrt{ 1 - (4g-4)u^2 } }The first few g cases: A000984 = [ countIdentityWordsZ2 2 (2*n) | n<-[0..] ] = [1,2,6,20,70,252,924,3432,12870,48620,184756...] A089022 = [ countIdentityWordsZ2 3 (2*n) | n<-[0..] ] = [1,3,15,87,543,3543,23823,163719,1143999,8099511,57959535...] A035610 = [ countIdentityWordsZ2 4 (2*n) | n<-[0..] ] = [1,4,28,232,2092,19864,195352,1970896,20275660,211823800,2240795848...] A130976 = [ countIdentityWordsZ2 5 (2*n) | n<-[0..] ] = [1,5,45,485,5725,71445,925965,12335685,167817405,2321105525,32536755565...]BCounts the number of words (without inverse generators) of length nJ whose reduced form in the product of Z2-s (that is, for each generator x we have x^2=1) has length k (clearly n and k3 must have the same parity for this to be nonzero): _countWordReductionsZ2 g n k == sum [ 1 | w <- allWordsNoInv g n, k == length (reduceWordZ2 w) ]BCounts the number of words (without inverse generators) of length n= which reduce to the identity element, using the relations x^3=1. acountIdentityWordsZ3NoInv g n == sum [ 1 | w <- allWordsNoInv g n, 0 == length (reduceWordZ2 w) ] In mathematica, the formula is: BSum[ g^k * (g-1)^(n-k) * k/n * Binomial[3*n-k-1, n-k] , {k, 1,n} ](Z[\]^_`abcdefg = number of generators n = length of the wordgg = number of generators n = length of the wordhg = number of generators ig = number of generators jg = number of generators n = length of the wordkg = number of generators n = length of the wordlmnop*g = number of generators in the free group n = length of the unreduced wordq*g = number of generators in the free group n = length of the unreduced wordk = length of the reduced wordrstuvwxyz{|}~*g = number of generators in the free group n = length of the unreduced word*g = number of generators in the free group n = length of the unreduced wordk = length of the reduced word*g = number of generators in the free group n = length of the unreduced word'Z[\]^_`abcdefghijklmnopqrstuvwxyz{|}~([\]^_`aZbcdefghijklmnopqrstuvwxyz{|}~&Z[\]^_`abcdefghijklmnopqrstuvwxyz{|}~NoneA partition of the set [1..n] (in standard order)yThe "shape" of a set partition is the partition we get when we forget the set structure, keeping only the cardinalities. Synonym for  Synonym for  ^sort (setPartitionsWithKParts k n) == sort [ p | p <- setPartitions n , numberOfParts p == k ]List all set partitions of [1..n], naive algorithmSet partitions of the set [1..n] into k parts.Set partitions are counted by the Bell numbersSet partitions of size k3 are counted by the Stirling numbers of second kindk = number of partsn = size of the setk = number of partsn = size of the setk = number of partsn = size of the set None$A non-crossing partition of the set [1..n]t in standard form: entries decreasing in each block and blocks listed in increasing order of their first entries..Checks whether a set partition is noncrossing.Implementation method: we convert to a Dyck path and then back again, and finally compare. Probably not very efficient, but should be better than a naive check for crosses...)5Warning: This function assumes the standard ordering!zConvert to standard form: entries decreasing in each block and blocks listed in increasing order of their first entries.<Throws an error if the input is not a non-crossing partitionCIf a set partition is actually non-crossing, then we can convert it7Bijection between Dyck paths and noncrossing partitionsBased on: David Callan: &Sets, Lists and Noncrossing Partitions&Fails if the input is not a Dyck path.Safe version of 0The inverse bijection (should never fail proper -s) Safe version %Lists all non-crossing partitions of [1..n]XEquivalent to (but orders of magnitude faster than) filtering out the non-crossing ones: f(sort $ catMaybes $ map setPartitionToNonCrossing $ setPartitions n) == sort (nonCrossingPartitions n)%Lists all non-crossing partitions of [1..n] into k parts. nsort (nonCrossingPartitionsWithKParts k n) == sort [ p | p <- nonCrossingPartitions n , numberOfParts p == k ]:Non-crossing partitions are counted by the Catalan numbersNon-crossing partitions with k* parts are counted by the Naranaya numbers'Uniformly random non-crossing partitionk = number of parts n = size of the setk = number of parts n = size of the setNone9; 8Adds unique labels to the nodes (including leaves) of a  8Adds unique labels to the nodes (including leaves) of a .regularNaryTrees d n' returns the list of (rooted) trees on n$ nodes where each node has exactly d0 children. Note that the leaves do not count in n. Naive algorithm.Ternary trees on n nodes (synonym for regularNaryTrees 3)We have clength (regularNaryTrees d n) == countRegularNaryTrees d n == \frac {1} {(d-1)n+1} \binom {dn} {n}  %# = \frac {1} {(2n+1} \binom {3n} {n} All trees on nZ nodes where the number of children of all nodes is in element of the given set. Example: autoTabulate RowMajor (Right 5) $ map asciiTreeVertical $ map labelNChildrenTree_ $ semiRegularTrees [2,3] 2 [ length $ semiRegularTrees [2,3] n | n<-[0..] ] == [1,2,10,66,498,4066,34970,312066,2862562,26824386,...](The latter sequence is A027307 in OEIS: https://oeis.org/A027307Remark: clearly, we have .semiRegularTrees [d] n == regularNaryTrees d n:Vertical ASCII drawing of a tree, without labels. Example: PautoTabulate RowMajor (Right 5) $ map asciiTreeVertical_ $ regularNaryTrees 2 4 Nodes are denoted by @ , leaves by *.Prints all labels. Example: HasciiTreeVertical $ addUniqueLabelsTree_ $ (regularNaryTrees 3 9) !! 666Nodes are denoted by (label) , leaves by label.9Prints the labels for the leaves, but not for the nodes.DThe leftmost spine (the second element of the pair is the leaf node)(The leftmost spine without the leaf node/The length (number of edges) on the left spine 0leftSpineLength tree == length (leftSpine_ tree) is leaf,  is node=Attaches the depth to each node. The depth of the root is 0. .Attaches the number of children to each node. fComputes the set of equivalence classes of rooted trees (in the sense that the leaves of a node are  unordered ) with  n = length ks| leaves where the set of heights of the leaves matches the given set of numbers. The height is defined as the number of edges from the leaf to the root. TODO: better name?) (degree = number of children of each nodenumber of nodes!set of allowed number of childrennumber of nodes7 !"#$% , ) $Nonec !"#$% np%None !"#$% lnp      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXfghijklmnopqrstuvwxyz{|}~     &&'(&')&')*+,*+-*+.*+/0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTTUVWXYZ[\]^_`abbcdefghijklmnopqrstuvwxyz{|}~                                                                    ! "#$%&'()*+,-./0123456789:;<<==>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABBCCDEFGHIJKLMNOPQRSTUVWXYZ[\fe)]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-.//=>00123456789:;<=>?@fAeBCDE)^FGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                        \[&&     & !"#$*+%&*+'*+(*+)*+**++*+,*+-*+.*+/*+01'combinat-0.2.8.2-4VRnhRe8Ox27nh4FhdmIGgMath.Combinat.TypeLevelMath.Combinat.Trees.NaryMath.Combinat.Partitions.Vector!Math.Combinat.Partitions.MultisetMath.Combinat.Trees.BinaryMath.Combinat.Trees.GraphvizMath.Combinat.Numbers.PrimesMath.Combinat.HelperMath.Combinat.ClassesMath.Combinat.ASCIIMath.Combinat.TuplesMath.Combinat.SignMath.Combinat.NumbersMath.Combinat.SetsMath.Combinat.CompositionsMath.Combinat.Permutations Math.Combinat.Partitions.IntegerMath.Combinat.Tableaux*Math.Combinat.Tableaux.GelfandTsetlin.ConeMath.Combinat.Partitions.PlaneMath.Combinat.Numbers.SeriesMath.Combinat.Groups.BraidMath.Combinat.Groups.Braid.NFMath.Combinat.Partitions.SkewMath.Combinat.Tableaux.Skew%Math.Combinat.Tableaux.GelfandTsetlin+Math.Combinat.Tableaux.LittlewoodRichardsonMath.Combinat.LatticePathsMath.Combinat.Groups.Thompson.FMath.Combinat.Groups.FreeMath.Combinat.Partitions.Set$Math.Combinat.Partitions.NonCrossingSystemRandomMath.Combinat.PartitionsMath.Combinat.Trees Math.Combinatbase Data.Proxy asProxyTypeOfProxycontainers-0.5.7.1 Data.Tree subForest rootLabelNodeTreeaddUniqueLabelsForest_addUniqueLabelsTree_addUniqueLabelsForestaddUniqueLabelsTree IntVectorvectorPartitions_vectorPartitionsfasc3B_algorithm_MpartitionMultisetBinTree'Branch'Leaf'BinTreeBranchLeafDotgraphvizDotBinTreegraphvizDotBinTree'graphvizDotForestgraphvizDotTreeprimes primesSimple primesTMWEgroupIntegerFactorsintegerFactorsTrialDivision integerLog2 ceilingLog2isSquareintegerSquareRootceilingSquareRootintegerSquareRoot'integerSquareRootNewton'powerModmillerRabinPrimalityTestisProbablyPrimeisVeryProbablyPrimeSome proxyUndefproxyOfproxyOf1proxyOf2asProxyTypeOf1typeArgiTypeArgwithSome withSomeM selectSome selectSomeM withSelected withSelectedMRandTRanddebugswappairs pairsWithsum'equatingreverseOrderingreverseCompare reverseSort groupSortBynubOrdisWeaklyIncreasingisStrictlyIncreasingisWeaklyDecreasingisStrictlyDecreasing mapWithLast mapWithFirstmapWithFirstLastmkLinesUniformWidthmkBlocksUniformHeightmkUniformBlocks hConcatLines vConcatLinescount histogramfromJust intToBool boolToIntnestunfold1unfold unfoldEitherunfoldM mapAccumM longZipWithrunRand flipRunRandrunRandT flipRunRandTrandrandRoll randChoose randProxy1$fFunctorRandT$fApplicativeRandT $fMonadRandTHasNumberOfCyclesnumberOfCyclesHasNumberOfLeavesnumberOfLeavesHasNumberOfNodes numberOfNodesHasShapeshape HasDualitydual HasWeightweight HasHeightheightHasWidthwidthHasNumberOfParts numberOfParts CanBeEmptyisEmptyempty MatrixOrderRowMajorColMajorVSep VSepEmpty VSepSpaces VSepStringHSep HSepEmpty HSepSpaces HSepString AlignmentAlignVAlignVTopVCenterVBottomHAlignHLeftHCenterHRight DrawASCIIasciiASCII asciiSize asciiLines emptyRect asciiXSize asciiYSize asciiString printASCIIasciiFromLinesasciiFromStringhSepSize hSepStringvSepSize vSepString|||===hCatTophCatBotvCatLeft vCatRighthCatWithvCatWithhPadvPadpad hExtendTo vExtendTo hExtendWith vExtendWithhIndentvIndenthCutvCut pasteOnto pasteOnto' pasteOntoRel pasteOntoRel'tabulate autoTabulatecaptioncaption'asciiBoxroundedAsciiBox filledBoxtransparentBox asciiNumber asciiShow $fShowASCII $fEqHAlign $fShowHAlign $fEqVAlign $fShowVAlign $fShowHSep $fShowVSep$fEqMatrixOrder$fOrdMatrixOrder$fShowMatrixOrder$fReadMatrixOrdertuples'tuples1' countTuples' countTuples1'tuplestuples1 countTuples countTuples1 binaryTuplesSignPlusMinusisPlusisMinus signValuesigned paritySignparitySignValue negateIfOdd oppositeSignmulSignproductOfSigns $fRandomSign $fMonoidSign$fEqSign $fOrdSign $fShowSign $fReadSign factorialdoubleFactorialbinomialsignedBinomial pascalRow multinomialcatalancatalanTrianglesignedStirling1stArraysignedStirling1stunsignedStirling1st stirling2nd bernoullibellNumbersArray bellNumberchoose_choosechoose'choose'' chooseTaggedcombinecomposetuplesFromList listTensor kSublistscountKSublistssublists countSublists randomChoice Composition compositions'countCompositions'allCompositions1allCompositions' compositionscountCompositions compositions1countCompositions1randomCompositionrandomComposition1DisjointCycles PermutationfromPermutationpermutationUArraypermutationArraytoPermutationUnsafeuarrayToPermutationUnsafe isPermutationmaybePermutation toPermutationpermutationSizeisIdentityPermutationasciiPermutationasciiDisjointCyclestwoLineNotationinverseTwoLineNotationgenericTwoLineNotationfromDisjointCyclesdisjointCyclesUnsafedisjointCyclesToPermutationpermutationToDisjointCyclesisEvenPermutationisOddPermutationsignOfPermutationsignValueOfPermutationisCyclicPermutation inversionsnumberOfInversionsnumberOfInversionsMergenumberOfInversionsNaive bubbleSort2 bubbleSortreversePermutationisReversePermutation transpositiontranspositionsadjacentTranspositionadjacentTranspositions cycleLeft cycleRightmultiplyinverseidentity multiplyMany multiplyMany'permute permuteList permuteRightpermuteRightList permuteLeftpermuteLeftList permutations _permutationspermutationsNaive_permutationsNaivecountPermutationsrandomPermutation_randomPermutationrandomCyclicPermutation_randomCyclicPermutationrandomPermutationDurstenfeldrandomCyclicPermutationSattolopermuteMultisetcountPermuteMultisetfasc2B_algorithm_L$fHasNumberOfCyclesPermutation!$fHasNumberOfCyclesDisjointCycles$fDrawASCIIDisjointCycles$fHasWidthPermutation$fDrawASCIIPermutation$fReadPermutation$fShowPermutation$fEqPermutation$fOrdPermutation$fEqDisjointCycles$fOrdDisjointCycles$fShowDisjointCycles$fReadDisjointCyclesPartitionConventionEnglishNotationEnglishNotationCCWFrenchNotationPair Partition mkPartitiontoPartitionUnsafe toPartition isPartitionisEmptyPartitionemptyPartition fromPartitionpartitionHeightpartitionWidth heightWidthpartitionWeight dualPartition_dualPartition_dualPartitionNaive diffSequenceelements _elementstoExponentialForm_toExponentialFormfromExponentialFromcountAutomorphisms_countAutomorphisms partitions _partitionscountPartitionscountPartitionsNaivepartitionCountListpartitionCountListNaive allPartitionsallPartitionsGroupedallPartitions'allPartitionsGrouped'countAllPartitions'countAllPartitions _partitions' partitions'countPartitions'randomPartitionrandomPartitions dominatesdominatedPartitions_dominatedPartitionsdominatingPartitions_dominatingPartitionspartitionsWithKPartscountPartitionsWithKPartspartitionsWithOddPartspartitionsWithDistinctPartsisSubPartitionOfisSuperPartitionOf subPartitions_subPartitionsallSubPartitions_allSubPartitionssuperPartitions_superPartitions pieriRule dualPieriRuleasciiFerrersDiagramasciiFerrersDiagram'$fDrawASCIIPartition$fHasDualityPartition$fHasWeightPartition$fHasWidthPartition$fHasHeightPartition$fCanBeEmptyPartition$fHasNumberOfPartsPartition $fEqPartition$fOrdPartition$fShowPartition$fReadPartition$fEqPartitionConvention$fShowPartitionConventionTableau asciiTableau _tableauShape tableauShape tableauWeight dualTableautableauContenthooks hookLengthsrowWordrowWordToTableau columnWordcolumnWordToTableau isLatticeWordisSemiStandardTableausemiStandardYoungTableauxcountSemiStandardYoungTableauxisStandardTableaustandardYoungTableauxcountStandardYoungTableaux$fHasDuality[] $fHasWeight[]$fHasShape[]Partition $fDrawASCII[]$fCanBeEmpty[]TriunTriTriangularArraytriangularArrayUnsafefromTriangularArrayasciiTriangularArraygtSimplexContent_gtSimplexContentgtSimplexTableaux_gtSimplexTableauxcountGTSimplexTableauxinvertGTSimplexTableau_invertGTSimplexTableau$fDrawASCIIArray$fIxTri$fEqTri$fOrdTri $fShowTri$fEqHole $fOrdHole $fShowHole PlanePart fromPlanePartisValidPlanePart toPlanePartplanePartShapeplanePartZHeightplanePartWeight singleLayer stackLayersunsafeStackLayersplanePartLayersplanePartitions$fHasWeightPlanePart$fCanBeEmptyPlanePart $fEqPlanePart$fOrdPlanePart$fShowPlanePart unitSeries zeroSeries constSeriesidSeries powerTerm addSeries sumSeries subSeries negateSeries scaleSeries mulSeriesproductOfSeriesconvolve convolveManyreciprocalSeriesintegralReciprocalSeries composeSeries substitute lagrangeCoeffintegralLagrangeInversionlagrangeInversion expSeries cosSeries sinSeries coshSeries sinhSeries log1Series dyckSeries coinSeries coinSeries'convolveWithCoinSeriesconvolveWithCoinSeries'productPSeriesproductPSeries'convolveWithProductPSeriesconvolveWithProductPSeries'pseriesconvolveWithPSeriespseries'convolveWithPSeries' signedPSeriesconvolveWithSignedPSeries SomeBraidBraidBrGenSigmaSigmaInvbrGenIdx brGenSign brGenSignIdxinvBrGennumberOfStrands someBraid withSomeBraidmkBraid withBraid braidWordbraidWordLengthextendfreeReduceBraidWordsigmasigmaInv doubleSigma positiveWord halfTwist _halfTwisttheGarsideBraidtautauPerm composeManycomposeDontReduce isPureBraidbraidPermutation_braidPermutationisPositiveBraidWordisPermutationBraid_isPermutationBraidpermutationBraid_permutationBraid_permutationBraid' linkingMatrix_linkingMatrix strandLinking bronfmanHbronfmanHsListexpandBronfmanHhorizBraidASCIIhorizBraidASCII'allPositiveBraidWords allBraidWords_allPositiveBraidWords_allBraidWordsrandomBraidWordrandomPositiveBraidWordrandomPerturbBraidWordwithRandomBraidWordwithRandomPositiveBraidWord_randomBraidWord_randomPositiveBraidWord$fDrawASCIIBraid $fEqBrGen $fOrdBrGen $fShowBrGen $fShowBraidBraidNF _nfDeltaExp_nfPerms nfReprWordbraidNormalFormbraidNormalForm'braidNormalFormNaive'permWordStartingSetpermWordFinishingSetpermutationStartingSetpermutationFinishingSet $fEqBraidNF $fOrdBraidNF $fShowBraidNF$fEqXGen $fShowXGen SkewPartitionmkSkewPartitionsafeSkewPartitionskewPartitionWeightnormalizeSkewPartitionfromSkewPartitionouterPartitioninnerPartitiondualSkewPartitionskewPartitionsWithOuterShapeallSkewPartitionsWithOuterShapeskewPartitionsWithInnerShapeasciiSkewFerrersDiagramasciiSkewFerrersDiagram'$fDrawASCIISkewPartition$fHasDualitySkewPartition$fHasWeightSkewPartition$fEqSkewPartition$fOrdSkewPartition$fShowSkewPartition SkewTableauskewTableauShapeskewTableauWeightdualSkewTableauisSemiStandardSkewTableauisStandardSkewTableausemiStandardSkewTableauxasciiSkewTableauasciiSkewTableau'skewTableauRowWordskewTableauColumnWordfillSkewPartitionWithRowWordfillSkewPartitionWithColumnWordskewTableauRowContent$fDrawASCIISkewTableau$fHasDualitySkewTableau$fHasWeightSkewTableau"$fHasShapeSkewTableauSkewPartition$fFunctorSkewTableau$fEqSkewTableau$fOrdSkewTableau$fShowSkewTableauGT kostkaNumberkostkaNumberReferenceNaivekostkaNumbersWithGivenLambdakostkaNumbersWithGivenMuasciiGTkostkaGelfandTsetlinPatternskostkaGelfandTsetlinPatterns'!countKostkaGelfandTsetlinPatternsiteratedPieriRuleiteratedPieriRule'iteratedPieriRule''iteratedDualPieriRuleiteratedDualPieriRule'iteratedDualPieriRule'' lrRuleNaivelrRule_lrRulelrCoefflrCoeff'lrScalar _lrScalarlrMultParen LeftParen RightParenleafgraftforgetNodeDecorationsenumerateLeaves_enumerateLeaves'enumerateLeaves toRoseTree toRoseTree'parenthesesToStringstringToParenthesesforestToNestedParenthesesforestToBinaryTreenestedParenthesesToForestnestedParenthesesToForestUnsafenestedParenthesesToBinaryTree#nestedParenthesesToBinaryTreeUnsafebinaryTreeToNestedParenthesesbinaryTreeToForestnestedParenthesesrandomNestedParenthesesnthNestedParenthesescountNestedParenthesesfasc4A_algorithm_Pfasc4A_algorithm_Wfasc4A_algorithm_U binaryTreescountBinaryTreesbinaryTreesNaiverandomBinaryTreefasc4A_algorithm_RasciiBinaryTree_$fDrawASCIIBinTree$fMonadBinTree$fApplicativeBinTree$fTraversableBinTree$fFoldableBinTree$fFunctorBinTree$fHasNumberOfLeavesBinTree'$fHasNumberOfNodesBinTree'$fHasNumberOfLeavesBinTree$fHasNumberOfNodesBinTree $fEqBinTree $fOrdBinTree $fShowBinTree $fReadBinTree $fEqBinTree' $fOrdBinTree'$fShowBinTree'$fReadBinTree' $fEqParen $fOrdParen $fShowParen $fReadParen LatticePathStepUpStepDownStep asciiPath isValidPath isDyckPath pathHeight pathEndpointpathCoordinatespathNumberOfUpStepspathNumberOfDownStepspathNumberOfUpDownStepspathNumberOfPeakspathNumberOfZeroTouchespathNumberOfTouches' dyckPathsdyckPathsNaivecountDyckPathsnestedParensToDyckPathdyckPathToNestedParensboundedDyckPathsboundedDyckPathsNaive latticePathslatticePathsNaivecountLatticePathstouchingDyckPathstouchingDyckPathsNaivecountTouchingDyckPathspeakingDyckPathspeakingDyckPathsNaivecountPeakingDyckPathsrandomDyckPath $fHasWidth[] $fHasHeight[]$fEqStep $fOrdStep $fShowStepTTDiag_width_domain_rangeX1X0CtBrLfmkTDiagmkTDiagDontReduce isValidTDiag isPositive isReducedx0x1xkpositive equivalentreduce treeCaretList removeCaretsextensionToCommonTree subdivision1 subdivision2 listGraftbranchcarettreeNumberOfLeaves treeWidth enumerate_ enumerate rightVineleftVineflipTree toBinTree fromBinTreeasciiTasciiT' asciiTLabels asciiTLabels' asciiTDiag$fHasWidthTree$fHasNumberOfLeavesTree$fDrawASCIITree$fHasWidthTDiag$fDrawASCIITDiag$fEqTree $fOrdTree $fShowTree $fFunctorTree $fEqTDiag $fOrdTDiag $fShowTDiagWord GeneratorGenInvgenIdxgenSign genSignValueabsGenshowGenshowWord inverseGen inverseWordallWords allWordsNoInvrandomGeneratorrandomGeneratorNoInv randomWordrandomWordNoInv multiplyFreeequivalentFreereduceWordFreereduceWordFreeNaivecountIdentityWordsFreecountWordReductionsFree multiplyZ2 multiplyZ3 multiplyZm equivalentZ2 equivalentZ3 equivalentZm reduceWordZ2 reduceWordZ3 reduceWordZmreduceWordZ2NaivereduceWordZ3NaivereduceWordZmNaivecountIdentityWordsZ2countWordReductionsZ2countIdentityWordsZ3NoInv$fFunctorGenerator $fEqGenerator$fOrdGenerator$fShowGenerator$fReadGenerator SetPartition_standardizeSetPartitionfromSetPartitiontoSetPartitionUnsafetoSetPartition_isSetPartitionsetPartitionShape setPartitionssetPartitionsWithKPartssetPartitionsNaivesetPartitionsWithKPartsNaivecountSetPartitionscountSetPartitionsWithKParts$fHasNumberOfPartsSetPartition$fEqSetPartition$fOrdSetPartition$fShowSetPartition$fReadSetPartition NonCrossing_isNonCrossing_isNonCrossingUnsafe_standardizeNonCrossingfromNonCrossingtoNonCrossingUnsafe toNonCrossingtoNonCrossingMaybesetPartitionToNonCrossingdyckPathToNonCrossingPartition#dyckPathToNonCrossingPartitionMaybenonCrossingPartitionToDyckPath$_nonCrossingPartitionToDyckPathMaybenonCrossingPartitionsnonCrossingPartitionsWithKPartscountNonCrossingPartitions$countNonCrossingPartitionsWithKPartsrandomNonCrossingPartition$fHasNumberOfPartsNonCrossing$fEqNonCrossing$fOrdNonCrossing$fShowNonCrossing$fReadNonCrossingregularNaryTrees ternaryTreescountRegularNaryTreescountTernaryTreessemiRegularTreesasciiTreeVertical_asciiTreeVerticalasciiTreeVerticalLeavesOnly leftSpine rightSpine leftSpine_ rightSpine_leftSpineLengthrightSpineLengthclassifyTreeNode isTreeLeaf isTreeNode isTreeLeaf_ isTreeNode_treeNodeNumberOfChildrencountTreeNodescountTreeLeavescountTreeLabelsWithcountTreeNodesWithlabelDepthTreelabelDepthForestlabelDepthTree_labelDepthForest_labelNChildrenTreelabelNChildrenForestlabelNChildrenTree_labelNChildrenForest_ derivTrees$fHasNumberOfNodesTreedigraphBracket binTreeDot' binTree'Dot'integerRndSequencefind2kmpow'mulMod squareModpowMod Data.EitherRightLeftmakeChoiceFromIndicesKnuthmakeChoiceFromIndicesNaive#randomPermutationDurstenfeldSattoloReverseHoleTableauReverseTableauHolebinom2index'deIndex'toHolenextHolereverseTableau normalize normalize' startHole enumHoleshelper newLines'newLinessizes'ghc-prim GHC.TypesTrueFalseXGenXDeltaXSigmaXLXTauLreplaceInversesreplaceInversesNaivemoveDeltasLeftexpandPosXWordexpandAnyXWordposLposRposLPermposRPermfilterDeltaFactorsfails_lemmma_2_5normalizePermFactorsnormalizePermFactors1leftGreedyFactorsisXDeltaGHC.BaseNothingDiagramFillingfillings fillings'addMuaddRowOfnewBoxesaddBox headOrZerodiffSeqPart nextLetter nextLetter' parenToCharForest derivTrees'unfoldForestM_BFunfoldTreeM_BF unfoldForestM unfoldTreeM unfoldForest unfoldTreelevelsflatten drawForestdrawTree