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

%I #6 Aug 09 2015 00:02:29

%S 1,1,2,2,6,8,26,55,148,377,1066,2853,8044,22298,63134,178399,509944,

%T 1460728,4213962,12194213

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

%C 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".

%C 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.

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

%e 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

%K nonn,hard,more

%O 0,3

%A _Don Knuth_, Jan 20 2003