OFFSET
1,1
COMMENTS
Here A,B,C,D are positive integers, in Z+, satisfying A*D-B*C=1.
The SL(2,Z+) monoid may be constructed as a binary tree by starting with the identity matrix, I = [[1,0],[0,1]], then multiply by L = [[1,0],[1,1]] and R = [[1,1],[0,1]] creating the 2nd row in the tree. Multiplying the two elements of the 2nd row by L and R creates the 3rd row. Repeat for each row. See the Python program.
The monoid SL(2,Z+) is isomorphic to the positive rationals Q+. The sum of the rows of an SL(2,Z+) element create a unique reduced fraction, p/q.: [[a,b],[c,d]] => (a+b)/(c+d) = p/q These fractions map to the entries of the Stern-Brocot tree.
SL(2,Z+) is a sub-monoid of SL(2,Z). The generators of SL(2,Z) are [[0,-1],[1,0]] and [[1,1],[0,1]]. The author believes that L and R are generators for SL(2,Z+) and all elements of the monoid are present in the tree.
LINKS
James Kirk Winkler, Table of n, a(n) for n = 1..8191
EXAMPLE
row 1: [[1,0],[0,1]] trace = 2
row 2: [[1,0],[1,1]], [[1,1],[0,1]] trace = 2, 2
row 3: [[1,0],[2,1]], [[1,1],[1,2]], [2,1],[1,1]], [[1,2],[0,1]] trace = 2, 3, 3, 2
...
Sum the matrix rows for the Stern-Brocot tree.
row 1: 1/1
row 2: 1/2, 2/1
row 3: 1/3, 2/3, 3/2, 3/1
...
MATHEMATICA
row[n_] := Module[{v = Table[0, {2^(n-1)}], L = {{1, 0}, {1, 1}}}, For[k = 0, k <= Length[v]-1, k++, v[[k+1]] = Tr[Dot @@ Table[If[BitGet[k, b] == 1, Transpose[L], L], {b, 0, n-2}]]]; v]; row[1] = {2};
Array[row, 7] // Flatten (* Jean-François Alcover, Dec 17 2018, after Andrew Howroyd *)
PROG
(Python)
def mul(A, B):
a = A[0]*B[0] + A[1]*B[2]
b = A[0]*B[1] + A[1]*B[3]
c = A[2]*B[0] + A[3]*B[2]
d = A[2]*B[1] + A[3]*B[3]
return([a, b, c, d])
I = [1, 0, 0, 1]
L = [1, 0, 1, 1]
R = [1, 1, 0, 1]
slg = [I]
a_lst = slg
for n in range(12):
b_lst = []
for ele in a_lst:
b_lst.append(mul(ele, L))
b_lst.append(mul(ele, R))
a_lst = b_lst
for ele in b_lst:
slg.append(ele)
seq = []
for ele in slg:
seq.append(ele[0]+ele[3])
(PARI)
row(n)={my(v=vector(2^(n-1)), L=[1, 0; 1, 1]); for(k=0, #v-1, v[k+1]=trace(prod(b=0, n-2, if(bittest(k, b), L~, L)))); v}
{ for(n=1, 7, print(row(n))) } \\ Andrew Howroyd, Dec 12 2018
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
James Kirk Winkler, Dec 11 2018
STATUS
approved