|
%I #16 Feb 24 2019 01:54:07
%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
|
