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.

Previous Showing 11-14 of 14 results.

A058873 Number of 3-colored labeled graphs with n nodes.

Original entry on oeis.org

0, 0, 8, 192, 5120, 192000, 10938368, 976453632, 138258022400, 31176435302400, 11206367427166208, 6420240819994755072, 5860188449655027138560, 8518797083350691185950720, 19715227484913090464294371328, 72618853907514273117149186752512
Offset: 1

Views

Author

N. J. A. Sloane, Jan 07 2001

Keywords

Comments

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. A213442 counts those colorings of labeled graphs on n vertices that use exactly three colors. In this sequence, graph colorings that differ only by a permutation of the three colors are considered to be the same. Hence a(n) = 1/3!*A213442(n). [Peter Bala, Apr 12 2013]

References

  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, Table 1.5.1.

Links

Crossrefs

A diagonal of A058843. A213442.

Programs

  • Maple
    E:= Sum(x^n/(n!*2^(n*(n-1)/2)),n=1..infinity):
G:= 1/6*E^3:
S:= series(G,x,21):
seq(coeff(S,x,n)*n!*2^(n*(n-1)/2),n=1..20); # Robert Israel, Aug 01 2018
  • Mathematica
    f[list_] := (Apply[Multinomial, list] * 2^((Total[list]^2-Total[Table[list[[i]]^2, {i, 1, Length[list]}]])/2))/3!; Table[Total[Map[f, Select[Compositions[n, 3], Count[#, 0]==0&]]], {n, 1, 20}] (* Geoffrey Critzer, Oct 24 2011 *)
  • PARI
    N=66;  x='x+O('x^N);
E=sum(n=0, N, x^n/(n!*2^binomial(n,2)) );
tgf=(E-1)^3/6;  v=concat([0,0], Vec(tgf));
v=vector(#v, n, v[n] * n! * 2^(n*(n-1)/2) )
/* Joerg Arndt, Apr 14 2013 */

Formula

Let E(x) = sum {n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + x^4/(4!*2^6) + .... Then a generating function is 1/6*(E(x) - 1)^3 = 8*x^3/(3!*2^3) + 192*x^4/(4!*2^6) + 5120*x^5/(5!*2^10) + ... (see Read). - Peter Bala, Apr 13 2013

A058874 Number of 4-colored labeled graphs with n nodes.

Original entry on oeis.org

0, 0, 0, 64, 5120, 450560, 56197120, 10877927424, 3407830056960, 1765179884830720, 1528596578057584640, 2225354662890778394624, 5460264388115266042593280, 22602991882128566753395998720, 157891665026904821204431467970560
Offset: 1

Views

Author

N. J. A. Sloane, Jan 07 2001

Keywords

References

  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, Table 1.5.1.

Links

Crossrefs

A diagonal of A058843.
Equals 64 * A006202.

Programs

  • Mathematica
    m = 16;
CoefficientList[Sum[x^j*j!*2^Binomial[j, 2], {j, 1, m}] + O[x]^n, x]* CoefficientList[(Sum[x^j/(j!*2^Binomial[j, 2]), {j, 1, n}] + O[x]^m)^4/24 + O[x]^m, x] // Rest (* Jean-François Alcover, Sep 06 2019, from PARI *)
  • PARI
    seq(n)={Vec(serconvol(sum(j=1, n, x^j*j!*2^binomial(j,2)) + O(x*x^n), (sum(j=1, n, x^j/(j!*2^binomial(j,2))) + O(x*x^n))^4)/24, -n)} \\ Andrew Howroyd, Nov 30 2018

A219765 Triangle of coefficients of a polynomial sequence related to the coloring of labeled graphs.

Original entry on oeis.org

1, 0, 1, 0, -1, 2, 0, 5, -12, 8, 0, -79, 208, -192, 64, 0, 3377, -9520, 10240, -5120, 1024, 0, -362431, 1079744, -1282560, 778240, -245760, 32768, 0, 93473345, -291615296, 372893696, -255754240, 100925440, -22020096, 2097152, 0, -56272471039, 182582658048, -247557029888, 185511968768, -84263567360, 23488102400, -3758096384, 268435456
Offset: 0

Views

Author

Peter Bala, Apr 16 2013

Keywords

Comments

A simple graph G is a k-colorable graph if it is possible to assign one of k' <= k colors to each vertex of G so that no two adjacent vertices receive the same color. Such an assignment of colors is called a k-coloring function for the graph. The chromatic polynomial P(G,k) of a simple graph G gives the number of different k-colorings functions of the graph as a function of k. P(G,k) is a polynomial function of k.
The row polynomials R(n,x) of this triangle are defined to be the sum of the chromatic polynomials of all labeled simple graphs on n vertices: R(n,x) = sum {labeled graphs G on n nodes} P(G,x). An example is given below.

Examples

			Triangle begins:
  n\k.|..0.....1......2.......3......4.......5
  = = = = = = = = = = = = = = = = = = = = = = =
  .0..|..1
  .1..|..0.....1
  .2..|..0....-1......2
  .3..|..0.....5....-12.......8
  .4..|..0...-79....208....-192.....64
  .5..|..0..3377..-9520...10240..-5120....1024
  ...
Row 3 = [5, -12, 8]: There are 4 unlabeled graphs on 3 vertices, namely
(a)  o    o    o    (b)  o    o----o    (c)  o----o----o
(d)   0
     / \
    0---0
with chromatic polynomials x^3, x^2*(x-1), x*(x-1)^2 and (x-1)^3 - (x-1), respectively. Allowing for labeling, there is 1 labeled graph of type (a), 3 labeled graphs of type (b), 3 labeled graphs of type (c) and 1 labeled graph of type (d). Thus the sum of the chromatic polynomials over all labeled graphs on 3 nodes is x^3 + 3*x^2*(x-1) + 3*x*(x-1)^2  + (x-1)^3 - (x-1) = 5*x - 12*x^2 + 8*x^3.
Row 3 of A058843 is [1,12,8]. Thus R(3,x) = x + 12*x*(x-1) + 8*x*(x-1)*(x-2) = 5*x - 12*x^2 + 8*x^3.

Links

Crossrefs

Cf. A003024 (alt. row sums), A006125 (main diagonal), A095351 (main subdiagonal), A134531 (column 1), A058843, A322280.

Programs

  • Maple
    R:= proc(n) option remember; `if`(n=0, 1, expand(x*add(
      binomial(n-1, k)*2^(k*(n-k))*subs(x=x-1, R(k)), k=0..n-1)))
    end:
T:= n-> (p-> seq(coeff(p,x,i), i=0..degree(p)))(R(n)):
seq(T(n), n=0..10);  # Alois P. Heinz, May 16 2024
  • Mathematica
    r[0] = 1; r[1] = x; r[n_] := r[n] = x*Sum[ Binomial[n-1, k]*2^(k*(n-k))*(r[k] /. x -> x-1), {k, 0, n-1}]; row[n_] := CoefficientList[ r[n], x]; Table[ row[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, Apr 17 2013 *)

Formula

Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + x^4/(4!*2^6) + .... Then a generating function for the triangle is E(z)^x = Sum_{n >= 0} R(n,x)*z^n/(n!*2^C(n,2)) = 1 + x*z + (-x + 2*x^2)*z^2/(2!*2) + (5*x - 12*x^2 + 8*x^3)*z^3/(3!*2^3) + ....
The row polynomials satisfy the recurrence equation: R(0,x) = 1 and
R(n+1,x) = x*Sum_{k = 0..n} binomial(n,k)*2^(k*(n+1-k))*R(k,x-1).
In terms of the basis of falling factorial polynomials we have, for n >= 1, R(n,x) = Sum_{k = 1..n} A058843(n,k)*x*(x-1)*...*(x-k+1).
The polynomials R(n,x)/2^comb(n,2) form a sequence of binomial type (see Stanley). Setting D = d/dx, the associated delta operator begins D + D^2/(2!*2) + D^3/(3!*2^3) - D^4/(4!*2^4) + 23*D^5/(5!*2^5) + 559*D^6/(6!*2^6) - ... obtained by series reversion of the formal series D - D^2/(2!*2) + 5*D^3/(3!*2^3) - 79*D^4/(4!*2^4) + 3377*D^5/(5!*2^5) - ... coming from column 1 of the triangle.
Alternating row sums A003024. Column 1 = A134531. Main diagonal A006125. Main subdiagonal (-1)*A095351.
The row polynomials evaluated at k is A322280(n,k). - Geoffrey Critzer, Mar 02 2024
Let k>=1 and let D be a directed acyclic graph with vertices labeled on [n]. Then (-1)^n*R(n,-k) is the number of maps C:[n]->[k] such that for all vertices i,j in [n], if i is directed to j in D then C(i)>=C(j). Cf A003024 (k=1), A339934 (k=2). - Geoffrey Critzer, May 15 2024

A371633 Number of ways to choose a simple labeled graph on [n], then partition the vertex set into independent sets, then choose a vertex from each independent set.

Original entry on oeis.org

1, 1, 4, 35, 740, 34629, 3581894, 802937479, 386655984648, 396751196145673, 862046936883049482, 3946154005780155709451, 37896676657907955726032908, 760791471852690599411320471565, 31830237745009483676211065390546958, 2768049771339996987073597682850993569807
Offset: 0

Views

Author

Geoffrey Critzer, Jun 06 2024

Keywords

Comments

An independent set is a set of vertices in a graph, no two of which are adjacent.

Links

Crossrefs

Cf. A000248, A240936, A058843, A011266.

Programs

  • Mathematica
    nn = 14; B[n_] := n! 2^Binomial[n, 2];ggf[egf_] := Normal[Series[egf, {x, 0, nn}]] /.Table[x^i -> x^i/2^Binomial[i, 2], {i, 0, nn}];Table[B[n], {n, 0, nn}] CoefficientList[Series[Exp[ggf[x Exp[x]]], {x, 0, nn}], x]

Formula

Sum_{n>=0} a(n)*x^n/A011266(n) = exp(f(x)) where f(x) = Sum_{n>=1} n*x^n/A011266(n).
Previous Showing 11-14 of 14 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.