On the number of F-arithmetic expressions in n distinct variables

Abstract

How many arithmetic expressions are there in n distinct variables? In this paper, we provide a Θ(n2) algorithm for computing this number for arithmetic expressions over an arbitrary field F. We consider several cases of this problem with various restrictions on the allowed operations. An expression tree is an ordered rooted tree whose internal nodes represent operations to be performed, while its leaves correspond to formal variables from a set X. We view any arithmetic expression as an element of F(X) that is obtained by evaluating an expression tree.