Computing growth functions of braid monoids and counting vertex-labelled bipartite graphs

We derive a recurrence relation for the number of simple vertex-labelled bipartite graphs with given degrees of the vertices and use this result to obtain a new method for computing the growth function of the Artin monoid of type An−1 with respect to the simple elements (permutation braids) as generators. Instead of matrices of size 2n−1×2n−1, we use matrices of size p(n)×p(n), where p(n) is the number of partitions of n.