login
G.f.: A(x) satisfies: coefficient of x^n in A(x)^(n+1)/(n+1) = 2^(n*(n-1)/2).
19

%I #19 Sep 26 2024 03:20:37

%S 1,1,1,4,39,748,27162,1880872,252273611,66358216668,34506398937158,

%T 35644762692112792,73356520492898454022,301274559225693420690360,

%U 2471654510727312089903896948,40527708183358718551543295827536

%N G.f.: A(x) satisfies: coefficient of x^n in A(x)^(n+1)/(n+1) = 2^(n*(n-1)/2).

%C a(n) is the number of graphs on vertices 1,...,n such that, when these vertices are arranged counterclockwise around a circle and edges are drawn as straight line segments, the resulting diagram is connected. - Jonathan Novak (j2novak(AT)math.uwaterloo.ca), Apr 30 2010

%C In this interpretation, both intersecting (set theoretically) and crossing (topologically) edges are considered connected. - _Gus Wiseman_, Feb 23 2019

%H Gus Wiseman, <a href="/A136653/a136653.png">The a(4) = 39 graphs connected by overlaps or crossings.</a>

%F G.f.: A(x) = x/Series_Reversion( x*Sum_{k=0..n} 2^(k(k-1)/2)*x^k ).

%F Equals the free cumulant sequence corresponding to A006125. - Jonathan Novak (j2novak(AT)math.uwaterloo.ca), Apr 30 2010

%e G.f.: A(x) = 1 + x + x^2 + 4*x^3 + 39*x^4 + 748*x^5 + 27162*x^6 +...

%e Let F(x) = 1 + x + 2*x^2 + 8*x^3 + 64*x^4 + 1024*x^5 +...+ 2^(n*(n-1)/2)*x^n +..

%e then A(x) = F(x/A(x)), A(x*F(x)) = F(x).

%e Coefficient of x^n in A(x)^(n+1)/(n+1) = 2^(n*(n-1)/2),

%e as can be seen by the main diagonal in the array of

%e coefficients in the initial powers of A(x):

%e A^1: [(1), 1, 1, 4, 39, 748, 27162, 1880872, 252273611,...;

%e A^2: [1, (2), 3, 10, 87, 1582, 55914, 3817876, 508370795,...;

%e A^3: [1, 3, (6), 19, 147, 2517, 86398, 5813550, 768378627,...;

%e A^4: [1, 4, 10, (32), 223, 3572, 118778, 7870640, 1032387787,...;

%e A^5: [1, 5, 15, 50, (320), 4771, 153245, 9992130, 1300492845,...;

%e A^6: [1, 6, 21, 74, 444, (6144), 190023, 12181278, 1572792585,...;

%e A^7: [1, 7, 28, 105, 602, 7728, (229376), 14441659, 1849390375,...;

%e A^8: [1, 8, 36, 144, 802, 9568, 271616, (16777216), 2130394591,...;

%e A^9: [1, 9, 45, 192, 1053, 11718, 317112, 19192320, (2415919104),...;

%e dividing each diagonal term in row n by (n+1) gives 2^(n*(n-1)/2).

%e The diagonal above the main diagonal gives coefficients of l.g.f.:

%e log(F(x)) = x + 3*x^2/2 + 19*x^3/3 + 223*x^4/4 + 4771*x^5/5 +...

%t max = 15; s = x*Sum[2^(k*(k-1)/2)*x^k, {k, 0, max}] + O[x]^(max+2); x/InverseSeries[s] + O[x]^(max+1) // CoefficientList[#, x]& (* _Jean-François Alcover_, Sep 03 2017 *)

%t croXQ[stn_]:=MatchQ[stn,{___,{___,x_,___,y_,___},___,{___,z_,___,t_,___},___}/;x<z<y<t||z<x<t<y];

%t csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];

%t bicmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],Intersection@@#!={}&],Select[Subsets[stn,{2}],croXQ]]];

%t Table[Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],Length[bicmpts[#]]<=1]&]],{n,0,5}] (* _Gus Wiseman_, Feb 23 2019 *)

%o (PARI) a(n)=polcoeff(x/serreverse(x*sum(k=0,n,2^(k*(k-1)/2)*x^k +x*O(x^n))),n)

%Y Cf. A136652 (log(A(x))), A136654.

%Y Cf. A000699, A002662, A006125, A007297, A016098, A054726, A099947, A306438.

%Y Cf. A324166, A324169, A324172, A324173, A324327, A324328.

%K nonn

%O 0,4

%A _Paul D. Hanna_, Jan 15 2008

%E Name changed and part of prior name moved to formula section by _Paul D. Hanna_, Sep 19 2013