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 A n − 1 with respect to the simple elements (permutation braids) as generators. Instead of matrices of size 2 n − 1 × 2 n − 1 , we use matrices of size p ( n ) × p ( n ) , where p ( n ) is the number of partitions of n.