Combinatorics

module CombinatoricsGeneration

CombinatoricsGeneration.hs
Functions to generate simple combinatorial sets.
Exports
cartProd sets - returns the cartesian product of the sets
powerset xs - returns the power set of xs
combinationsOf k xs - returns the k-element subsets of xs
combinations k n - combinations of k numbers from [1..n]
permutationsOf xs - returns all permutations of xs
permutations n - permutations of [1..n]
partitions n
Examples 

> cartProd [[0,4],[0,2],[0,1]]
[[0,0,0],[0,0,1],[0,2,0],[0,2,1],[4,0,0],[4,0,1],[4,2,0],[4,2,1]]
> powerset [4,2,1]
[[],[1],[2],[2,1],[4],[4,1],[4,2],[4,2,1]]
> combinations 3 5
[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]
> permutations 3
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
> partitions 5
[[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]

module CombinatoricsCounting

CombinatoricsCounting.hs

Functions to count the number of elements in simple combinatorial sets, such as those provided by the module above.
Exports
factorial n
choose n k - the number of k-subsets of an n-set
fallingFactorial x n = x(x-1)..(x-n+1)
risingFactorial x n = x(x+1)..(x+n-1)
pascalTriangle n - Pascal's triangle
stirlingFirstTriangle n - triangle of Stirling numbers of the first kind, that is the numbers s(n,k) such that (-1)n-ks(n,k) is the number of permutations of [1..n] with k cycles.
pascalTriangle n - triangle of Stirling numbers of the second kind, that is the numbers S(n,k) such that S(n,k) is the number of partitions of [1..n] with k (non-empty) parts
bellNumbers - the Bell numbers. Bn is the total number of partitions of [1..n]
catalanNumbers - the Catalan numbers
(Note, partitions of a set are not the same things as partitions of a number. For example, the partitions of 3 are [3], [2,1], [1,1,1], whereas the partitions of {1,2,3} are {{1,2,3}}, {{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}}, {{1},{2},{3}}.)

Examples 

> take 6 pascalTriangle
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]
> take 6 stirlingFirstTriangle
[[1],[0,1],[0,-1,1],[0,2,-3,1],[0,-6,11,-6,1],[0,24,-50,35,-10,1]]
> take 6 stirlingSecondTriangle
[[1],[0,1],[0,1,1],[0,1,3,1],[0,1,7,6,1],[0,1,15,25,10,1]]
> take 10 bellNumbers
[1,1,2,5,15,52,203,877,4140,21147]
> take 10 catalanNumbers
[0,1,1,2,5,14,42,132,429,1430]

module Graph

Graph.hs
Functions to generate graphs in various families, and compute simple invariants.
Exports
type Graph = (Int,[[Int]]) - the number of vertices and the list of edges
c n - the cyclic graph Cn on n vertices
k n - the complete graph Kn on n vertices
kb m n - the complete bipartite graph Km,n
j v k i - the generalised Johnson graph on v vertices, sets of size k with incidence i
kneser v k - the Kneser graph Kv:k
johnson v k - the Johnson graphs
petersenGraph - the Petersen graph
q k - the k-cube Qk
lineGraph graph - the line graph L(G) of G
complement graph - the complement of G
adjacencyMatrix graph - the adjacency matrix of a graph, in which the ij entry is 1 if i and j are adjacent, 0 otherwise
incidenceMatrix graph - the incidence matrix of a graph, in which there is a row for each vertex and column for each edge, with the ijth entry 1 if vertex i is in edge j, 0 otherwise
valencyVector graph - the "valency vector" of a graph, showing how many vertices of each valency it has
Examples 

> c 5
(5,[[1,2],[1,5],[2,3],[3,4],[4,5]])
> k 4
(4,[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]])
> mapM_ print $ adjacencyMatrix (5,[[1,2],[1,3],[1,5]])
[0,1,1,0,1]
[1,0,0,0,0]
[1,0,0,0,0]
[0,0,0,0,0]
[1,0,0,0,0]
> mapM_ print $ incidenceMatrix (5,[[1,2],[1,3],[1,5]])
[1,1,1]
[1,0,0]
[0,1,0]
[0,0,0]
[0,0,1]
> valencyVector (5,[[1,2],[1,3],[1,5]])
[1,3,0,1]