A005004 Davenport-Schinzel numbers of degree n on 3 symbols.

1, 3, 5, 8, 10, 14, 16, 20, 22, 26, 28, 32, 34, 38, 40, 44, 46, 50, 52, 56, 58, 62, 64, 68, 70, 74, 76, 80, 82, 86, 88, 92, 94, 98, 100, 104, 106, 110, 112, 116, 118, 122, 124, 128, 130, 134, 136, 140, 142, 146, 148, 152, 154, 158, 160, 164, 166

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

References

• Annette J. Dobson and Shiela Oates Macdonald, "Lower bounds for the lengths of Davenport-Schinzel sequences", Utilitas Mathematica 6 (1974): 251-257.
• R. K. Guy, Unsolved Problems in Number Theory, E20.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• R. G. Stanton and P. H. Dirksen, Davenport-Schinzel sequences, Ars. Combin., 1 (1976), 43-51.

Links

• Pankaj K. Agarwal, Micha Sharir, and Peter Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, Journal of Combinatorial Theory, Series A 52.2 (1989): 228-274.
• Boris Aronov and Dmitriy Drusvyatskiy, Complexity of a Single Face in an Arrangement of s-Intersecting Curves, arXiv:1108.4336v1 [cs.CG], 2011.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• R. G. Stanton and P. H. Dirksen, Davenport-Schinzel sequences, Ars. Combin., 1 (1976), 43-51. [Annotated scanned copy]
• R. G. Stanton and P. H. Dirksen, Davenport-Schinzel sequences, Ars. Combin., 1 (1976), 43-51. [Annotated scanned copy, different annotations from one above]
• Index entries for linear recurrences with constant coefficients, signature (1, 1, -1).

Crossrefs

Cf. A002004.

A row of the array in A259874.

Programs

Maple

A005004:=(z**3-z**2+z+1)*(z**2+z+1)/(1+z)/(z-1)**2; # Conjectured by Simon Plouffe in his 1992 dissertation

Mathematica

Join[{1, 3, 5}, LinearRecurrence[{1, 1, -1}, {8, 10, 14}, 60]] (* Jean-François Alcover, Sep 04 2018 *)

Formula

For n > 3, a(2*n) = 6 * n - 4 and a(2*n+1) = 6 * n - 5. - Sean A. Irvine, Feb 19 2016

Extensions

Improved title and more terms from Sean A. Irvine, Feb 19 2016