A008927 Number of increasing sequences of star chain type with maximal element n.

1, 1, 1, 2, 3, 6, 10, 20, 36, 70, 130, 252, 475, 916, 1745, 3362, 6438, 12410, 23852, 46020, 88697, 171339, 330938, 640189, 1238751, 2399677, 4650819, 9021862, 17510819, 34013311, 66106491, 128568177, 250191797, 487168941, 949133722, 1850211247, 3608650388

Offset: 1

Author

Mauro Torelli (torelli(AT)hermes.mc.dsi.unimi.it)

Keywords

• nonn

Comments

a(n) counts the Brauer addition chains for n, which are equivalent to star chains. In a Brauer chain, each element after the first is the sum of any previous element with the immediately previous element. This sequence counts all Brauer chains for n, not just the minimal ones, which are given by A079301. - David W. Wilson, Apr 01 2006

In other words, a(n) = the number of increasing star addition chains ending in n.

Examples

			a(5)=3 because 1,2,3,4,5; 1,2,3,5; 1,2,4,5 are star-kind addition chains.
a(8)=20 because there are 21 increasing addition chains up to 8, but 1,2,4,5,8 is not a star chain.
		

References

• M. Torelli, Increasing integer sequences and Goldbach's conjecture, preprint, 1996.
• D. E. Knuth, The Art of Computer Programming; Addison-Wesley. Section 4.6.3.

Links

• Martin Fuller, Table of n, a(n) for n = 1..70
• M. Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications, vol.40, no.02 (April 2006), pp.107-121.

Crossrefs

Cf. A008928, A079301.

Formula

Conjecture: a(n) ~ 2^n/n. - Martin Fuller, Apr 29 2025

Extensions

More terms from David W. Wilson, Apr 01 2006