Expressions with n variables

The original motivation was to make an efficient algorithm to solve such problems as: use 1,1,5,8 to make 10 with addition, subtraction, multiplication, division (called "sisoku" in Japanese). It was not successful, but instead, I listed up all expressions (ignoring sign). Ignoring sign is useful because numbers are often all positive in such problems.

---- The Idea ----

---- The First Step ----

For n=3, there are 4 types: a+a+a, aaa, a+aa, a(a+a).
If labeled, there are 8 types: a+b+c, abc, a+bc, b+ac, c+ab, a(b+c), b(a+c), c(a+b).
Each expression with addition and multiplication is conjugated with a "series-parallel network". We can regard series part as addition and parallel part as multiplication. The enumeration are registered on A000084(unlabeled) and A006351(labeled)[*1]. For n=3, they are 4 and 8, consistent with numbers of types above. I found the reference[*2] available to generate all series-parallel graphs.

My source code: spg.js and the result: spgraph.txt

In this result, a(aa) gives both a+aa and a(a+a). So the sizes of arrays are half of A000084 (also resistered as A000669).

Reference:
[*1] https://oeis.org/ The On-Line Encyclopedia of Integer Sequences
[*2] http://ci.nii.ac.jp/naid/110002811999
直並列グラフの列挙 Generating All Series-parallel Graphs
川野 晋一郎 Kawano Shin-ichiro, 中野 眞一 Nakano Shin-ichi
情報処理学会研究報告. AL, アルゴリズム研究会報告

---- The Second Step ----

The labeling is done by the restriction (1) below. There needs some other restrictions for mixing subtraction and division. Without restrictions, for example, we may get:
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]
abc -> [abc, a*b/c, a/b*c, 1/a*b*c, a/b/c, a/b/c, 1/a/b*c, 1/a/b/c] [*3]
Each last one is not appropriate. Also, a+b-c and -a-b+c (etc.) are equivalent. Following restrictions works well to avoid these problems.
　(1) If two term are the same unlabeled type, the latter is labeled bigger. [*4]
　(2) The first term is positive (addition and subtraction).
　(3) At least one term is multiplying (multiplication and division).
Thus we can obtain the all expressions.

My source code: sisoku.js and the result: sisoku4.txt (n=4), sisoku5.txt (n=5)
I could not upload the file of n=6 because of the file size.

[*3] a/b*c means (a/b)*c, and a/b/c means (a/b)/c, which equals a/(bc).
[*4] Big or small is determined by the character codes ("b">"a" is true in javascript).

Actually we can solve the sisoku problem using the list, for example:
var B="a+b+c+d,a+b+c-d,..(abbreviated)..,c/(a-b)-d".split(",");
var a=1,b=1,c=5,d=8,aim=10,x,i;
for(i=0;x=B[i];i++)if(eval(x)==aim||eval(x)==-aim)alert(x);

Let X be the number of expressions using at least one minus, and Y without minus. Then, 2X+Y gives the number of all expressions not ignoring sign, which is registered on A140606. Expressions without minus can be obtained by modifying the restriction (2) above: sisoku_no_minus.txt (n=3,4,5). The numbers are consistent with A140606:

Acknowledgement ... Always thanks to everyone, 2014/9/29 Azuma Seiichi