A047863 -id:A047863 - cp's OEIS frontend

A122802 Number of labeled bipartite graphs on n vertices with no isolated vertices.

1, 0, 1, 6, 29, 510, 5032, 161406, 3294405, 194342910, 7934652356, 881008805886, 71275547085536, 15178191426486270, 2434250064518832302, 1008694542117649154046, 321680912414994434144165, 262063364967549826752315390, 166681427053102507699172431372

Offset: 0

Max Alekseyev, Sep 11 2006

nonn

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

Cf. A122801, A052332, A001831, A002031, A047863.

a(n)={sum(k=0, n, binomial(n, k)*(2^k-2)^(n-k)) - if(n%2==0&&n>0, binomial(n-1, n/2)*sum(k=0, n/2, binomial(n/2, k)*(-1)^k*(2^(n/2-k)-1)^(n/2)))} \\ Andrew Howroyd, Nov 07 2019

a(2n+1) = A052332(2n+1); a(2n) = A052332(2n) - A122801(n) for n > 0.

Terms a(17) and beyond from Andrew Howroyd, Nov 07 2019

A172388 a(n) = Sum_{k=0..n} (-1)^kC(n,k)2^(k*(n-k)).

Original entry on oeis.org

1, 0, -2, 0, 34, 0, -2942, 0, 1144834, 0, -1906714622, 0, 13264071114754, 0, -380188784001777662, 0, 44530311225683389448194, 0, -21199108233888497863938801662, 0, 40869840581497696551494454452682754

Offset: 0

Paul D. Hanna, Feb 03 2010

sign

			O.g.f.: A(x) = 1 - 2*x^2 + 34*x^4 - 2942*x^6 + 1144834*x^8 +...
A(x) = 1/(1+x) + x/(1+2*x)^2 + x^2/(1+2^2*x)^3 + x^3/(1+2^3*x)^4 +...+ x^n/(1+2^n*x)^(n+1) +...
E.g.f.: E(x) = 1 - 2*x^2/2! + 34*x^4/4! - 2942*x^6/6! + 1144834*x^8/8! +...
E(x) = exp(-x) + exp(-2*x)*x + exp(-2^2*x)*x^2/2! + exp(-2^3*x)*x^3/3! +...+ exp(-2^n*x)*x^n/n! +...

Cf. variants: A172389, A047863.

{a(n)=sum(k=0,n,(-1)^k*binomial(n,k)*2^(k*(n-k)))}

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

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

O.g.f.: A(x) = Sum_{n>=0} x^n/(1+2^n*x)^(n+1).

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

A179534 Number of labeled split graphs on n vertices.

Original entry on oeis.org

1, 2, 8, 58, 632, 9654, 202484, 5843954, 233064944, 12916716526, 998745087980, 108135391731690, 16434082400952296, 3513344943520006118, 1058030578581541945316, 449389062270642095128546, 269419653009366144571801568, 228157953744571034350576205790

Offset: 1

Vladislav Bina, Jul 18 2010

A split graph is a graph whose vertices can be partitioned into a clique and an independent set. - Justin M. Troyka, Oct 28 2018

V. Bina, Enumeration of Labeled Split Graphs and Counts of Important Superclasses. In Adacher L., Flamini, M., Leo, G., Nicosia, G., Pacifici, A., Picialli, V. (Eds.). CTW 2011, Villa Mondragone, Frascati, pp. 72-75 (2011).

Andrew Howroyd, Table of n, a(n) for n = 1..100
E. A. Bender, L. B. Richmond, and N. C. Wormald, Almost all chordal graphs split, J. Austral. Math. Soc. (Series A), 38 (1985), 214-221.
V. Bina, Multidimensional probability distributions: Structure and learning, PHD Thesis. Fac. of Management, University of Economics in Prague (2011).
Venkatesan Guruswami, Enumerative aspects of certain subclasses of perfect graphs, Discrete Mathematics 205 (1999), 97-117.
J. M. Troyka, Split graphs: combinatorial species and asymptotics, arXiv:1803.07248 [math.CO], 2018-2019.
J. M. Troyka, Split graphs: combinatorial species and asymptotics, Electron. J. Combin., 26 (2019), #P2.42.

Cf. A047863, A048194, A058862, A006125.

A179534 := proc(n) local a,k; a := 1 ; for k from 2 to n do a := a+binomial(n,k)*( (2^k-1)^(n-k) -add(j*k*binomial(n-k,j)*(2^(k-1)-1)^(n-k-j)/(j+1), j=1..n-k) ) end do: a ; end proc: # R. J. Mathar, Jun 21 2011

a[n_] := 1 + Sum[Binomial[n,k]*((2^k-1)^(n-k) - Sum[j*k*Binomial[n-k,j]*(2^(k-1)-1)^(n-k-j)/(j+1), {j,1,n-k}]), {k,2, n}]; Array[a, 20] (* Stefano Spezia, Oct 29 2018 *)

b(n) = {sum(k=0, n, binomial(n, k)*2^(k*(n-k)))} \\ A047863(n)
a(n) = b(n) - n*b(n-1) \\ Andrew Howroyd, Jun 06 2021

a(n) = 1 + Sum_{k=2..n} binomial(n,k)*( (2^k-1)^(n-k) - Sum_{j=1..n-k} j*k*binomial(n-k,j)*(2^(k-1)-1)^(n-k-j) /(j+1) ).
From Justin M. Troyka, Oct 28 2018: (Start)
a(n) = [ Sum_{k=0..n} binomial(n,k) 2^(k(n-k)) ] - [ n Sum_{k=0..n-1} binomial(n-1,k)*2^(k(n-k-1)) ] (see the Troyka link, Cor. 3.4).
a(n) = A047863(n) - n*A047863(n-1) (see the Troyka link, Cor. 3.4).
a(n) ~ A047863(n) (see Bender, Richmond, and Wormald, Cor. 1). (End)

a(12)-a(16) corrected and terms a(17) and beyond from Andrew Howroyd, Jun 06 2021

A228890 Triangular array read by rows. T(n,k) is the number of 2-colored labeled graphs on n nodes with exactly k edges; n >= 0, 0 <= k <= A002620(n).

Original entry on oeis.org

1, 2, 4, 2, 8, 12, 6, 16, 48, 60, 32, 6, 32, 160, 360, 440, 310, 120, 20, 64, 480, 1680, 3480, 4680, 4212, 2520, 960, 210, 20, 128, 1344, 6720, 20720, 43680, 66108, 73514, 60480, 36540, 15820, 4662, 840, 70, 256, 3584, 24192, 103040, 308560, 686784, 1172976, 1565888, 1649340, 1373680, 900592, 459312, 178416, 50960, 10080, 1232, 70

Offset: 0

Geoffrey Critzer, Sep 07 2013

A 2-colored labeled graph is a simple labeled graph in which each vertex is painted black or white and black vertices are only connected to white vertices and vice versa. [corrected by Geoffrey Critzer, Mar 27 2023]

			Triangle begins:
   1;
   2;
   4,   2;
   8,  12,    6;
  16,  48,   60,   32,    6;
  32, 160,  360,  440,  310,  120,   20;
  64, 480, 1680, 3480, 4680, 4212, 2520, 960, 210, 20;
  ...

Row sums are A047863.
Column k=0 gives A000079.
Cf. A002620.

nn=6;f[x_,y_]:=Sum[Exp[x (1+y)^n]x^n/n!,{n,0,nn}];Map[Select[#,#>0&]&,Range[0,nn]!CoefficientList[Series[f[x,y],{x,0,nn}],{x,y}]]//Grid

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

A381058 Irregular triangular array read by rows. Let S_n be the set of labeled graphs G on [n] with 2-colored nodes where black nodes are only connected to white nodes and vice versa. Orient the edges in each such graph G from black to white. T(n,k) is the number of graphs in S_n containing exactly k descents, n>=0, 0<=k<=A002620(n).

Original entry on oeis.org

1, 2, 5, 1, 16, 8, 2, 67, 56, 30, 8, 1, 374, 436, 358, 188, 68, 16, 2, 2825, 4143, 4508, 3460, 2032, 924, 320, 80, 13, 1, 29212, 50460, 66976, 66092, 52412, 34280, 18630, 8376, 3072, 892, 194, 28, 2, 417199, 811790, 1246486, 1471358, 1436404, 1195166, 859650, 537750, 292880, 138280, 56048, 19168, 5382, 1188, 192, 20, 1

Offset: 0

Geoffrey Critzer, Feb 12 2025

A descent in a labeled directed graph is an edge s->t such that s>t.

T(n,0) = A006116(n).

			    1;
    2;
    5,    1;
   16,    8,    2;
   67,   56,   30,    8,    1;
  374,  436,  358,  188,   68,  16,   2;
 2825, 4143, 4508, 3460, 2032, 924, 320, 80, 13, 1;
 ...

Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020.

Cf. A228890, A047863 (row sums), A006116, A111636, A381102, A381192.

nn = 7; B[n_] := FunctionExpand[QFactorial[n, (1 + u y)/(1 + y)]] (1+y)^Binomial[n,2]; e[z_] := Sum[z^n/B[n], {n, 0, nn}];Map[CoefficientList[#, u] &,  Table[B[n], {n, 0, nn}] CoefficientList[Series[e[z]^2, {z, 0, nn}],z] /. y -> 1] // Grid

A172389 a(n) = Sum_{k=0..n} C(n,k)3^(k(n-k))/2^n.

Original entry on oeis.org

1, 1, 2, 7, 44, 481, 9272, 310087, 18164624, 1843946881, 326808099872, 100310221406407, 53656068398769344, 49686835289802328801, 80090696216400251499392, 223445962168511596412895367

Offset: 0

Paul D. Hanna, Feb 03 2010

nonn

			O.g.f.: A(x) = 1 + x + 2*x^2 + 7*x^3 + 44*x^4 + 481*x^5 + 9272*x^6 +...
A(x) = 2/(2-x) + 2*x/(2-3*x)^2 + 2*x^2/(2-3^2*x)^3 + 2*x^3/(2-3^3*x)^4 +...+ 2*x^n/(2-3^n*x)^(n+1) +...
E.g.f.: E(x) = 1 + x + 2*x^2/2! + 7*x^3/3! + 44*x^4/4! + 481*x^5/5! +...
E(x) = exp(x/2) + exp(3*x/2)*x/2 + exp(3^2*x/2)*(x/2)^2/2! + exp(3^3*x/2)*(x/2)^3/3! +...+ exp(3^n*x/2)*(x/2)^n/n! +...

Cf. variants: A135079, A047863.

{a(n)=sum(k=0,n,binomial(n,k)*3^(k*(n-k)))/2^n}

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

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

O.g.f.: A(x) = Sum_{n>=0} 2*x^n/(2 - 3^n*x)^(n+1).
E.g.f.: E(x) = Sum_{n>=0} exp(3^n*x/2)*(x/2)^n/n!.
a(n) = A135079(n)/2^n.

A228859 Triangular array read by rows. T(n,k) is the number of labeled bipartite graphs on n nodes having exactly k connected components; n>=1, 1<=k<=n.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 19, 15, 6, 1, 195, 125, 45, 10, 1, 3031, 1545, 480, 105, 15, 1, 67263, 27307, 7035, 1400, 210, 21, 1, 2086099, 668367, 140098, 24045, 3430, 378, 28, 1, 89224635, 22427001, 3746925, 536214, 68355, 7434, 630, 36, 1

Offset: 1

Geoffrey Critzer, Sep 05 2013

The Bell transform of A001832(n+1) (without column 0). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 21 2016

			1,
1, 1,
3, 3, 1,
19, 15, 6, 1,
195, 125, 45, 10, 1,
3031, 1545, 480, 105, 15, 1,

Row sums are A047864.
Column 1 is A001832.
Cf. A047863.

nn=9;f[x_]:=Sum[Sum[Binomial[n,k]2^(k(n-k)),{k,0,n}]x^n/n!,{n,0,nn}];Map[Select[#,#>0&]&,Drop[Range[0,nn]!CoefficientList[Series[Exp[y Log[f[x]]/2],{x,0,nn}],{x,y}],1]]//Grid

# uses[bell_matrix from A264428, A001832]
# Adds 1,0,0,0,... as column 0 to the triangle.
bell_matrix(lambda n: A001832(n+1), 8) # Peter Luschny, Jan 21 2016

E.g.f.: sqrt(A(x)^y) where A(x) is the e.g.f. for A047863.

Sum_{k=1..n} T(n,k)*2^k = A047863(n).

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

Original entry on oeis.org

1, 1, 2, 13, 98, 721, 7682, 165313, 4816898, 154732801, 7052328962, 587435092993, 67748952539138, 9011561121239041, 1692739935456460802, 557257804202631217153, 255875811615404841762818, 138681207656726645785559041, 105975684493162347867458764802

Offset: 0

Paul D. Hanna, Jan 12 2021

nonn

a(n) = A047863(n) - A340452(n) for n >= 0, in which A047863 gives the number of labeled graphs with 2-colored nodes when connected only to nodes of a different color.

			E.g.f.: A(x) = 1 + x + 2*x^2/2! + 13*x^3/3! + 98*x^4/4! + 721*x^5/5! + 7682*x^6/6! + 165313*x^7/7! + 4816898*x^8/8! + 154732801*x^9/9! + ...
where
A(x) = cosh(x) + x*cosh(2*x) + x^2*cosh(2^2*x)/2! + x^3*cosh(2^3*x)/3! + x^4*cosh(2^4*x)/4! + x^5*cosh(2^5*x)/5! + ...
also
A(x) = exp(x) + x^2*exp(2^2*x)/2! + x^4*exp(2^4*x)/4! + x^6*exp(2^6*x)/6! + x^8*exp(2^8*x)/8! + ...

Cf. A047863, A172388, A340452.

{a(n) = my(A = sum(m=0, n, x^m/m! * cosh(2^m*x +x*O(x^n)) )); n!*polcoeff(A, n)}
for(n=0, 20, print1(a(n), ", "))

{a(n) = my(A = sum(m=0, n\2, x^(2*m)/(2*m)! * exp(2^(2*m)*x +x*O(x^n)) )); n!*polcoeff(A, n)}
for(n=0, 20, print1(a(n), ", "))

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

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

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

Original entry on oeis.org

1, 4, 13, 64, 721, 10624, 165313, 3672064, 154732801, 8959043584, 587435092993, 54484881424384, 9011561121239041, 2072928719458238464, 557257804202631217153, 211345500389721452314624, 138681207656726645785559041, 127174792727050845731397566464

Offset: 1

Paul D. Hanna, Jan 12 2021

nonn

a(n) = A047863(n) - A340451(n) for n >= 0, in which A047863 gives the number of labeled graphs with 2-colored nodes when connected only to nodes of a different color.

			E.g.f.: A(x) = x + 4*x^2/2! + 13*x^3/3! + 64*x^4/4! + 721*x^5/5! + 10624*x^6/6! + 165313*x^7/7! + 3672064*x^8/8! + 154732801*x^9/9! + ...
where
A(x) = sinh(x) + x*sinh(2*x) + x^2*sinh(2^2*x)/2! + x^3*sinh(2^3*x)/3! + x^4*sinh(2^4*x)/4! + x^5*sinh(2^5*x)/5! + ...
also
A(x) = x*exp(2*x) + x^3*exp(2^3*x)/3! + x^5*exp(2^5*x)/5! + x^7*exp(2^7*x)/7! + x^9*exp(2^9*x)/9! + ...

Cf. A047863, A172388, A340451.

{a(n) = my(A = sum(m=0, n, x^m/m! * sinh(2^m*x +x*O(x^n)) )); n!*polcoeff(A, n)}
for(n=1, 20, print1(a(n), ", "))

{a(n) = my(A = sum(m=0, n\2+1, x^(2*m+1)/(2*m+1)! * exp(2^(2*m+1)*x +x*O(x^n)) )); n!*polcoeff(A, n)}
for(n=1, 20, print1(a(n), ", "))

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

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

A355395 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where T(n,k) = Sum_{j=0..n} k^(j(n-j)) binomial(n,j).

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 1, 2, 4, 2, 1, 2, 6, 8, 2, 1, 2, 8, 26, 16, 2, 1, 2, 10, 56, 162, 32, 2, 1, 2, 12, 98, 704, 1442, 64, 2, 1, 2, 14, 152, 2050, 15392, 18306, 128, 2, 1, 2, 16, 218, 4752, 84482, 593408, 330626, 256, 2, 1, 2, 18, 296, 9506, 318752, 7221250, 39691136, 8488962, 512, 2

Offset: 0

Seiichi Manyama, Jul 02 2022

The Stanley reference below describes a family of binomial posets whose elements are two colored graphs with vertices labeled on [n] and with edges labeled on [k-1]. T(n,k) is the number of elements in an n-interval of such a binomial poset. - Geoffrey Critzer, Aug 21 2023

			Square array begins:
  1,  1,    1,     1,     1,      1, ...
  2,  2,    2,     2,     2,      2, ...
  2,  4,    6,     8,    10,     12, ...
  2,  8,   26,    56,    98,    152, ...
  2, 16,  162,   704,  2050,   4752, ...
  2, 32, 1442, 15392, 84482, 318752, ...

R. P. Stanley, Enumerative Combinatorics, Volume 1, Second Edition, Example 3.18.3(e), page 323.

Columns k=0..4 give A040000, A000079, A047863, A135079, A355440.
Main diagonal gives A320287.
Cf. A009999.

T(n, k) = sum(j=0, n, k^(j*(n-j))*binomial(n, j));

E.g.f. of column k: Sum_{j>=0} exp(k^j * x) * x^j/j!.
G.f. of column k: Sum_{j>=0} x^j/(1 - k^j * x)^(j+1).
For k>=1, E(x)^2 = Sum_{n>=0} T(n,k)*x^n/B_k(n) where B_k(n) = n!*k^binomial(n,2) and E(x) = Sum_{n>=0} x^n/b_k(n). - Geoffrey Critzer, Aug 21 2023

cp's OEIS Frontend

A122802 Number of labeled bipartite graphs on n vertices with no isolated vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A172388 a(n) = Sum_{k=0..n} (-1)^k*C(n,k)*2^(k*(n-k)).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

PARI

PARI

Formula

A179534 Number of labeled split graphs on n vertices.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A228890 Triangular array read by rows. T(n,k) is the number of 2-colored labeled graphs on n nodes with exactly k edges; n >= 0, 0 <= k <= A002620(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A172389 a(n) = Sum_{k=0..n} C(n,k)*3^(k*(n-k))/2^n.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

PARI

PARI

Formula

A228859 Triangular array read by rows. T(n,k) is the number of labeled bipartite graphs on n nodes having exactly k connected components; n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Sage

Formula

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

Views

Author

A172388 a(n) = Sum_{k=0..n} (-1)^kC(n,k)2^(k*(n-k)).

A172389 a(n) = Sum_{k=0..n} C(n,k)3^(k(n-k))/2^n.

A355395 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where T(n,k) = Sum_{j=0..n} k^(j(n-j)) binomial(n,j).