A322278 -id:A322278

Search: a322278 -id:a322278

Displaying 1-6 of 6 results found.

page 1

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.

+10
12

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,8

COMMENTS

Not all colors need to be used.

LINKS

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.

FORMULA

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

EXAMPLE

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

...

MATHEMATICA

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

PROG

(PARI)

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, ]))

CROSSREFS

Columns k=0..4 are A000007, A000012, A047863, A191371, A223887.

Main diagonal gives A372920.

Cf. A058843, A058875, A322278, A322279.

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Dec 01 2018

STATUS

approved

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.

+10
8

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,8

COMMENTS

Not all colors need to be used.

LINKS

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.

FORMULA

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

EXAMPLE

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

...

PROG

(PARI)

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, ]))

CROSSREFS

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

Cf. A058843, A058875, A322278, A322280.

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Dec 01 2018

STATUS

approved

A322064

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

+10
7

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

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.

LINKS

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

EXAMPLE

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}}

MATHEMATICA

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}]

PROG

(PARI) \\ See A322278 for M.

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

CROSSREFS

Row sums of A322278.

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

KEYWORD

nonn

AUTHOR

Gus Wiseman, Nov 25 2018

EXTENSIONS

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

STATUS

approved

A002032

Number of n-colored connected graphs on n labeled nodes.
(Formerly M2141 N0852)

+10
6

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

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

REFERENCES

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

LINKS

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.

FORMULA

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

MATHEMATICA

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

PROG

(PARI) 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

CROSSREFS

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

Cf. A001187, A322278, A322279, A322280.

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

STATUS

approved

A322330

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

+10
3

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

3,1

COMMENTS

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.

LINKS

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

PROG

(PARI) \\ See A322278 for M.

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

CROSSREFS

Column k=3 of A322278.

Cf. A058873 (not necessarily connected), A322064.

Cf. A001832, A322331.

KEYWORD

nonn

AUTHOR

Andrew Howroyd, Dec 03 2018

STATUS

approved

A322331

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

+10
3

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

4,1

COMMENTS

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.

LINKS

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

PROG

(PARI) \\ See A322278 for M.

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

CROSSREFS

Column k=4 of A322278.

Cf. A058873 (not necessarily connected), A322064.

Cf. A001832, A322330.

KEYWORD

nonn

AUTHOR

Andrew Howroyd, Dec 03 2018

STATUS

approved

page 1

Search completed in 0.009 seconds