A079494 Number of words of weight n in the free central groupoid on one generator.

1, 1, 2, 2, 6, 8, 26, 55, 148, 377, 1066, 2853, 8044, 22298, 63134, 178399, 509944, 1460728, 4213962, 12194213

Offset

0,3

Comments

The cited paper does not include the numerical sequence, but these numbers will be included in an addendum when the paper is reprinted this spring in my "Selected Papers on Discrete Mathematics".

Computed by a simple 20-line C program, which runs fast but needs exponential memory. The basic idea is: Include a new word m=j.k for all subwords j and k whose total weight is n-1, unless one of the following three conditions is true: (a) j>0 && k>0 && r[j]==l[k]; (b) k>0 && l[k]>0 && l[l[k]]==j; (c) j>0 && r[j]>0 && r[r[j]]==k; so that the first few words of positive weight are 1=0.0, 2=0.1, 3=1.0, 4=0.2, 5=3.0, 6=0.4, 7=0.5, 8=1.3, 9=2.1, 10=4.0, 11=5.0; words 6 through 11 are the ones of weight 3 listed in the example.

References

D. E. Knuth, "Notes on central groupoids," Journal of Combinatorial Theory 8 (1970), 376-390. [Especially page 389.]

Links

Table of n, a(n) for n=0..19.

Example

a(4)=6 because the following six elements have four multiplications: a.(a.(a.(a.a))), a.(((a.a).a).a), (a.a).((a.a).a), (a.(a.a)).(a.a), (a.(a.(a.a))).a, (((a.a).a).a).a

Crossrefs

Sequence in context: A074933 A157253 A003178 * A169970 A334499 A357950

Adjacent sequences: A079491 A079492 A079493 * A079495 A079496 A079497

Keyword

nonn,hard,more

Author

Don Knuth, Jan 20 2003

Status

approved