cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A079491 Numerator of Sum_{k=0..n} binomial(n,k)/2^(k*(k-1)/2).

Original entry on oeis.org

1, 2, 7, 45, 545, 12625, 564929, 49162689, 8361575425, 2789624383745, 1830776926245889, 2368773751202917377, 6053217182280501452801, 30595465072175429929979905, 306239118989330960523869667329, 6076268165073202122463201684865025
Offset: 0

Views

Author

N. J. A. Sloane, Jan 20 2003

Keywords

Comments

Conjecture: Also the number of loop-graphs on n vertices without any non-loop edge having loops at both ends, with formula a(n) = Sum_{k=0..n} binomial(n,k) 2^(k*(n-k) + binomial(k,2)). The unlabeled version is A339832. - Gus Wiseman, Jan 25 2024
The above conjecture is true since (n-k)*k + binomial(n-k,2) = binomial(n,2) - binomial(k,2) and A006125 gives the denominators for this sequence. - Andrew Howroyd, Feb 20 2024

Examples

			1, 2, 7/2, 45/8, 545/64, 12625/1024, 564929/32768, 49162689/2097152, ...

References

  • D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, CRC Press, 1999, p. 113.

Links

Crossrefs

Denominators are in A006125.
Cf. A079492.
The unlabeled version is A339832 (loop-graphs interpretation).
A000085, A100861, A111924 count set partitions into singletons or pairs.
A000666 counts unlabeled loop-graphs, covering A322700.
A006125 (shifted left) counts labeled loop-graphs, covering A322661.
A006129 counts labeled covering graphs, connected A001187.

Programs

  • Magma
    [Numerator( (&+[Binomial(n,k)/2^Binomial(k,2): k in [0..n]]) ): n in [0..20]]; // G. C. Greubel, Jun 19 2019
  • Maple
    f := n->add(binomial(n,k)/2^(k*(k-1)/2),k=0..n);
  • Mathematica
    Table[Numerator[Sum[Binomial[n,k]/2^Binomial[k,2], {k,0,n}]], {n,0,20}] (* G. C. Greubel, Jun 19 2019 *)
  • PARI
    {a(n)=n!*polcoeff(sum(k=0, n, exp(2^k*x +x*O(x^n))*2^(k*(k-1)/2)*x^k/k!), n)} \\ Paul D. Hanna, Sep 14 2009
  • PARI
    a(n) = sum(k=0, n, binomial(n,k)*2^(binomial(n,2)-binomial(k,2))) \\ Andrew Howroyd, Feb 20 2024
  • Sage
    [numerator( sum(binomial(n,k)/2^binomial(k,2) for k in (0..n)) ) for n in (0..20)] # G. C. Greubel, Jun 19 2019

Formula

E.g.f.: Sum_{n>=0} a(n)*x^n/n! = Sum_{n>=0} exp(2^n*x)*2^(n(n-1)/2)*x^n/n!. - Paul D. Hanna, Sep 14 2009
a(n) = Sum_{k=0..n} binomial(n,k) * 2^(binomial(n,2)-binomial(k,2)). - Andrew Howroyd, Feb 20 2024

A339830 Number of bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other.

Original entry on oeis.org

1, 2, 2, 4, 10, 26, 75, 234, 768, 2647, 9466, 34818, 131149, 503640, 1965552, 7777081, 31138051, 125961762, 514189976, 2115922969, 8769932062, 36584593158, 153510347137, 647564907923, 2744951303121, 11687358605310, 49965976656637, 214423520420723, 923399052307921
Offset: 0

Views

Author

Andrew Howroyd, Dec 19 2020

Keywords

Comments

The black nodes form an independent vertex set. For n > 0, a(n) is then the total number of indistinguishable independent vertex sets summed over distinct unlabeled trees with n nodes.

Examples

			a(2) = 2 because at most one node can be colored black.
a(3) = 4 because the only tree is the path graph P_3. If the center node is colored black then neither of the ends can be colored black; otherwise zero, one or both of the ends can be colored black. In total there are 4 possibilities.
There are 3 trees with 5 nodes:
    o                                     o
    |                                     |
    o---o---o    o---o---o---o---o    o---o---o
    |                                     |
    o                                     o
These correspond respectively to 11, 9 and 6 bicolored trees (with black nodes not adjacent), so a(5) = 11 + 9 + 6 = 26.

Links

Crossrefs

Cf. A038056 (bicolored trees), A339829, A339831, A339832, A339834, A339837.

Programs

  • PARI
    EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=v=[1]); for(n=2, n, my(t=concat([1], EulerT(v))); v=concat([1], EulerT(u+v)); u=t); my(g=x*Ser(u+v), gu=x*Ser(u)); Vec(1 + g + (subst(g,x,x^2) - subst(gu,x,x^2) - g^2 + gu^2)/2)}

A339836 Number of bicolored graphs on n unlabeled nodes such that every white node is adjacent to a black node.

Original entry on oeis.org

1, 1, 3, 10, 47, 296, 2970, 49604, 1484277, 81494452, 8273126920, 1552510549440, 538647737513260, 346163021846858368, 413301431190875322768, 920040760819708654610560, 3832780109273882704828352620, 29989833030101321999992097828464, 442280129125813382230656891568680400
Offset: 0

Views

Author

Andrew Howroyd, Dec 19 2020

Keywords

Comments

The black nodes form a dominating set. For n > 0, a(n) is then the total number of indistinguishable dominating sets summed over distinct unlabeled graphs on n nodes.

Links

Crossrefs

A049312 counts bicolored graphs where adjacent nodes cannot have the same color.
A000666 counts bicolored graphs where adjacent nodes can have the same color.
Cf. A339832, A339834 (trees), A340021.

Programs

  • PARI
    permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
dom(u, v) = {prod(i=1, #u, 2^sum(j=1, #v, gcd(u[i], v[j]))-1)}
U(nb,nw)={my(s=0); forpart(u=nw, my(t=0); forpart(v=nb, t += permcount(v) * 2^edges(v) * dom(u,v)); s += t*permcount(u) * 2^edges(u)/nb!); s/nw!}
a(n)={sum(k=0, n, U(k, n-k))}

A340021 Number of bicolored graphs on n unlabeled nodes such that black nodes are not adjacent to each other and every white node is adjacent to a black node.

Original entry on oeis.org

1, 1, 2, 5, 16, 66, 407, 3948, 66781, 2057140, 117820559, 12562407832, 2488441442819, 915216371901462, 625792587599236833, 797474948692631218674, 1899724021357155410243835, 8486672841492724213636009230, 71324140440429733888694354552551, 1131126439181050621704917376323373818
Offset: 0

Views

Author

Andrew Howroyd, Dec 30 2020

Keywords

Comments

The black nodes form a maximal independent vertex set (or a set that is both independent and dominating). For n > 0, a(n) is then the total number of indistinguishable maximal independent vertex sets summed over distinct unlabeled graphs with n nodes.

Links

Crossrefs

A049312 counts bicolored graphs where adjacent nodes cannot have the same color.
A000666 counts bicolored graphs where adjacent nodes can have the same color.
Cf. A339832 (independent only), A339836 (dominating only), A339837 (trees).

Programs

  • Mathematica
    permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
dom[u_, v_] := Product[2^Sum[GCD[u[[i]], v[[j]]], {j, 1, Length[v]}] - 1, {i, 1, Length[u]}];
U[nb_, nw_] := Module[{s = 0}, Do[t = 0; Do[t += permcount[v]*dom[u, v], {v, IntegerPartitions[nb]}]; s += t*permcount[u]*2^edges[u]/nb!, {u, IntegerPartitions[nw]}]; s/nw!];
a[n_] := Sum[U[k, n - k], {k, 0, n}];
Array[a, 20] (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)
  • PARI
    permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
dom(u, v) = {prod(i=1, #u, 2^sum(j=1, #v, gcd(u[i], v[j]))-1)}
U(nb, nw)={my(s=0); forpart(u=nw, my(t=0); forpart(v=nb, t += permcount(v) * dom(u, v)); s += t*permcount(u) * 2^edges(u)/nb!); s/nw!}
a(n)={sum(k=0, n, U(k, n-k))}

A370165 Number of labeled loop-graphs covering n vertices without a non-loop edge with loops at both ends.

Original entry on oeis.org

1, 1, 4, 29, 400, 10289, 496548, 45455677, 7983420736, 2716094133313, 1803251169342820, 2348787270663723581, 6024912118926389490448, 30516957491540079828757553, 305811332460677494410532494660, 6071677788061208810793717466942237
Offset: 0

Views

Author

Gus Wiseman, Feb 12 2024

Keywords

Comments

Number of ways to choose a stable vertex set of a simple graph with n vertices.

Examples

			The a(3) = 29 loop-graphs (loops shown as singletons):
  {1,23}   {1,2,3}     {1,2,13,23}
  {2,13}   {1,2,13}    {1,3,12,23}
  {3,12}   {1,2,23}    {2,3,12,13}
  {12,13}  {1,3,12}    {1,12,13,23}
  {12,23}  {1,3,23}    {2,12,13,23}
  {13,23}  {2,3,12}    {3,12,13,23}
           {2,3,13}
           {1,12,13}
           {1,12,23}
           {1,13,23}
           {2,12,13}
           {2,12,23}
           {2,13,23}
           {3,12,13}
           {3,12,23}
           {3,13,23}
           {12,13,23}

Links

Crossrefs

Without loops we have A006129, connected A001187.
The non-covering version is A079491.
The unlabeled version is A370166, non-covering A339832.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A000666 counts unlabeled loop-graphs, covering A322700.
A006125 counts labeled loop-graphs (shifted left), covering A322661.
Cf. A048291, A062740, A116539, A320461, A322635.

Programs

  • Mathematica
    Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]], Union@@#==Range[n]&&!MatchQ[#, {_,{x_},_,{y_},_,{x_,y_},_}]&]],{n,0,5}]
  • PARI
    seq(n)={Vec(serlaplace(sum(k=0, n, exp((2^k-1)*x + O(x*x^n))*2^(k*(k-1)/2)*x^k/k!)))} \\ Andrew Howroyd, Feb 20 2024

Formula

Inverse binomial transform of A079491.
E.g.f.: Sum_{k >= 0} exp((2^k-1)*x)*2^(k*(k-1)/2)*x^k/k!. - Andrew Howroyd, Feb 20 2024

A370166 Number of unlabeled loop-graphs covering n vertices without a non-loop edge with loops at both ends.

Original entry on oeis.org

1, 1, 3, 9, 36, 180, 1313, 14709, 277755, 9304977, 568315345, 63806703305, 13200565313255, 5042653259803433, 3567050969262370941, 4688444463558713135201, 11491940559865490367844649, 52719458629883487816297211441, 454220675869975957947658748125099
Offset: 0

Views

Author

Gus Wiseman, Feb 12 2024

Keywords

Examples

			Representatives of the a(0) = 1 through a(3) = 9 loop-graphs (loops shown as singletons):
  {}  {{1}}  {{1,2}}      {{1},{2,3}}
             {{1},{2}}    {{1,2},{1,3}}
             {{1},{1,2}}  {{1},{2},{3}}
                          {{1},{2},{1,3}}
                          {{1},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}
                          {{1,2},{1,3},{2,3}}
                          {{1},{2},{1,3},{2,3}}
                          {{1},{1,2},{1,3},{2,3}}

Crossrefs

Without loops we have A002494, labeled A006129, connected A001349.
The non-covering version is A339832.
The labeled version is A370165, non-covering A079491 (apparently).
A000666 counts unlabeled loop-graphs, covering A322700.
A006125 counts labeled loop-graphs (shifted left), covering A322661.
Cf. A000085, A001187, A048291, A062740, A116539.

Programs

  • Mathematica
    brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{1,2}]],Union@@#==Range[n] && !MatchQ[#,{_,{x_},_,{y_},_,{x_,y_},_}]&]]], {n,0,4}]

Formula

First differences of A339832 (the non-covering version).
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.