A351922 Consider well-formed strings consisting of n operands, n - 1 binary operators +, -, *, /, ^, and n-1 pairs of parentheses, and call two such strings equivalent if they are algebraically identical; a(n) is the number of equivalence classes.

1, 8, 146, 4294

Offset

1,2

Comments

E.g., a+b-c is considered equivalent to b-c+a; (a-b)/(c-d) to (b-a)/(d-c); and (a^b)^c to a^(b*c). Each algebraically equivalent possibility is counted once. Parentheses can be used freely.

Links

Table of n, a(n) for n=1..4.

N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: Slides; Slides (an alternative source).

Example

For n = 2 the a(2) = 8 expressions are a+b, a-b, b-a, a*b, a/b, b/a, a^b, b^a. b+a does not count because it is equivalent to a+b.
For n=3, the a(3)=146 expressions (as rendered canonically by fullratsimp/fortran in maxima) are: a*b-a*c; a*b-b*c; (a*b)/c; (a-b)*c; (a-b)^c; a*b*c; a*b-c; a*b^c; a-b*c; a-b^c; a/(b*c); a/b^c; a^(b*c); a^(b-c); a^(b/c); a^b*c; a^b-c; a^b/c; a^b^c; a^b*c^b; a^b/c^b; a*c+a*b; a*c-a*b; (a*c)/b; (a-c)^b; -a/(c-b); a*c+b; a*c-b; a*c^b; a-c^b; a/(c+b); a/(c-b); a/c^b; a^(c+b); a^(c-b); a^(c/b); a^c*b; a^c-b; a^c/b; a^c^b; (a*c+b)/a; (a*c-b)/a; -(a*c-b)/a; (a*c+b)/c; (a*c-b)/c; -(a*c-b)/c; a^c*b^c; a^c/b^c; (b+a)*c; (b+a)/c; (b+a)^c; (b-a)*c; (b-a)/c; (b-a)^c; -(b-a)/c; b+a^c; b-a*c; b-a^c; b/(a*c); b/a^c; b^(a*c); b^(a-c); b^(a/c); b^a*c; b^a-c; b^a/c; b^a^c; b^a*c^a; b^a/c^a; (b*c)/a; (b-c)^a; -b/(c-a); b*c+a; b*c-a; b*c^a; b-c^a; b/(c+a); b/(c-a); b/c^a; b^(c+a); b^(c-a); b^(c/a); b^c+a; b^c-a; b^c/a; b^c^a; (b*c+a)/b; (b*c-a)/b; -(b*c-a)/b; b*c+a*b; b*c-a*b; (b*c+a)/c; (b*c-a)/c; -(b*c-a)/c; b^c/a^c; (c+a)/b; (c+a)^b; (c-a)/b; (c-a)^b; -(c-a)/b; c+a*b; c+a^b; c-a*b; c-a^b; c/(a*b); c/a^b; c^(a*b); c^(a-b); c^(a/b); c^a+b; c^a-b; c^a/b; c^a^b; (c+a*b)/a; (c-a*b)/a; -(c-a*b)/a; c^a/b^a; (c+a*b)/b; (c-a*b)/b; -(c-a*b)/b; (-c)+b+a; (-c)+b-a; (-c)-b+a; (c+b)/a; (c+b)^a; (c-b)/a; (c-b)^a; -(c-b)/a; -c/(b-a); c+b+a; c+b-a; c+b^a; c-b+a; c-b-a; c-b^a; c/(b+a); c/(b-a); c/b^a; c^(b+a); c^(b-a); c^(b/a); c^b+a; c^b-a; c^b/a; c^b^a; c^b/a^b.

Crossrefs

Cf. A140606 (which does not allow ^).

Sequence in context: A123812 A064331 A230938 * A239758 A239759 A279127

Adjacent sequences: A351919 A351920 A351921 * A351923 A351924 A351925

Keyword

nonn,more,hard,nice

Author

Jonathan Dushoff, Feb 25 2022

Status

approved