A063842 -id:A063842 - cp's OEIS frontend

A063843 Number of n-multigraphs on 5 nodes.

0, 1, 34, 792, 10688, 90005, 533358, 2437848, 9156288, 29522961, 84293770, 217993600, 519341472, 1154658869, 2420188694, 4821091920, 9187076352, 16837177281, 29809183410, 51172613512, 85448030080, 139159855989, 221554769150, 345523218536, 528767663040

Offset: 0

N. J. A. Sloane, Aug 25 2001

Equivalently, number of ways to color edges of complete graph on 5 nodes with n colors, under action of symmetric group S_5, of order 120, with cycle index on edges given by (1/120)*(24*x5^2 + 30*x2*x4^2 + 20*x3^3*x1 + 20*x3*x6*x1 + 15*x1^2*x2^4 + 10*x1^4*x2^3 + x1^10). Setting all x_i = n gives the sequence.
Number of vertex colorings of the Petersen graph. Marko Riedel, Mar 24 2016
Number of unoriented colorings of the 10 triangular edges or triangular faces of a pentachoron, Schläfli symbol {3,3,3}, using n or fewer colors. Also called a 5-cell or 4-simplex. - Robert A. Russell, Oct 17 2020

T. D. Noe, Table of n, a(n) for n = 0..1000
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes
Marko Riedel, Vertex colorings of the Petersen graph, Math StackExchange
Index entries for linear recurrences with constant coefficients, signature (11,-55,165,-330,462,-462,330,-165,55,-11,1).

Cf. A063842. A row of A063841.
Cf. A331350 (oriented), A331352 (chiral), A331353 (achiral), A000389(n+4) (vertices and facets)
Other polychora: A331359 (8-cell), A331355 (16-cell), A338953 (24-cell), A338965 (120-cell, 600-cell).
Row 4 of A327084 (simplex edges and ridges) and A337884 (simplex faces and peaks).

f:=n-> 1/120*(24*n^2+50*n^3+20*n^4+15*n^6+10*n^7+n^10);

Table[(24n^2+50n^3+20n^4+15n^6+10n^7+n^10)/120,{n,0,30}] (* or *) LinearRecurrence[{11,-55,165,-330,462,-462,330,-165,55,-11,1},{0,1,34,792,10688,90005,533358,2437848,9156288,29522961,84293770},30] (* Harvey P. Dale, Oct 20 2012 *)

a(n)=n^2*(n^8+10*n^5+15*n^4+20*n^2+50*n+24)/120 \\ Charles R Greathouse IV, Jan 20 2012

a(n) = (1/120)*(24*n^2+50*n^3+20*n^4+15*n^6+10*n^7+n^10).
a(n+1) = (1/5!)*(n^10 + 10*n^9 + 45*n^8 + 130*n^7 + 295*n^6 + 552*n^5 + 805*n^4 + 900*n^3 + 774*n^2 + 448*n + 120).
G.f. = (1 + 23*x + 473*x^2 + 3681*x^3 + 10717*x^4 + 11221*x^5 + 3779*x^6 + 339*x^7 + 6*x^8)/(1-x)^11.  - M. F. Hasler, Jan 19 2012
a(0)=0, a(1)=1, a(2)=34, a(3)=792, a(4)=10688, a(5)=90005, a(6)=533358, a(7)=2437848, a(8)=9156288, a(9)=29522961, a(10)=84293770, a(n)= 11*a(n-1)- 55*a(n-2)+165*a(n-3)-330*a(n-4)+462*a(n-5)-462*a(n-6)+ 330*a(n-7)- 165*a(n-8)+55*a(n-9)-11*a(n-10)+a(n-11). - Harvey P. Dale, Oct 20 2012
From Robert A. Russell, Oct 17 2020: (Start)
a(n) = A331350(n) - A331352(n) = (A331350(n) + A331353(n)) / 2 = A331352(n) + A331353(n).
a(n) = 1*C(n,1) + 32*C(n,2) + 693*C(n,3) + 7720*C(n,4) + 44150*C(n,5) + 138312*C(n,6) + 247380*C(n,7) + 252000*C(n,8) + 136080*C(n,9) + 30240*C(n,10), where the coefficient of C(n,k) is the number of unoriented colorings using exactly k colors. (End)

More terms from Vladeta Jovovic, Sep 02 2001

A199406 The number of inequivalent ways to color the edges of a cube using at most n colors.

Original entry on oeis.org

1, 144, 12111, 358120, 5131650, 45528756, 288936634, 1433251296, 5887880415, 20842168600, 65402344161, 185788177224, 485443851256, 1181242399260, 2703252560100, 5864398969216, 12138503871789, 24101498435616, 46112016365155, 85335258695400, 153249227870046

Offset: 1

Geoffrey Critzer, Nov 05 2011

Two edge colorings are equivalent if one is the mirror image of the other or the cube can be picked up and rotated in any manner to obtain the other.
The group here has order 48 (compare A060530). - N. J. A. Sloane, Aug 14 2012
Also the number of unoriented colorings of the 12 edges of a regular octahedron with n or fewer colors. The Schläfli symbols of the cube and octahedron are {4,3} and {3,4} respectively. They are mutually dual. For an unoriented coloring, chiral pairs are counted as one. - Robert A. Russell, Oct 17 2020

T. D. Noe, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (13,-78,286,-715,1287,-1716,1716,-1287,715,-286,78,-13,1).

Cf. A060530 (oriented), A337406 (chiral), A331351 (achiral), A128766 (cube vertices, octahedron faces), A198833 (cube faces, octahedron vertices), A063842(n-1) (tetrahedron), A337963 (dodecahedron, icosahedron).

Row 3 of A337408 (orthotope edges, orthoplex ridges) and A337412 (orthoplex edges, orthotope ridges).

Table[CycleIndex[KSubsetGroup[Automorphisms[CubicalGraph], Edges[CubicalGraph]],s] /. Table[s[i]->n, {i,1,6}], {n,1,15}]
Table[(8n^2+12n^3+8n^4+4n^6+12n^7+3n^8+n^12)/48, {n,20}] (* Robert A. Russell, Oct 17 2020 *)

a(n) = n^12/48 + n^8/16 + n^7/4 + n^6/12 + n^4/6 + n^3/4 + n^2/6.
Cycle index = 1/48(s_1^12+3s_1^4s_2^4+12s_1^2s_2^5+4s_2^6+8s_3^4+12s_4^3+8s_6^2).
G.f.: -x*(76*x^10 +10016*x^9 +212772*x^8 +1380453*x^7 +3384939*x^6 +3388593*x^5 +1380279*x^4 +211623*x^3 +10317*x^2 +131*x +1)/(x -1)^13. [Colin Barker, Aug 13 2012]
From Robert A. Russell, Oct 17 2020: (Start)
a(n) = A060530(n) - A337406(n) = (A060530(n) + A331351(n)) / 2 = A337406(n) + A331351(n).
a(n) = 1*C(n,1) + 142*C(n,2) + 11682*C(n,3) + 310536*C(n,4) + 3460725*C(n,5) + 19870590*C(n,6) + 65886660*C(n,7) + 133585200*C(n,8) + 168399000*C(n,9) + 128898000*C(n,10) + 54885600*C(n,11) + 9979200*C(n,12), where the coefficient of C(n,k) is the number of unoriented colorings using exactly k colors. (End)

A327084 Array read by descending antidiagonals: A(n,k) is the number of unoriented colorings of the edges of a regular n-dimensional simplex using up to k colors.

Original entry on oeis.org

1, 2, 1, 3, 4, 1, 4, 10, 11, 1, 5, 20, 66, 34, 1, 6, 35, 276, 792, 156, 1, 7, 56, 900, 10688, 25506, 1044, 1, 8, 84, 2451, 90005, 1601952, 2302938, 12346, 1, 9, 120, 5831, 533358, 43571400, 892341888, 591901884, 274668

Offset: 1

Robert A. Russell, Aug 19 2019

An n-dimensional simplex has n+1 vertices and (n+1)*n/2 edges. For n=1, the figure is a line segment with one edge. For n=2, the figure is a triangle with three edges. For n=3, the figure is a tetrahedron with six edges. The Schläfli symbol, {3,...,3}, of the regular n-dimensional simplex consists of n-1 threes. Two unoriented colorings are the same if congruent; chiral pairs are counted as one.

A(n,k) is also the number of unoriented colorings of (n-2)-dimensional regular simplices in an n-dimensional simplex using up to k colors. Thus, A(2,k) is also the number of unoriented colorings of the vertices (0-dimensional simplices) of an equilateral triangle.

			Array begins with A(1,1):
  1  2   3     4     5      6       7       8        9       10 ...
  1  4  10    20    35     56      84     120      165      220 ...
  1 11  66   276   900   2451    5831   12496    24651    45475 ...
  1 34 792 10688 90005 533358 2437848 9156288 29522961 84293770 ...
  ...
For A(2,3) = 10, the nine achiral colorings are AAA, AAB, AAC, ABB, ACC, BBB, BBC, BCC, and CCC. The chiral pair is ABC-ACB.

Chai Wah Wu, Table of n, a(n) for n = 1..1528 (terms 1..325 from Robert A. Russell)
Harald Fripertinger, The cycle type of the induced action on 2-subsets
E. M. Palmer and R. W. Robinson, Enumeration under two representations of the wreath product, Acta Math., 131 (1973), 123-143.

Cf. A327083 (oriented), A327085 (chiral), A327086 (achiral), A327088 (exactly k colors), A325000 (vertices, facets), A337884 (faces, peaks), A337408 (orthotope edges, orthoplex ridges), A337412 (orthoplex edges, orthotope ridges).
Rows 1-4 are A000027, A000292, A063842(n-1), A063843.
Cf. A063841 (k-multigraphs on n nodes).

CycleX[{2}] = {{1,1}}; (* cycle index for permutation with given cycle structure *)
CycleX[{n_Integer}] := CycleX[n] = If[EvenQ[n], {{n/2,1}, {n,(n-2)/2}}, {{n,(n-1)/2}}]
compress[x : {{, } ...}] := (s = Sort[x]; For[i = Length[s], i > 1, i -= 1, If[s[[i, 1]] == s[[i-1,1]], s[[i-1,2]] += s[[i,2]]; s = Delete[s,i], Null]]; s)
CycleX[p_List] := CycleX[p] = compress[Join[CycleX[Drop[p, -1]], If[Last[p] > 1, CycleX[{Last[p]}], ## &[]], If[# == Last[p], {#, Last[p]}, {LCM[#, Last[p]], GCD[#, Last[p]]}] & /@ Drop[p, -1]]]
pc[p_List] := Module[{ci, mb}, mb = DeleteDuplicates[p]; ci = Count[p, #] & /@ mb; Total[p]!/(Times @@ (ci!) Times @@ (mb^ci))] (* partition count *)
row[n_Integer] := row[n] = Factor[Total[pc[#] j^Total[CycleX[#]][[2]] & /@ IntegerPartitions[n+1]]/(n+1)!]
array[n_, k_] := row[n] /. j -> k
Table[array[n,d-n+1], {d,1,10}, {n,1,d}] // Flatten
(* Using Fripertinger's exponent per Andrew Howroyd code in A063841: *)
pc[p_] := Module[{ci, mb}, mb = DeleteDuplicates[p]; ci = Count[p, #] &/@ mb; Total[p]!/(Times @@ (ci!) Times @@ (mb^ci))]
ex[v_] := Sum[GCD[v[[i]], v[[j]]], {i,2,Length[v]}, {j,i-1}] + Total[Quotient[v,2]]
array[n_,k_] := Total[pc[#]k^ex[#] &/@ IntegerPartitions[n+1]]/(n+1)!
Table[array[n,d-n+1], {d,10}, {n,d}] // Flatten
(* Another program (translated from Andrew Howroyd's PARI code): *)
permcount[v_] := Module[{m=1, s=0, k=0, t}, For[i=1, i <= Length[v], i++, t = v[[i]]; k = If[i>1 && t == v[[i-1]], k+1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i-1}] + Total[Quotient[v, 2]];
T[n_, k_] := Module[{s = 0}, Do[s += permcount[p]*k^edges[p], {p, IntegerPartitions[n+1]}]; s/(n+1)!];
Table[T[n-k+1, k], {n, 1, 9}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jan 08 2021 *)

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
T(n, k) = {my(s=0); forpart(p=n+1, s+=permcount(p)*k^edges(p)); s/(n+1)!} \\ Andrew Howroyd, Sep 06 2019

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A327084_T(n,k): return int(sum(Fraction(k**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n+1))) # Chai Wah Wu, Jul 09 2024

The algorithm used in the Mathematica program below assigns each permutation of the vertices to a partition of n+1. It then determines the number of permutations for each partition and the cycle index for each partition.
A(n,k) = Sum_{j=1..(n+1)*n/2} A327088(n,j) * binomial(k,j).
A(n,k) = A327083(n,k) - A327085(n,k) = (A327083(n,k) + A327086(n,k)) / 2 = A327085(n,k) + A327086(n,k).
A(n,k) = A063841(n+1,k-1).

A063841 Table T(n,k) giving number of k-multigraphs on n nodes (n >= 1, k >= 0) read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 10, 11, 1, 1, 5, 20, 66, 34, 1, 1, 6, 35, 276, 792, 156, 1, 1, 7, 56, 900, 10688, 25506, 1044, 1, 1, 8, 84, 2451, 90005, 1601952, 2302938, 12346, 1, 1, 9, 120, 5831, 533358, 43571400, 892341888, 591901884, 274668, 1

Offset: 1

N. J. A. Sloane, Aug 25 2001

The first five rows admit the g.f. 1/(1-x), 1/(1-x)^2, 1/(1-x)^4 and those given in A063842, A063843. Is it known that the n-th row admits a rational g.f. with denominator (1-x)^A000124(n)? - M. F. Hasler, Jan 19 2012

T(n+1,k-1) is the number of unoriented ways to color the edges of a regular n-dimensional simplex using up to k colors. - Robert A. Russell, Aug 21 2019

			Table begins
===========================================================
n\k| 0    1       2         3           4             5
---|-------------------------------------------------------
1  | 1    1       1         1           1             1 ...
2  | 1    2       3         4           5             6 ...
3  | 1    4      10        20          35            56 ...
4  | 1   11      66       276         900          2451 ...
5  | 1   34     792     10688       90005        533358 ...
6  | 1  156   25506   1601952    43571400     661452084 ...
7  | 1 1044 2302938 892341888 95277592625 4364646955812 ...
...
T(3,2)=10 because there are 10 unlabeled graphs with 3 nodes with at most 2 edges connecting any pair.
(. . .),(.-. .),(.-.-.),(.-.-.-),(.=. .),(.=.=.),(.=.=.=),(.-.=.),(.-.-.=),(.=.=.-). - _Geoffrey Critzer_, Jan 23 2012

Chai Wah Wu, Table of n, a(n) for n = 1..1584 (terms 1..820 from Andrew Howroyd)
Harald Fripertinger, The cycle type of the induced action on 2-subsets
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes

Columns give A000088, A004102, A053400, A053420, A053421.
Rows (4th and 5th) are listed in A063842, A063843.
Cf. A327084 (unoriented simplex edge colorings).

(* This code gives the array T(n,k). *) Needs["Combinatorica`"]; Transpose[Table[Table[PairGroupIndex[SymmetricGroup[n],s]/.Table[s[i]->k+1, {i,0,Binomial[n,2]}], {n,1,7}], {k,0,6}]]//Grid (* Geoffrey Critzer, Jan 23 2012 *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
T[n_, k_] := (s=0; Do[s += permcount[p]*(k+1)^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Table[T[n-k, k], {n, 1, 10}, {k, n-1, 0, -1}] // Flatten (* Jean-François Alcover, Jul 08 2018, after Andrew Howroyd *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
T(n, k) = {my(s=0); forpart(p=n, s+=permcount(p)*(k+1)^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A063841_T(n,k): return int(sum(Fraction((k+1)**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 09 2024

T(n,k) = A327084(n-1,k+1) for n > 1. - Robert A. Russell, Aug 21 2019

More terms from Vladeta Jovovic, Sep 03 2001

A337963 Number of unoriented colorings of the 30 edges of a regular dodecahedron or icosahedron using n or fewer colors.

Original entry on oeis.org

1, 8972888, 1715781087090, 9607681898535232, 7761021569825850025, 1842282666811844114760, 187827835789041358086652, 10316166994361788355074560, 353259652295786354195866209

Offset: 1

Robert A. Russell, Oct 03 2020

Each chiral pair is counted as one when enumerating unoriented arrangements. The Schläfli symbols for the regular icosahedron and regular dodecahedron are {3,5} and {5,3} respectively. They are mutually dual.

Index entries for linear recurrences with constant coefficients, signature (31, -465, 4495, -31465, 169911, -736281, 2629575, -7888725, 20160075, -44352165, 84672315, -141120525, 206253075, -265182525, 300540195, -300540195, 265182525, -206253075, 141120525, -84672315, 44352165, -20160075, 7888725, -2629575, 736281, -169911, 31465, -4495, 465, -31, 1).

Cf. A282670 (oriented), A337964 (chiral), A337953 (achiral).
Other elements: A252704 (dodecahedron vertices, icosahedron faces), A252705 (dodecahedron faces, icosahedron vertices).
Other polyhedra: A063842(n-1) (tetrahedron), A199406 (cube/octahedron).

Table[(n^30+15n^17+15n^16+n^15+20n^10+24n^6+20n^5+24 n^3)/120,{n,30}]

a(n) = (n^30 + 15*n^17 + 15*n^16 + n^15 + 20*n^10 + 24*n^6 + 20*n^5 + 24*n^3) / 120.
a(n) = 1*C(n,1) + 8972886*C(n,2) + 1715754168429*C(n,3) + 9600818828024196*C(n,4) + 7713000318054315890*C(n,5) + 1795860618305879894604*C(n,6) + 175094502365510493018246*C(n,7) + 8864694277953928285823280*C(n,8) + 267022176369217557115630320*C(n,9) + 5242809910440825835898466240*C(n,10) + 71533267863142929693959229120*C(n,11) + 710438037081557065871500310400*C(n,12) + 5315930749209812373842350550400*C(n,13) + 30757743469720892095213642099200*C(n,14) + 140355611183197554763055563526400*C(n,15) + 512749946932635114150296808960000*C(n,16) + 1516429386147442831807688225280000*C(n,17) + 3659586727743885232600161343488000*C(n,18) + 7243809192262705479647976345600000*C(n,19) + 11790166608014659213935198412800000*C(n,20) + 15777861864770715186138442260480000*C(n,21) + 17309780658863308912305163714560000*C(n,22) + 15473267984805657314364466790400000*C(n,23) + 11155559298200256484274739609600000*C(n,24) + 6385716995478673633837056000000000*C(n,25) + 2834140845518322325537731379200000*C(n,26) + 939989821959452064042418176000000*C(n,27) + 219202016094796777623060480000000*C(n,28) + 32051387227306419585220608000000*C(n,29) + 2210440498434925488635904000000*C(n,30), where the coefficient of C(n,k) is the number of unoriented colorings using exactly k colors.
a(n) = A282670(n) - A337964(n) = (A282670(n) + A337953(n)) / 2 = A337964(n) + A337953(n).

A337899 Number of chiral pairs of colorings of the edges of a regular tetrahedron using n or fewer colors.

Original entry on oeis.org

0, 1, 21, 140, 575, 1785, 4606, 10416, 21330, 40425, 71995, 121836, 197561, 308945, 468300, 690880, 995316, 1404081, 1943985, 2646700, 3549315, 4694921, 6133226, 7921200, 10123750, 12814425, 16076151, 20001996

Offset: 1

Robert A. Russell, Sep 28 2020

nonn

Each member of a chiral pair is a reflection, but not a rotation, of the other. A regular tetrahedron has 6 edges and Schläfli symbol {3,3}.

			For a(2)=1, two opposite edges and one edge connecting those have one color; the other three edges have the other color.

Index entries for linear recurrences with constant coefficients, signature (7, -21, 35, -35, 21, -7, 1).

Cf. A046023(unoriented), A063842(n-1) (oriented), A037270 (chiral).
Other elements: A000332 (vertices and faces).
Other polyhedra: A337406 (cube/octahedron).
Row 3 of A327085 (chiral pairs of colorings of edges or ridges of an n-simplex).

Mathematica
```
Table[(n-1)n^2(n+1)(n^2-2)/24, {n, 40}]
```

a(n) = (n-1) * n^2 * (n+1) * (n^2-2) / 24.
a(n) = 1*C(n,2) + 18*C(n,3) + 62*C(n,4) + 75*C(n,5) + 30*C(n,6), where the coefficient of C(n,k) is the number of chiral pairs of colorings using exactly k colors.
a(n) = A046023(n) - A063842(n-1) = (A046023(n) - A037270(n)) / 2 = A063842(n-1) - A037270(n).
G.f.: x^2 * (1+x) * (1+13x+x^2)/(1-x)^7.

cp's OEIS Frontend

A063843 Number of n-multigraphs on 5 nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A199406 The number of inequivalent ways to color the edges of a cube using at most n colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A327084 Array read by descending antidiagonals: A(n,k) is the number of unoriented colorings of the edges of a regular n-dimensional simplex using up to k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A063841 Table T(n,k) giving number of k-multigraphs on n nodes (n >= 1, k >= 0) read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A337963 Number of unoriented colorings of the 30 edges of a regular dodecahedron or icosahedron using n or fewer colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A337899 Number of chiral pairs of colorings of the edges of a regular tetrahedron using n or fewer colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula