|
| |
|
|
A309784
|
|
T(n,k) is the number of non-equivalent distinguishing coloring partitions of the cycle on n vertices with exactly k parts. Regular triangle read by rows, n >= 1, 1 <= k <= n.
|
|
11
|
|
|
|
0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 4, 2, 1, 0, 1, 8, 10, 3, 1, 0, 1, 25, 32, 16, 3, 1, 0, 4, 62, 129, 84, 27, 4, 1, 0, 7, 176, 468, 433, 171, 37, 4, 1, 0, 18, 470, 1806, 2260, 1248, 338, 54, 5, 1, 0, 31, 1311, 6780, 11515, 8388, 3056, 590, 70, 5, 1, 0, 70, 3620, 25917, 58312, 56065, 26695, 6907, 1014, 96, 6, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,13
|
|
|
COMMENTS
|
The cycle graph is defined for n>=3; extended to n=1,2 using the closed form.
A vertex-coloring of a graph G is called distinguishing if it is only preserved by the identity automorphism of G. This notion is considered in the subject of symmetry breaking of simple (finite or infinite) graphs. A distinguishing coloring partition of a graph G is a partition of the vertices of G such that it induces a distinguishing coloring for G. We say two distinguishing coloring partitions P1 and P2 of G are equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. Given a graph G, we use the notation psi_k(G) to denote the number of non-equivalent distinguishing coloring partitions of G with exactly k parts. For n>=3, this sequence gives T(n,k) = psi_k(C_n), i.e., the number of non-equivalent distinguishing coloring partitions of the cycle C_n on n vertices with exactly k parts.
T(n,k) is the number of primitive (period n) n-bead bracelet structures which are not periodic palindromes using exactly k different colored beads. - Andrew Howroyd, Sep 20 2019
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
The triangle begins:
0;
0, 0;
0, 0, 1;
0, 0, 1, 1;
0, 0, 4, 2, 1;
0, 1, 8, 10, 3, 1;
0, 1, 25, 32, 16, 3, 1;
0, 4, 62, 129, 84, 27, 4, 1;
0, 7, 176, 468, 433, 171, 37, 4, 1;
0, 18, 470, 1806, 2260, 1248, 338, 54, 5, 1;
...
For n=6, we can partition the vertices of C_6 into exactly 3 parts in 8 ways such that all these partitions induce distinguishing colorings for C_6 and that all the 8 partitions are non-equivalent. The partitions are as follows:
{ { 1 }, { 2 }, { 3, 4, 5, 6 } }
{ { 1 }, { 2, 3 }, { 4, 5, 6 } }
{ { 1 }, { 2, 3, 4, 6 }, { 5 } }
{ { 1 }, { 2, 3, 5 }, { 4, 6 } }
{ { 1 }, { 2, 3, 6 }, { 4, 5 } }
{ { 1 }, { 2, 4, 5 }, { 3, 6 } }
{ { 1, 2 }, { 3, 4 }, { 5, 6 } }
{ { 1, 2 }, { 3, 5 }, { 4, 6 } }
For n=6, the above 8 partitions can be written as the following 3 colored bracelet structures: ABCCCC, ABBCCC, ABBBCB, ABBCBC, ABBCCB, ABCBBC, AABBCC, AABCBC. - Andrew Howroyd, Sep 22 2019
|
|
|
PROG
|
Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
R(n)={Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
T(n)={my(A=Ach(n), M=R(n), S=matrix(n, n, n, k, stirling(n, k, 2))); Mat(vectorv(n, n, sumdiv(n, d, moebius(d)*(M[n/d, ] + A[n/d, ])/2 - moebius(d)*(S[(n/d+1)\2, ] + S[n/d\2+1, ] + if((n-d)%2, A[(n/d+1)\2, ] + A[n/d\2+1, ]))/if(d%2, 2, 1) )))}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Oct 02 2019
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
