A008909 Join 2n points on a line with n arcs above the line; form graph with the arcs as nodes, joining 2 nodes when the arcs cross. a(n) is the number of cases in which the graph is a path.

1, 1, 3, 8, 21, 56, 153, 428, 1222, 3549, 10454, 31159, 93801, 284788, 871007, 2681018, 8298932, 25817395, 80674901, 253106836, 796968055, 2517706036, 7977573202, 25347126629, 80738862084, 257778971503, 824798533932, 2644335308021, 8493626448823

Offset: 1

Author

Martin Klazar

Keywords

• nonn

Comments

a(n+1) is the number of (finite) positive integer sequences b(1),...,b(k) with b(1) + Sum_{i=1..k-1} (1+max{b(i+1)-b(i), 0}) <= n. - Klaus Strassburger. [E.g., a(4)=8 since the integer sequences are 1; 2; 3; 1,1; 1,2; 2,1; 2,2; 1,1,1.]

Formula

G.f. (conjecture): 1 - G(0)/(1-x), where G(k)= 1 - 1/(1 - x/(1 - x/(1 - x/(1 - x/(x - 1/G(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, Jul 12 2013

G.f. (conjecture): (2*x^3-x^2+2*x-1+sqrt(x^4+2*x^2-4*x+1))/(2*x^2-2*x). - Michael D. Weiner, Dec 17 2019

Extensions

More terms from Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de), Sep 24 2001

More terms from Sean A. Irvine, Apr 10 2018