A214872 The number of subsets of positive integers of cardinality n, produced as the steps in a computation starting with 1 and using the operations of multiplication, addition, or subtraction.

1, 2, 8, 59, 663, 10609, 225219, 6057298, 199290037, 7805646133, 356263294786, 18626811747385

Offset: 1

Author

Gil Dogon, May 03 2013

Keywords

• nonn
• hard

Comments

A straight-line program (SLP) is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction. The length of the SLP is defined as that of the sequence without the first 1. An SLP is said to be positive if all numbers in the sequence are positive, and reduced if there is no repetition in the sequence. Two SLPs are considered equivalent if their sequence consists of the same numbers (only difference is sequence order). This OEIS sequence gives the number of reduced positive SLPs with n steps.

For most purposes only positive SLPs can be considered, as for every general SLP sequence, applying absolute value to all the steps will produce a positive SLP.

This OEIS sequence can also be thought of as defining the size of the search space that needs to be traversed when trying to compute other SLP related OEIS sequences as given in the cross references below.

Examples

			a(1) = 1 and the SLP is (1,2).
a(2) = 2 and the positive SLPs are (1,2,3) (1,2,4).
a(3) = 8 and the positive SLPs are (1,2,3,4) (1,2,3,5) (1,2,3,6) (1,2,3,9) (1,2,4,5) (1,2,4,6) (1,2,4,8) (1,2,4,16).
Notice that also (1,2,4,3) is a legal positive reduced length 3 SLP sequence but it is equivalent to (1,2,3,4) hence is not enumerated.
		

Links

• Al Zimmermann, Al Zimmermann's Programming Contests: Factorials

Crossrefs

Cf. A217032, A216999, A217031, A173419, A141414.

Formula

a(n) >= a(n-1) * 2 * (n-1) and a(2)=2 Hence a(n) >= 2^(n-1)*(n-1)! .

The recurrence above is true since if the maximum of an SLP sequence of length n-1 is added to all elements except itself, and multiplied with all elements except the first 1 (including itself), then 2n-2 different extensions of the original SLP sequence are produced, resulting in 2n-2 reduced SLP's of length n.