A095351 -id:A095351 - cp's OEIS frontend

A103904 a(n) = n(n-1)/2 2^(n*(n-1)/2).

0, 2, 24, 384, 10240, 491520, 44040192, 7516192768, 2473901162496, 1583296743997440, 1981583836043018240, 4869940435459321626624, 23574053482485268906770432, 225305087149939210031640608768

Offset: 1

Ralf Stephan, Feb 21 2005

nonn

a(n) is the number of birooted graphs on n labeled nodes. - Andrew Howroyd, Nov 23 2020

Old (incorrect) name was: "Number of perfect matchings of an n X (n+1) Aztec rectangle with the third vertex in the topmost row removed". See Mathematics Stack Exchange for the discussion. - Andrey Zabolotskiy, Jun 05 2022

M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97, doi:10.1006/jcta.1996.2725.
N. Elkies, G. Kuperberg, M. Larsen and J. Propp, Alternating sign matrices and domino tilings, Journal of Algebraic Combinatorics 1 (1992), 111-132 (Part I), 219-234 (Part II); arXiv:math/9201305 [math.CO], 1992.
H. Helfgott and I. M. Gessel, Enumeration of tilings of diamonds and hexagons with defects, arXiv:math/9810143 [math.CO], 1998.
C. Krattenthaler, Schur function identities and the number of perfect matchings of Aztec holey rectangles, arXiv:math/9712204 [math.CO], 1997.
Mathematics Stack Exchange, Mistake in OEIS A103904?, 2021.

Cf. A000217, A006125, A038094, A095340, A095351, A134401, A036289, A303831.

a(n)={binomial(n,2)*2^binomial(n,2)} \\ Andrew Howroyd, Nov 23 2020

a(n) = A000217(n-1) * A006125(n).
a(n) = 2*A095351(n). - Andrew Howroyd, Nov 23 2020
a(n) = A036289(n*(n-1)/2). - Michael Somos, Feb 28 2021

Name replaced by a formula, a(1) changed from 1 to 0, and entry edited by Andrey Zabolotskiy, Jun 05 2022

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

Peter Bala, Apr 16 2013

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.

			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.

Alois P. Heinz, Rows n = 0..77, flattened
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. P. Stanley, Exponential structures
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.
Wikipedia, Graph coloring

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

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

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 *)

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

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).

A094602 Total number of edges in all connected unlabeled graphs on n nodes.

Original entry on oeis.org

0, 1, 5, 25, 130, 951, 9552, 160220, 4756703, 264964172, 27746801125, 5419696866001, 1964101824992259, 1319988856541150115, 1648566523004692022634, 3838409698542815296758222, 16719797018733808721401666187, 136732968429033400292302529059213

Offset: 1

Vladeta Jovovic, Jun 06 2004

nonn

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

Cf. A046751, A054923, A054924, A086314, A095351.

\\ See A054923 for G, InvEulerMT.
a(n)={subst(deriv(InvEulerMT(vector(n, k, G(k,y)))[n]), y, 1)} \\ Andrew Howroyd, Feb 01 2020

a(n) = Sum_{k=1..binomial(n,2)} k*A054924(n, k). - Andrew Howroyd, Feb 01 2020

Terms a(17) and beyond from Andrew Howroyd, Feb 01 2020

A094594 Total number of edges in all connected labeled graphs on n nodes.

Original entry on oeis.org

0, 1, 9, 144, 4140, 214200, 20264832, 3580049088, 1202974894656, 779257681804800, 982078160760512640, 2423077679970846226944, 11755368773275419420291072, 112487517660848696830655493120

Offset: 1

Vladeta Jovovic, Jun 06 2004

a[1]:=0: for n from 1 to 16 do a[n]:= binomial(n,2)*2^(binomial(n,2)-1)-sum(binomial(n,k)*2^binomial(n-k,2)*a[k],k=1..n-1) od: seq(a[n],n=1..16); # Emeric Deutsch, Dec 18 2004

nn=14;f[x_,y_]:=Sum[(1+y)^Binomial[n,2]x^n/n!,{n,0,nn}];Drop[Range[0,nn]!CoefficientList[Series[D[Log[f[x,y]],y]/.y->1,{x,0,nn}],x],1] (* Geoffrey Critzer, Sep 04 2013 *)

E.g.f.: A(x)/B(x), where A(x) is e.g.f. of A095351 and B(x) is e.g.f. of A006125. recurrence: a(n) = binomial(n, 2)*2^(binomial(n, 2) - 1) - Sum_{k=1..n-1} binomial(n, k)*2^binomial(n-k, 2)*a(k).

a(n) = Sum_{k=0..binomial(n,2)} A062734(n,k)*k. - Geoffrey Critzer, Sep 04 2013

More terms from Emeric Deutsch, Dec 18 2004

A285529 Triangle read by rows: T(n,k) is the number of nodes of degree k counted over all simple labeled graphs on n nodes, n>=1, 0<=k<=n-1.

Original entry on oeis.org

1, 2, 2, 6, 12, 6, 32, 96, 96, 32, 320, 1280, 1920, 1280, 320, 6144, 30720, 61440, 61440, 30720, 6144, 229376, 1376256, 3440640, 4587520, 3440640, 1376256, 229376, 16777216, 117440512, 352321536, 587202560, 587202560, 352321536, 117440512, 16777216

Offset: 1

Geoffrey Critzer, Apr 20 2017

			1,
2,   2,
6,   12,   6,
32,  96,   96,   32,
320, 1280, 1920, 1280, 320,
...

Row sums give A095340.

Columns for k=0-3: A123903, A095338, A038094, A038096.

nn = 9; Map[Select[#, # > 0 &] &,
  Drop[Transpose[Table[A[z_] := Sum[Binomial[n, k] 2^Binomial[n, 2] z^n/n!, {n, 0, nn}];Range[0, nn]! CoefficientList[Series[z A[z], {z, 0, nn}], z], {k,0, nn - 1}]], 1]] // Grid

E.g.f. for column k: x * Sum_{n>=0} binomial(n,k)*2^binomial(n,2)*x^n/n!.
Sum_{k=1..n-1} T(n,k)*k/2 = A095351(n).
T(n,k) = n*binomial(n-1,k)*2^binomial(n-1,2). - Alois P. Heinz, Apr 21 2017

cp's OEIS Frontend

A103904 a(n) = n*(n-1)/2 * 2^(n*(n-1)/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A094602 Total number of edges in all connected unlabeled graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A094594 Total number of edges in all connected labeled graphs on n nodes.

Views

Author

Keywords

Programs

Maple

Mathematica

Formula

Extensions

A285529 Triangle read by rows: T(n,k) is the number of nodes of degree k counted over all simple labeled graphs on n nodes, n>=1, 0<=k<=n-1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A103904 a(n) = n(n-1)/2 2^(n*(n-1)/2).