A005004 - OEIS

A005004

Davenport-Schinzel numbers of degree n on 3 symbols.
(Formerly M2431)

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

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

Table of n, a(n) for n=1..57.

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).

FORMULA

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

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 *)

CROSSREFS

Cf. A002004.

A row of the array in A259874.

Sequence in context: A051611 A258028 A345427 * A006218 A062839 A372866

Adjacent sequences: A005001 A005002 A005003 * A005005 A005006 A005007