

A007123


Number of connected unit interval graphs with n nodes; also number of bracelets (turn over necklaces) with n black beads and n1 white beads.
(Formerly M1218)


12



1, 1, 2, 4, 10, 26, 76, 232, 750, 2494, 8524, 29624, 104468, 372308, 1338936, 4850640, 17685270, 64834550, 238843660, 883677784, 3282152588, 12233309868, 45741634536, 171530482864, 644953425740, 2430975800876
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Also number of rooted planar general trees (of n vertices or n1 edges) up to reflection.  Antti Karttunen, Aug 09 2002 (for the correspondence with bracelets, start by considering Raney's lemma as explained by Graham, Knuth & Patashnik).
Number of connected lattice path matroids on n elements up to isomorphism.
a(n) = number of noncrossing set partitions of [n] up to reflection (i<>n+1i). Example: a(4) counts 123, 123, 132, 123 but not 123 because it is the reflection of 123.  David Callan, Oct 08 2005
From Vladimir Shevelev, Apr 23 2011: (Start)
Also number of nonequivalent necklaces of n beads, each of which is painted by one of 2*n1 colors.
The sequence solves the socalled Reis problem about convex kgons in case N=2*n1, k=n. H. Gupta (1979) gave a full solution; I gave a short proof of Gupta's result and showed an equivalence of this problem and each of the following problems: the problem of enumerating the bracelets of n beads of 2 colors, k of them black, and the problem of enumerating the necklaces of k beads, each painted by one of n colors.
a(n) is an essentially unimprovable upper estimate for the number of distinct values of the permanent in (0,1)circulants of order 2*n1 with n 1's in every row.
(End)


REFERENCES

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.7.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. AddisonWesley, Reading, MA, 1990, p. 345 & 346.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

R. W. Robinson, Table of n, a(n) for n = 1..190
J. E. Bonin, A. de Mier and M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials, arXiv:math/0211188 [math.CO], 2002.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
H. Gupta, Enumeration of incongruent cyclic kgons, Indian J. Pure and Appl. Math., 10 (1979), no.8, 964999.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
V. Shevelev, Necklaces and convex kgons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629638.
V. Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma), arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).
Index entries for sequences related to bracelets


FORMULA

a(n+1) = (Cat(n)+binomial(n, floor(n/2)))/2 = (A000108(n)+A001405(n))/2.  Antti Karttunen, Aug 09 2002
G.f.: (1+2*xsqrt(14*x)*sqrt(14*x^2))/(4*sqrt(14*x^2)).
G.f.: (sqrt((1 + 2*x) / (1  2*x))  sqrt(1  4*x)) / 4.  Michael Somos, Apr 16 2012
a(n) = (A063886(n)  A002420(n)) / 4.  Michael Somos, Apr 16 2012


EXAMPLE

x + x^2 + 2*x^3 + 4*x^4 + 10*x^5 + 26*x^6 + 76*x^7 + 232*x^8 + 750*x^9 + ...


MATHEMATICA

f[k_Integer, n_] := (Plus @@ (EulerPhi[ # ]Binomial[n/#, k/# ] & /@ Divisors[GCD[n, k]])/n + Binomial[(n  If[OddQ@n, 1, If[OddQ@k, 2, 0]])/2, (k  If[OddQ@k, 1, 0])/2])/2  Robert A. Russell, Sep 27 2004
Table[ f[n, 2n  1], {n, 10}]
(* Comment from Wouter Meeussen, Feb 02 2013, added by N. J. A. Sloane, Feb 02 2013: To get lists of the necklaces in Mathematica, use (if n=4, say):
<<Combinatorica`;
ListNecklaces[2*4 1, {0, 1}, Dihedral] *)


PROG

(PARI) {a(n) = if( n<1, 0, (2 * binomial(n1, (n1)\2) + binomial(2*n, n) / (2*n  1)) / 4)} /* Michael Somos, Apr 16 2012 */
(Python)
from sympy import catalan, binomial, floor
def a(n): return 1 if n==1 else (catalan(n  1) + binomial(n  1, floor((n  1)/2)))/2 # Indranil Ghosh, Jun 03 2017


CROSSREFS

Cf. A002420, A007595, A063886, A073201.
Occurs as row 164 in A073201. Nexttocenter columns of triangle A052307.
Sequence in context: A148099 A007579 A239078 * A220871 A007578 A239079
Adjacent sequences: A007120 A007121 A007122 * A007124 A007125 A007126


KEYWORD

nonn,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

Extended by Christian G. Bower
Edited by Jon E. Schoenfield, Feb 14 2015


STATUS

approved



