A322278 -id:A322278 - cp's OEIS frontend

A322280 Array read by antidiagonals: T(n,k) is the number of graphs on n labeled nodes, each node being colored with one of k colors, where no edge connects two nodes of the same color.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 15, 26, 1, 0, 1, 5, 28, 123, 162, 1, 0, 1, 6, 45, 340, 1635, 1442, 1, 0, 1, 7, 66, 725, 7108, 35043, 18306, 1, 0, 1, 8, 91, 1326, 20805, 254404, 1206915, 330626, 1, 0, 1, 9, 120, 2191, 48486, 1058885, 15531268, 66622083, 8488962, 1, 0

Offset: 0

Andrew Howroyd, Dec 01 2018

Not all colors need to be used.

			Array begins:
===============================================================
n\k| 0 1      2        3          4           5           6
---+-----------------------------------------------------------
0  | 1 1      1        1          1           1           1 ...
1  | 0 1      2        3          4           5           6 ...
2  | 0 1      6       15         28          45          66 ...
3  | 0 1     26      123        340         725        1326 ...
4  | 0 1    162     1635       7108       20805       48486 ...
5  | 0 1   1442    35043     254404     1058885     3216486 ...
6  | 0 1  18306  1206915   15531268    95261445   386056326 ...
7  | 0 1 330626 66622083 1613235460 15110296325 83645197446 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. C. Read and E. M. Wright, Colored graphs: A correction and extension, Canad. J. Math. 22 1970 594-596.

Columns k=0..4 are A000007, A000012, A047863, A191371, A223887.
Main diagonal gives A372920.
Cf. A058843, A058875, A322278, A322279.

nmax = 10;
T[n_, k_] := n!*2^Binomial[n, 2]*SeriesCoefficient[Sum[ x^i/(i!* 2^Binomial[i, 2]), {i, 0, nmax}]^k, {x, 0, n}];
Table[T[n - k, k], {n, 0, nmax}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Sep 23 2019 *)

M(n)={
  my(p=sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n));
  my(q=sum(j=0, n, x^j*j!*2^binomial(j, 2)) + O(x*x^n));
  matconcat([1, Mat(vector(n, k, Col(serconvol(q, p^k))))]);
}
my(T=M(7)); for(n=1, #T, print(T[n,]))

T(n,k) = n!*2^binomial(n,2) * [x^n](Sum_{i>=0} x^i/(i!*2^binomial(i,2)))^k.

T(n,k) = Sum_{j=0..k} binomial(k,j)*j!*A058843(n,j).

A322279 Array read by antidiagonals: T(n,k) is the number of connected graphs on n labeled nodes, each node being colored with one of k colors, where no edge connects two nodes of the same color.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 1, 4, 6, 6, 0, 0, 1, 5, 12, 42, 38, 0, 0, 1, 6, 20, 132, 618, 390, 0, 0, 1, 7, 30, 300, 3156, 15990, 6062, 0, 0, 1, 8, 42, 570, 9980, 136980, 668526, 134526, 0, 0, 1, 9, 56, 966, 24330, 616260, 10015092, 43558242, 4172198, 0, 0

Offset: 0

Andrew Howroyd, Dec 01 2018

Not all colors need to be used.

			Array begins:
===============================================================
n\k| 0 1      2        3          4           5           6
---+-----------------------------------------------------------
0  | 1 1      1        1          1           1           1 ...
1  | 0 1      2        3          4           5           6 ...
2  | 0 0      2        6         12          20          30 ...
3  | 0 0      6       42        132         300         570 ...
4  | 0 0     38      618       3156        9980       24330 ...
5  | 0 0    390    15990     136980      616260     1956810 ...
6  | 0 0   6062   668526   10015092    65814020   277164210 ...
7  | 0 0 134526 43558242 1199364852 11878194300 67774951650 ...
...

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

Columns k=2..5 are A002027, A002028, A002029, A002030.

Cf. A058843, A058875, A322278, A322280.

M(n)={
  my(p=sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n));
  my(q=sum(j=0, n, x^j*2^binomial(j, 2)) + O(x*x^n));
  my(W=Mat(vector(n, k, Col(serlaplace(1 + log(serconvol(q, p^k)))))));
  matconcat([1, W]);
}
my(T=M(7)); for(n=1, #T, print(T[n,]))

k-th column is the logarithmic transform of the k-th column of A322280.

E.g.f of k-th column: 1 + log(Sum_{n>=0} A322280(n,k)*x^n/n!).

A322064 Number of ways to choose a stable partition of a simple connected graph with n vertices.

Original entry on oeis.org

1, 1, 1, 7, 141, 6533, 631875, 123430027, 48659732725, 39107797223409, 64702785181953175, 221636039917857648631, 1575528053913118966200441, 23249384407499950496231003021, 711653666389829384034090082068939, 45128328085994437067694854477617868995

Offset: 0

Gus Wiseman, Nov 25 2018

nonn

A stable partition of a graph is a set partition of the vertices where no non-singleton edge has both ends in the same block.

			The a(3) = 7 stable partitions. The simple connected graph is on top, and below is a list of all its stable partitions.
  {1,3}{2,3}     {1,2}{2,3}     {1,2}{1,3}     {1,2}{1,3}{2,3}
  --------       --------       --------       --------
  {{1,2},{3}}    {{1,3},{2}}    {{1},{2,3}}    {{1},{2},{3}}
  {{1},{2},{3}}  {{1},{2},{3}}  {{1},{2},{3}}

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

Row sums of A322278.

Cf. A000110, A000569, A001187, A006125, A048143, A229048, A240936, A245883, A277203, A321911, A321979, A322063, A322065.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Sum[Length[Select[Subsets[Complement[Subsets[Range[n],{2}],Union@@Subsets/@stn]],And[Union@@#==Range[n],Length[csm[#]]==1]&]],{stn,sps[Range[n]]}],{n,5}]

\\ See A322278 for M.
seq(n)={concat([1], (M(n)*vectorv(n,i,1))~)} \\ Andrew Howroyd, Dec 01 2018

Terms a(7) and beyond from Andrew Howroyd, Dec 01 2018

A002032 Number of n-colored connected graphs on n labeled nodes.

Original entry on oeis.org

1, 1, 2, 24, 912, 87360, 19226880, 9405930240, 10142439229440, 24057598104207360, 125180857812868300800, 1422700916050060841779200, 35136968950395142864227532800, 1876028272361273394915958613606400, 215474119792145796020405035320528076800

Offset: 0

N. J. A. Sloane

nonn

Every connected graph on n nodes can be colored with n colors in exactly n! ways, so this sequence is just n! * A001187(n). - Andrew Howroyd, Dec 03 2018

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.

Cf. A002027. A002028, A002029, A002030, A002031.

Cf. A001187, A322278, A322279, A322280.

(* b = A001187 *) b[n_] := b[n] = If[n == 0, 1, 2^(n(n-1)/2) - Sum[k* Binomial[n, k]*2^((n-k)(n-k-1)/2)*b[k], {k, 1, n-1}]/n];
a[n_] := n! b[n];
Array[a, 14] (* Jean-François Alcover, Aug 16 2019, using Alois P. Heinz's code for A001187 *)

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

a(n) = n!*A001187(n). - Andrew Howroyd, Dec 03 2018
Define M_0(k)=1, M_n(0)=0, M_n(k) = Sum_{r=0..n} C(n,r)*2^(r*(n-r))*M_r(k-1) [M_n(k) = A322280(n,k)], m_n(k) = M_n(k) -Sum_{r=1..n-1} C(n-1,r-1)*m_r(k)*M_{n-r}(k) [m_n(k) = A322279(n,k)], f_n(k) = Sum_{r=1..k} (-1)^(k-r)*C(k,r)*m_n(r). This sequence gives a(n) = f_n(n). - Sean A. Irvine, May 29 2013, edited Andrew Howroyd, Dec 03 2018
The above formula is referenced by sequences A002027-A002030, A002031. - Andrew Howroyd, Dec 03 2018

More terms from Sean A. Irvine, May 29 2013
Name clarified by Andrew Howroyd, Dec 03 2018
a(0)=1 prepended by Andrew Howroyd, Jan 05 2024

A322330 Number of 3-colored connected graphs on n labeled nodes up to permutation of the colors.

Original entry on oeis.org

4, 84, 2470, 108390, 7192444, 726782784, 112795368970, 27132558531330, 10196751602156944, 6022337098348167564, 5612248139616665602510, 8274349264629020203315230, 19333678744046195877906230404, 71675537050405087142116150917624, 421915518251999125756688245906168690

Offset: 3

Andrew Howroyd, Dec 03 2018

nonn

Equivalently, the number of ways to choose a stable partition of a simple connected graph on n labeled nodes with 3 parts. See A322064 for the definition of stable partition.

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

Column k=3 of A322278.
Cf. A058873 (not necessarily connected), A322064.
Cf. A001832, A322331.

\\ See A322278 for M.
{ my(N=20); M(N,3)[3..N, 3]~ }

A322331 Number of 4-colored connected graphs on n labeled nodes up to permutation of the colors.

Original entry on oeis.org

38, 3140, 307390, 42747460, 9030799218, 3012940879620, 1628920258500230, 1451200592494754420, 2152262350514389189978, 5344908165470797467243700, 22297912999366719508496874990, 156537595118740106754291705258180, 1850935702258755131781978373277937218

Offset: 4

Andrew Howroyd, Dec 03 2018

nonn

Equivalently, the number of ways to choose a stable partition of a simple connected graph on n labeled nodes with 4 parts. See A322064 for the definition of stable partition.

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

Column k=4 of A322278.
Cf. A058873 (not necessarily connected), A322064.
Cf. A001832, A322330.

\\ See A322278 for M.
{ my(N=20); M(N,4)[4..N, 4]~ }

cp's OEIS Frontend

A322280 Array read by antidiagonals: T(n,k) is the number of graphs on n labeled nodes, each node being colored with one of k colors, where no edge connects two nodes of the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A322279 Array read by antidiagonals: T(n,k) is the number of connected graphs on n labeled nodes, each node being colored with one of k colors, where no edge connects two nodes of the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A322064 Number of ways to choose a stable partition of a simple connected graph with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A002032 Number of n-colored connected graphs on n labeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A322330 Number of 3-colored connected graphs on n labeled nodes up to permutation of the colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A322331 Number of 4-colored connected graphs on n labeled nodes up to permutation of the colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI