0,2

The process of expressing a word in generators as a sorted word in generators and commutators is Marshall Hall's 'collection process'.

Since this monoid 'lives in' a nilpotent group, it inherits the growth restriction of a nilpotent group. So, according to a result of Bass,

a(n) = O( n^8)

It seems this is the correct growth rate. This sequence may well have a rational generating function, though, according to a result of M Stoll, the growth function of a nilpotent group need not be rational, or even algebraic.

Computations on a free nilpotent group, or on submonoids, may be aided by using matricies. I. D. MacDonald describes how to do this in an American Mathematical Monthly article, and he gives a recipie explicitly for the nil-2, 3 generator case.

H. Bass, `The degree of polynomial growth of finitely generated nilpotent groups', Proc. London Math. Soc. 25 (1972)

Michael Stoll,Rational and transcendental growth series for the higher Heisenberg groups Inventiones Mathematicae Volume 126, Number 1 / September, 1996

I. D. MacDonald, 'Commutators and Their Products', The American Mathematical Monthly, Vol. 93, No. 6, (Jun. - Jul., 1986), pp. 440-444

Suppose the generators are a,b,c, and their commutators are q,r,s, so

ba = abq, ca = acr, cb = bcs, nil-2 means that q,r,s commute with everything.

Now there are 81 different words of length 4 on a,b,c, but there are three equations:

abba = baab ( = aabbqq)

acca = caac ( = aaccrr)

bccb = cbbc ( = bbccss)

and these are the only equations, so instead of 81 distinct words we have 78 distinct words, a(4)=78.

Cf. sequence A000125 gives the analogous count for the 2 generator case. sequence A077028 refines A000125 by counting the number of words with k a's and (n-k)b's.

Sequence in context: A084707 A048481 A027027 this_sequence A139561 A006810 A090401

Adjacent sequences: A140345 A140346 A140347 this_sequence A140349 A140350 A140351

nonn

David and Moshe Newman (mshnoiman(AT)hotmail.com), May 29 2008