A047863 -id:A047863 - cp's OEIS frontend

A001830 Related to graded partially ordered sets.

1, 7, 61, 661, 8953, 152917, 3334921, 94354981, 3528929353, 177999003157, 12340001650921, 1194005625114661, 162936187792764073, 31536761103831315157, 8677703806537883683081, 3395880602480076153665701, 1889190751946097573211698313

Offset: 0

N. J. A. Sloane

nonn

Corresponds to the numbers c(7,n) in the Klarner paper. - Sean A. Irvine, Sep 24 2015

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

John Cerkan, Table of n, a(n) for n = 0..112
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19.
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
Index entries for sequences related to posets

Column k=7 of A361950.

Cf. A000684, A001827, A001828, A001829, A047863.

a(n) = Sum_{p+q+r+s+t+u+v=n} (n!/p!q!r!s!t!u!v!) 2^(pq+qr+rs+st+tu+uv) where (p,q,r,s,t,u,v) is any nonnegative composition of n. - Sean A. Irvine, Sep 24 2015

More terms from Sean A. Irvine, Sep 24 2015

A002027 Number of connected graphs on n labeled nodes, each node being colored with one of 2 colors, such that no edge joins nodes of the same color.

Original entry on oeis.org

1, 2, 2, 6, 38, 390, 6062, 134526, 4172198, 178449270, 10508108222, 853219059726, 95965963939958, 15015789392011590, 3282145108526132942, 1005193051984479922206, 432437051675617901246918, 261774334771663762228012950, 223306437526333657726283273822

Offset: 0

N. J. A. Sloane

nonn

a(n) is the number of connected labeled graphs with n 2-colored nodes where black nodes are only connected to white nodes and vice versa. - Geoffrey Critzer, Sep 05 2013

R. C. Read, personal communication.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50
R. C. Read, E. M. Wright, Colored graphs: A correction and extension, Canad. J. Math. 22 1970 594-596.

Column k=2 of A322279.
Essentially the same as A002031.
Cf. A002032.

nn=10;f[x_]:=Sum[Sum[Binomial[n,k]2^(k(n-k)),{k,0,n}]x^n/n!,{n,0,nn}];Range[0,nn]!CoefficientList[Series[Log[f[x]]+1,{x,0,nn}],x] (* Geoffrey Critzer, Sep 05 2013 *)

seq(n)={Vec(serlaplace(1 + log(serconvol(sum(j=0, n, x^j*2^binomial(j, 2)) + O(x*x^n), (sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n))^2))))} \\ Andrew Howroyd, Dec 03 2018

a(n) = m_n(2) using the functions defined in A002032. - Sean A. Irvine, May 29 2013
E.g.f.: log(A(x))+1 where A(x) is the e.g.f. for A047863. - Geoffrey Critzer, Sep 05 2013
Logarithmic transform of A047863. - Andrew Howroyd, Dec 03 2018

Corrected and extended by Sean A. Irvine, May 29 2013

Name clarified by Andrew Howroyd, Dec 03 2018

A058872 Number of 2-colored labeled graphs with n nodes.

Original entry on oeis.org

0, 2, 12, 80, 720, 9152, 165312, 4244480, 154732800, 8005686272, 587435092992, 61116916981760, 9011561121239040, 1882834327457349632, 557257804202631217152, 233610656002563147038720, 138681207656726645785559040, 116575238610106596799428165632

Offset: 1

N. J. A. Sloane, Jan 07 2001

A coloring of a simple graph is a choice of color for each graph vertex such that no two vertices sharing the same edge have the same color. A213441 counts those colorings of labeled graphs on n vertices that use exactly two colors. This sequence is 1/2 of A213441 (1/2 of column 2 of Table 1 in Read). - Peter Bala, Apr 11 2013

A047863 counts colorings of labeled graphs on n vertices that use two or fewer colors. - Peter Bala, Apr 11 2013

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, Table 1.5.1.
A. Mukhopadhyay, Lupanov decoding networks, in A. Mukhopadhyay, ed., Recent Developments in Switching Theory, Ac. Press, 1971, Chap. 3, see esp. p. 82 (number of shell functions).

R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.

A diagonal of A058843.

One half of A213441.

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

f[list_] := (Apply[Multinomial,list] * 2^((Total[list]^2 - Total[Table[list[[i]]^2, {i, 1, Length[list]}]])/2))/2!; Table[Total[Map[f, Select[Compositions[n,2], Count[#,0]==0&]]], {n, 1, 20}] (* Geoffrey Critzer, Oct 24 2011 *)

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

Original entry on oeis.org

1, 3, 11, 51, 311, 2583, 30011, 495771, 11740271, 399511023, 19531952051, 1369534859091, 137461591250951, 19708614005005383, 4029559971566918891, 1172950335844577723211, 485515762655939377001951, 285459356061242116657495263, 238215406681004045293498284131

Offset: 0

Paul D. Hanna, Jul 05 2014

nonn

			E.g.f.: A(x) = 1 + 3*x + 11*x^2/2! + 51*x^3/3! + 311*x^4/4! + 2583*x^5/5! +...
where
A(x) = exp(x)*(1 + 2*x + 6*x^2/2! + 26*x^3/3! + 162*x^4/4! + 1442*x^5/5! +...+ A047863(n)*x^n/n! +...).
ILLUSTRATION OF INITIAL TERMS:
a(1) = (1+2^0)^1 + (1+2^1)^0 = 3;
a(2) = (1+2^0)^2 + 2*(1+2^1)^1 + (1+2^2)^0 = 11;
a(3) = (1+2^0)^3 + 3*(1+2^1)^2 + 3*(1+2^2)^1 + (1+2^3)^0 = 51;
a(4) = (1+2^0)^4 + 4*(1+2^1)^3 + 6*(1+2^2)^2 + 4*(1+2^3)^1 + (1+2^4)^0 = 311; ...

Paul D. Hanna, Table of n, a(n) for n = 0..100

Cf. A047863, A244755, A243918.

Table[Sum[Binomial[n,k] * (1 + 2^k)^(n-k),{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, Jan 25 2015 *)

{a(n) = sum(k=0,n,binomial(n,k) * (1 + 2^k)^(n-k) )}
for(n=0,25,print1(a(n),", "))

/* E.g.f.: Sum_{n>=0} exp((1+2^n)*x)*x^n/n!: */
{a(n)=n!*polcoeff(sum(k=0, n, exp((1+2^k)*x +x*O(x^n))*x^k/k!), n)}
for(n=0,25,print1(a(n),", "))

/* O.g.f. Sum_{n>=0} x^n/(1 - (1+2^n)*x)^(n+1): */
{a(n)=polcoeff(sum(k=0, n, x^k/(1-(1+2^k)*x +x*O(x^n))^(k+1)), n)}
for(n=0,25,print1(a(n),", "))

E.g.f.: Sum_{n>=0} exp((1+2^n)*x) * x^n/n!.
O.g.f.: Sum_{n>=0} x^n/(1 - (1+2^n)*x)^(n+1).
a(n) ~ c * 2^(n^2/4 + n + 1/2) / sqrt(Pi*n), where c = JacobiTheta3(0, 1/2) = EllipticTheta[3, 0, 1/2] = 2.1289368272118771586... if n is even, and c = JacobiTheta2(0, 1/2) = EllipticTheta[2, 0, 1/2] = 2.12893125051302755859... if n is odd. - Vaclav Kotesovec, Jan 25 2015

A000685 Number of 3-colored labeled graphs on n nodes, divided by 3.

Original entry on oeis.org

1, 5, 41, 545, 11681, 402305, 22207361, 1961396225, 276825510401, 62368881977345, 22413909724518401, 12840603873823473665, 11720394922432296755201, 17037597932370037286600705

Offset: 1

N. J. A. Sloane

Sequence represents 1/3 of the number of 3-colored labeled graphs on n nodes. Indeed, on p. 413 of the Read paper, column 3 is 3, 15, 123, 1635, ...; or see A047863. - Emeric Deutsch, May 06 2004

R. C. Read, personal communication.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..50
S. R. Finch, Bipartite, k-colorable and k-colored graphs (3*A000685)
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
R. P. Stanley, Acyclic orientation of graphs Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
Eric Weisstein's World of Mathematics, k-Colorable Graph

Cf. A000683, A047863, A191371, A223887.

c[0]:=1: for n from 1 to 30 do c[n]:=sum(binomial(n,i)*2^(i*(n-i)),i=0..n) od: a:=n->(1/3)*sum(binomial(n,j)*2^(j*(n-j))*c[j],j=0..n): seq(a(n),n=1..19);

a[n_] := 1/3*Sum[ 2^((i-j)*j + i*(n-i))*Binomial[n, i]*Binomial[i, j], {i, 0, n}, {j, 0, i}]; Table[ a[n], {n, 1, 14}] (* Jean-François Alcover, Dec 07 2011, after Emeric Deutsch *)

a(n) = (1/3)Sum_{j=0..n} binomial(n, j)*2^(j(n-j))*c(j) where c(n) = Sum_{i=0..n} binomial(n, i)*2^(i(n-i)) = A047863(n). - Emeric Deutsch, May 06 2004
From Peter Bala, Apr 12 2013: (Start)
a(n) = 1/3*A191371(n). Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is 1/3*E(x)^3 - 1/3 = Sum_{n >= 1} a(n)*x^n/(n!*2^C(n,2)) = x + 5*x^2/(2!*2) + 41*x^3/(3!*2^3) + .... In general, E(x)^k, k = 1, 2, ..., is a generating function for labeled k-colored graphs (see Read). For examples see A047863 (k = 2), A191371 (k = 3) and A223887 (k = 4). (End)

More terms from Pab Ter (pabrlos(AT)yahoo.com) and Emeric Deutsch, May 05 2004

A221493 Number of tangled bicolored graphs on n labeled vertices.

Original entry on oeis.org

0, 0, 0, 0, 12, 120, 2460, 64680, 2323692, 111920760, 7272700860, 639739653960, 76764606923532, 12645557866982040, 2878366780307114460, 909775941009828296040, 401039212596034472197932, 247339947733328456032703160, 214013123181627427780427544060

Offset: 0

Mathieu Guay-Paquet, Jan 18 2013

A bicolored graph on n labeled vertices, k of which are black, and (n-k) of which are white, can be represented as a k X (n-k) matrix, where the (i,j) entry is 1 if the i-th black vertex is adjacent to the j-th white vertex, and 0 otherwise. Then, the graph is tangled if (1) the matrix does not have any rows or columns of all 0's or all 1's; and (2) it is not possible to permute the rows of the matrix and the columns of the matrix to obtain a matrix of the form
[ A | J ]
[---+---]
[ 0 | B ]
where the top right block J consists of all 1's, and the bottom left block 0 consists of all 0's.

			The only tangled bicolored graph on 4 vertices (up to isomorphism) consists of 2 black vertices, 2 white vertices, and 2 edges, with each black vertex joined to a different white vertex. Given 4 labels, there are 12 distinct ways of labeling the vertices, so a(4) = 1.

M. Guay-Paquet, A. H. Morales, E. Rowland, Structure and enumeration of (3+1)-free posets (extended abstract), arXiv:1212.5356 [math.CO], 2012.

Cf. A221492, A079145.

nmax = 19;
B[x_] = Sum[Exp[2^n x] x^n/n!, {n, 0, nmax}] + O[x]^nmax;
T[x_] = 2 Exp[-x] - 1 - 1/B[x] + O[x]^nmax;
CoefficientList[T[x], x] Range[0, nmax-1]! (* Jean-François Alcover, Aug 12 2018 *)

E.g.f.: T(x) = 2*e^(-x) - 1 - 1/B(x), where B(x) is the e.g.f. for A047863.

A222863 Strongly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

Original entry on oeis.org

1, 1, 3, 13, 111, 1381, 22383, 461413, 12163791, 420626821, 19880808303, 1337330559973, 130909732781391, 18649561895661061, 3830195104867879023, 1124247654215697637093, 469367653568553278229711, 278046313987470874905216901, 233462156432002170491075384943

Offset: 0

Joel B. Lewis, Mar 07 2013

nonn

Here "strongly graded" means that every maximal chain has the same length. Alternate terminology includes "graded" (e.g., in Stanley 2012) and "tiered" (as in A006860). A poset is said to be (3+1)-free if it does not contain four elements a, b, c, d such that a < b < c and d is incomparable to the other three.

R. P. Stanley, Enumerative Combinatorics, Volume 1. Cambridge University Press. 2nd edition, 2012. http://math.mit.edu/~rstan/ec/ec1/

J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, J. Combin. Theory Ser. A 120 (2013), no. 6, 1305-1327.

For strongly graded (3+1)-free posets by height, see A222864. For weakly graded (3+1)-free posets, see A222865. For all strongly graded posets, see A006860. For all (3+1)-free posets, see A079145.

m = maxExponent = 19;
Psi[x_] = Sum[E^(2^n*x)*x^n/n!, {n, 0, m}] + O[x]^m;
H[x_, y_] = 1+(2x^3 - 3x^2 + (x^3 - 4x^2 + 4x)y)/(2x^2 + x + (x^2-2x-1) y);
CoefficientList[H[E^x, Psi[x]] + O[x]^m, x] Range[0, m-1]! (* Jean-François Alcover, Dec 11 2018 *)

G.f.: H(e^x, Psi(x)) where H(x, y) = 1 + (2x^3 - 3x^2 + (x^3 - 4x^2 + 4x)y)/(2x^2 + x + (x^2 - 2x - 1)y) and Psi(x) is the g.f. for A047863.

A222865 Weakly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

Original entry on oeis.org

1, 1, 3, 19, 195, 2551, 41343, 826939, 20616795, 658486351, 28264985223, 1725711709459, 155998194920835, 21019550046219271, 4162663551546902223, 1192847436856343300779, 489879387071459457083115, 286844271719979335180726911, 238844671940165660117456403543

Offset: 0

Joel B. Lewis, Mar 07 2013

nonn

Here "weakly graded" means that there is a rank function rk from the vertices to the integers such that whenever x covers y we have rk(x) = rk(y) + 1. Alternate terminology includes "graded" and "ranked." A poset is said to be (3+1)-free if it does not contain four vertices a, b, c, d such that a < b < c and d is incomparable to the other three.

J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, To appear, J. Combinatorial Theory, Series A.

For weakly graded (3+1)-free posets by height, see A222866. For strongly graded (3+1)-free posets, see A222863. For all weakly graded posets, see A001833. For all (3+1)-free posets, see A079145.

m = maxExponent = 19;
Psi[x_] = Sum[E^(2^n x) x^n/n!, {n, 0, m}] + O[x]^m;
W[x_, y_] = (1-x)y/x + (2x^3 + (x^3 - 2x^2)y)/(2x^2 + x + (x^2-2x-1) y);
CoefficientList[W[E^x, Psi[x]] + O[x]^m, x] Range[0, m-1]! (* Jean-François Alcover, Dec 11 2018 *)

G.f. is W(e^x, Psi(x)) where W(x, y) = (1 - x)y/x + (2x^3 + (x^3 - 2x^2)y)/(2x^2 + x + (x^2 - 2x - 1)y) and Psi(x) is the GF for A047863.

A320287 a(n) = n! * [x^n] Sum_{k>=0} exp(n^kx)x^k/k!.

Original entry on oeis.org

1, 2, 6, 56, 2050, 318752, 252035714, 980755711616, 23647746367946754, 3088949241542073508352, 2940240000900000020000000002, 16218429504693724464229916894517248, 748528620411995327278028288988088683724802, 210422023062476527874650307058798916093350502080512

Offset: 0

Ilya Gutkovskiy, Oct 09 2018

nonn

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

Cf. A047863, A135079.

[(&+[Binomial(n,k)*n^(k*(n-k)):k in [0..n]]): n in [0..20]]; // G. C. Greubel, Nov 04 2018

Join[{1}, Table[n! SeriesCoefficient[Sum[Exp[n^k x] x^k/k!, {k, 0, n}], {x, 0, n}], {n, 13}]]
Join[{1}, Table[SeriesCoefficient[Sum[x^k/(1 - n^k x)^(k + 1), {k, 0, n}], {x, 0, n}], {n, 13}]]
Join[{1}, Table[Sum[Binomial[n, k] n^(k (n - k)), {k, 0, n}], {n, 13}]]

for(n=0,20, print1(sum(k=0,n, binomial(n,k)*n^(k*(n-k))), ", ")) \\ G. C. Greubel, Nov 04 2018

a(n) = [x^n] Sum_{k>=0} x^k/(1 - n^k*x)^(k+1).
a(n) = Sum_{k=0..n} binomial(n,k)*n^(k*(n-k)).
a(n) ~ 2^(n + 1/2) * n^(n^2/4 - 1/2) / sqrt(Pi) if n is even and a(n) ~ 2^(n + 3/2) * n^(n^2/4 - 3/4) / sqrt(Pi) if n is odd. - Vaclav Kotesovec, Jul 06 2022

A122801 Number of labeled bipartite graphs on 2n vertices having equal parts and no isolated vertices.

Original entry on oeis.org

1, 1, 21, 2650, 1452605, 3149738046, 26503552820514, 868081172737564500, 111606080497500509325405, 56762846667123360827351083510, 114847831981827229530824587617895286, 927685362544629192461621864598358779955500, 29976424929810726580224613882836823991388901138994

Offset: 0

Max Alekseyev, Sep 11 2006

nonn

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

Cf. A122802, A048291, A052332, A001831, A002031, A047863, A001700.

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

For n>0, a(n) = A001700(n-1) * A048291(n) = A052332(2n) - A122802(2n).

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

cp's OEIS Frontend

A001830 Related to graded partially ordered sets.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A002027 Number of connected graphs on n labeled nodes, each node being colored with one of 2 colors, such that no edge joins nodes of the same color.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A058872 Number of 2-colored labeled graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A000685 Number of 3-colored labeled graphs on n nodes, divided by 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A221493 Number of tangled bicolored graphs on n labeled vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A222863 Strongly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A320287 a(n) = n! * [x^n] Sum_{k>=0} exp(n^kx)x^k/k!.