login
Let r be the matrix {{1,1},{0,1}} and b={{1,0},{1,0}}. Let A be the semigroup generated by r and b. a(n) is the number of words of length n in A.
0

%I #8 Sep 29 2017 09:00:50

%S 1,2,3,5,8,12,18,26,37,51,69,92,121,157,202,257,324,405,503,620,760,

%T 926,1122,1353,1624,1941,2310,2739,3235,3808,4468,5226,6095,7088,8221,

%U 9511,10976,12638,14519,16644,19041

%N Let r be the matrix {{1,1},{0,1}} and b={{1,0},{1,0}}. Let A be the semigroup generated by r and b. a(n) is the number of words of length n in A.

%C The generating function was found by _Moshe Shmuel Newman_.

%H Melvyn B. Nathanson, <a href="https://www.jstor.org/stable/2589496">Number Theory and semigroups of intermediate growth</a>, Amer. Math. Monthly 106(1999) 666-669.

%F G.f.: 1/(1-x)+ x/((1-x)^2 (1-x^2)(1-x^3)(1-x^5)(1-x^7)(1-x^11)...) where the product is over all primes.

%e The products of two matrices in A are r.r, r.b, b.r and b.b, that is {{1, 2}, {0, 1}}, {{2, 0}, {1, 0}}, {{1, 1}, {1, 1}}, {{1, 0}, {1, 0}}.

%e Of these, the last one, b.b is an element of length one, since it is equal to b. The remainder are elements of length two, hence a(2)=3.

%K nonn

%O 0,2

%A _David S. Newman_, Sep 04 2006