A079491 -id:A079491 - cp's OEIS frontend

A165327 E.g.f: Sum_{n>=0} 2^(n(n-1)) * exp(2^nx) x^n/n!.

1, 2, 9, 125, 6561, 1419857, 1291467969, 4902227890625, 76686282021340161, 4891005035897482905857, 1262332172765951010966606849, 1312086657801266767978668212890625

Offset: 0

Paul D. Hanna, Sep 15 2009

nonn

More generally, Sum_{n>=0} m^n * q^(n^2) * exp(b*q^n*x) * x^n/n! = Sum_{n>=0} (m*q^n + b)^n * x^n/n! for all q, m, b.

			E.g.f: A(x) = 1 + 2*x + 3^2*x^2/2! + 5^3*x^3/3! + 9^4*x^4/4! +...
A(x) = exp(x) + exp(2x)*x + 2^2*exp(4x)*x^2/2! + 2^6*exp(8x)*x^3/3! +...
This is a special case of the more general statement:
Sum_{n>=0} m^n * F(q^n*x)^b * log(F(q^n*x) )^n / n! = Sum_{n>=0} x^n * [y^n] F(y)^(m*q^n + b) where F(x) = exp(x), q=2, m=1/2, b=1.

Cf. variants: A136516, A055601, A079491.

{a(n,q=2,m=1/2,b=1)=n!*polcoeff(sum(k=0, n, m^k*q^(k^2)*exp(b*q^k*x+x*O(x^n))*x^k/k!), n)}

a(n) = (2^(n-1) + 1)^n.

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

Original entry on oeis.org

1, 2, 5, 14, 50, 230, 1543, 16252, 294007, 9598984, 577914329, 64384617634, 13264949930889, 5055918209734322, 3572106887472105263, 4692016570446185240464, 11496632576435936553085113, 52730955262459923752850296554, 454273406825238417871411598421653

Offset: 0

Andrew Howroyd, Dec 19 2020

nonn

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 graphs on n nodes.

Andrew Howroyd, Table of n, a(n) for n = 0..40
Eric Weisstein's World of Mathematics, Independent Vertex Set

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. A079491 (labeled case), A339830 (trees), A339836, A340021.

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)}
cross(u, v) = {sum(i=1, #u, sum(j=1, #v, gcd(u[i], v[j])))}
U(nb,nw)={my(s=0); forpart(v=nw, my(t=0); forpart(u=nb, t += permcount(u) * 2^cross(u,v)); s += t*permcount(v) * 2^edges(v)/nb!); s/nw!}
a(n) = {sum(k=0, n, U(k, n-k))}

A180602 a(n) = (2^(n+1) - 1)^n.

Original entry on oeis.org

1, 3, 49, 3375, 923521, 992436543, 4195872914689, 70110209207109375, 4649081944211090042881, 1227102111503512992112190463, 1291749870339606615892191271170049, 5429914198235566686555216227881787109375

Offset: 0

Paul D. Hanna, Sep 11 2010

More generally, we have the following identities:
(1) Sum_{n>=0} m^n* F(q^n*x)^b* log( F(q^n*x) )^n/n! = Sum_{n>=0} x^n* [y^n] F(y)^(m*q^n + b);
(2) Sum_{n>=0} m^n* q^(n^2)* exp(b*q^n*x)*x^n/n! = Sum_{n>=0} (m*q^n + b)^n*x^n/n! for all q, m, b.
This sequence results from (2) when q=2, m=2, b=-1.
For n >= 2, a(n) is the first number in a set of three powerful numbers in arithmetic progression with difference a(n)*(2^n - 1). - Arkadiusz Wesolowski, Aug 26 2013

			E.g.f: A(x) = 1 + 3*x + 7^2*x^2/2! + 15^3*x^3/3! + 31^4*x^4/4! +...
A(x) = exp(-x) + 2^2*exp(-2*x)*x + 2^6*exp(-4*x)*x^2/2! + 2^12*exp(-8*x)*x^3/3! +...

Cf. A086459 (signed, offset 1), variants: A055601, A079491, A136516, A165327.

Cf. A001694.

[(2^(n+1)-1)^n : n in [0..11]]; // Arkadiusz Wesolowski, Aug 26 2013

A180602:=n->(2^(n+1) - 1)^n: seq(A180602(n), n=0..10); # Wesley Ivan Hurt, Oct 09 2014

Table[(2^(n + 1) - 1)^n, {n, 0, 10}] (* Wesley Ivan Hurt, Oct 09 2014 *)

{a(n)=n!*polcoeff(sum(k=0, n, 2^(k^2+k)*exp(-2^k*x+x*O(x^n))*x^k/k!), n)}

def A180602(n): return ((1<Chai Wah Wu, Sep 13 2024

E.g.f.: Sum_{n>=0} 2^(n^2+n) * exp(-2^n*x) * x^n/n!.

Name changed by Arkadiusz Wesolowski, Aug 26 2013

A368928 Triangle read by rows where T(n,k) is the number of labeled loop-graphs with n vertices and n edges, k of which are loops.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 1, 9, 9, 1, 15, 80, 90, 24, 1, 252, 1050, 1200, 450, 50, 1, 5005, 18018, 20475, 9100, 1575, 90, 1, 116280, 379848, 427329, 209475, 46550, 4410, 147, 1, 3108105, 9472320, 10548720, 5503680, 1433250, 183456, 10584, 224, 1

Offset: 0

Gus Wiseman, Jan 11 2024

			Triangle begins:
     1
     0     1
     0     2     1
     1     9     9     1
    15    80    90    24     1
   252  1050  1200   450    50     1
  5005 18018 20475  9100  1575    90     1
The loop-graphs counted in row n = 3 (loops shown as singletons):
  {12}{13}{23}  {1}{12}{13}  {1}{2}{12}  {1}{2}{3}
                {1}{12}{23}  {1}{2}{13}
                {1}{13}{23}  {1}{2}{23}
                {2}{12}{13}  {1}{3}{12}
                {2}{12}{23}  {1}{3}{13}
                {2}{13}{23}  {1}{3}{23}
                {3}{12}{13}  {2}{3}{12}
                {3}{12}{23}  {2}{3}{13}
                {3}{13}{23}  {2}{3}{23}

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Row sums are A014068, unlabeled version A000666.
Column k = 0 is A116508, covering version A367863.
The covering case is A368597.
The unlabeled version is A368836.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
A322661 counts labeled covering loop-graphs, connected A062740.
Cf. A057500, A079491, A339065, A368596, A368927.

Table[Length[Select[Subsets[Subsets[Range[n], {1,2}],{n}],Count[#,{_}]==k&]],{n,0,5},{k,0,n}]
T[n_,k_]:= Binomial[n,k]*Binomial[Binomial[n,2],n-k]; Table[T[n,k],{n,0,8},{k,0,n}]// Flatten (* Stefano Spezia, Jan 14 2024 *)

T(n,k) = binomial(n,k)*binomial(binomial(n,2),n-k) \\ Andrew Howroyd, Jan 14 2024

T(n,k) = binomial(n,k)*binomial(binomial(n,2),n-k).

A079492 Nearest integer to Sum_{k=0..n} binomial(n,k)/2^(k*(k-1)/2).

Original entry on oeis.org

1, 2, 4, 6, 9, 12, 17, 23, 31, 41, 52, 66, 82, 101, 124, 150, 180, 215, 254, 299, 351, 408, 473, 546, 628, 719, 820, 932, 1055, 1192, 1342, 1508, 1689, 1887, 2104, 2340, 2597, 2876, 3179, 3507, 3863, 4247, 4662, 5108, 5590, 6107, 6663, 7259, 7899, 8583, 9316, 10099

Offset: 0

N. J. A. Sloane, Jan 20 2003

nonn

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

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

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A079491.

[Round( (&+[Binomial(n,k)/2^(k*(k-1)/2): k in [0..n]]) ): n in [0..60]]; // G. C. Greubel, Jan 18 2019

f := n->add(binomial(n,k)/2^(k*(k-1)/2),k=0..n);

Table[Round[Sum[Binomial[n,k]/2^(k*(k-1)/2), {k,0,n}]], {n,0,60}] (* G. C. Greubel, Jan 18 2019 *)

vector(60, n, n--; round(sum(k=0,n, binomial(n,k)/2^(k*(k-1)/2)))) \\ G. C. Greubel, Jan 18 2019

[round(sum(binomial(n,k)/2^(k*(k-1)/2) for k in (0..30))) for n in (0..60)] # G. C. Greubel, Jan 18 2019

A277219 Triangle read by rows: T(n,k) is the number of independent sets of size k over all simple labeled graphs on n nodes, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 2, 4, 1, 8, 24, 12, 1, 64, 256, 192, 32, 1, 1024, 5120, 5120, 1280, 80, 1, 32768, 196608, 245760, 81920, 7680, 192, 1, 2097152, 14680064, 22020096, 9175040, 1146880, 43008, 448, 1, 268435456, 2147483648, 3758096384, 1879048192, 293601280, 14680064, 229376, 1024, 1

Offset: 0

Geoffrey Critzer, Oct 05 2016

Equivalently, T(n,k) is the number of size k cliques over all simple labeled graphs on n vertices.

			Triangle begins:
1;
1,     1;
2,     4,      1;
8,     24,     12,     1;
64,    256,    192,    32,    1;
1024,  5120,   5120,   1280,  80,   1;
32768, 196608, 245760, 81920, 7680, 192, 1;
...

Robert Israel, Table of n, a(n) for n = 0..3402 (rows 0 to 81, flattened)

Cf. A079491 (row sums), A006125 (column k=0), A095340 (column k=1), A095351 (column k = 2).

seq(seq(2^(n*(n-1)/2-k*(k-1)/2)*binomial(n,k),k=0..n),n=0..10); # Robert Israel, Oct 06 2016

Table[Table[2^Binomial[n, 2] Binomial[n, k]/2^Binomial[k, 2], {k, 0, n}], {n,0, 7}] // Grid

T(n,k) = 2^binomial(n,2)*binomial(n,k)/2^binomial(k,2).

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

Gus Wiseman, Feb 12 2024

nonn

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

			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}

Andrew Howroyd, Table of n, a(n) for n = 0..80

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.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]], Union@@#==Range[n]&&!MatchQ[#, {_,{x_},_,{y_},_,{x_,y_},_}]&]],{n,0,5}]

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

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

Gus Wiseman, Feb 12 2024

nonn

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

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.

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

First differences of A339832 (the non-covering version).

cp's OEIS Frontend

A165327 E.g.f: Sum_{n>=0} 2^(n(n-1)) * exp(2^n*x) * x^n/n!.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A180602 a(n) = (2^(n+1) - 1)^n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A368928 Triangle read by rows where T(n,k) is the number of labeled loop-graphs with n vertices and n edges, k of which are loops.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A079492 Nearest integer to Sum_{k=0..n} binomial(n,k)/2^(k*(k-1)/2).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

A277219 Triangle read by rows: T(n,k) is the number of independent sets of size k over all simple labeled graphs on n nodes, n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A165327 E.g.f: Sum_{n>=0} 2^(n(n-1)) * exp(2^nx) x^n/n!.