A003661 Number of bipartite Steinhaus graphs on n nodes. (Formerly M0996)

1, 2, 4, 6, 9, 10, 13, 15, 19, 19, 21, 23, 27, 28, 31, 34, 39, 38, 39, 40, 43, 44, 47, 50, 55, 55, 57, 59, 63, 65, 69, 73, 79, 77, 77, 77, 79, 79, 81, 83, 87, 87, 89, 91, 95, 97, 101, 105, 111, 110, 111, 112, 115, 116, 119, 122, 127, 128, 131, 134, 139, 142, 147, 152, 159

Offset

1,2

References

W. M. Dymacek, M. Koerlin and T. Whaley, A survey of Steinhaus graphs, Proc. 8th Quadrennial International Conf. on Graph Theory, Combinatorics, Algorithms and Application, Kalamazoo, Mich. 1996, pages 313-323, Vol. I.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

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

W. Dymacek, T. Whaley, Generating strings for bipartite Steinhaus graphs, Discrete Math. 141 (1995), pages 97-107.

Hsien-Kuei Hwang, S. Janson, T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.

Hsien-Kuei Hwang, S. Janson, T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.

Formula

a(n) <= (5n-7)/2 (n > 2) with equality for n=2^k + 1.

a(2k+1)=2a(k+1)+1; a(2k)=a(k)+a(k+1) for k >=2.

Maple

a := proc(n) if n=1 then 1 elif n=2 then 2 elif n=3 then 4 elif n mod 2 = 1 then 2*a((n+1)/2) + 1 else a(n/2)+a(n/2+1) fi end: seq(a(n), n=1..80);

Crossrefs

Sequence in context: A392663 A184416 A187225 * A065387 A219787 A331006

Adjacent sequences: A003658 A003659 A003660 * A003662 A003663 A003664

Keyword

nonn

Author

N. J. A. Sloane, Mira Bernstein

Extensions

More terms from Emeric Deutsch, Feb 26 2004

Status

approved