

A007123


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


13



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, 9183681736376, 34766785487152, 131873995933480
(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
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)
The number of Dyck paths of semilength n1 up to reversal; that is, the number of Dyck paths of semilength n1, treating as identical a path and that path when traveled in reverse order.  Noah A Rosenberg, Jan 28 2019


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



FORMULA

G.f.: (1 + 2*x  sqrt(1  4*x)*sqrt(1  4*x^2))/(4*sqrt(1  4*x^2)).
G.f.: (sqrt((1 + 2*x) / (1  2*x))  sqrt(1  4*x)) / 4.  Michael Somos, Apr 16 2012
Dfinite with recurrence n*(n1)*(n4)*a(n)  4*(n1)*(n^25*n+5)*a(n1)  4*(n2)*(n^27*n+11)*a(n2) + 8*(2*n7)*(n2)*(n3)*a(n3)=0.  R. J. Mathar, Aug 22 2018


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}]
<<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

Nexttocenter columns of triangle A052307.


KEYWORD

nonn,nice


AUTHOR



EXTENSIONS



STATUS

approved



