| Displaying 1-8 of 8 results found.
page
1
Triangle read by rows: T(n,k) is the number of n-bead bracelets with exactly k different colored beads.
+10
14
1, 1, 1, 1, 2, 1, 1, 4, 6, 3, 1, 6, 18, 24, 12, 1, 11, 56, 136, 150, 60, 1, 16, 147, 612, 1200, 1080, 360, 1, 28, 411, 2619, 7905, 11970, 8820, 2520, 1, 44, 1084, 10480, 46400, 105840, 129360, 80640, 20160, 1, 76, 2979, 41388, 255636, 821952, 1481760, 1512000, 816480, 181440
COMMENTS
For bracelets, chiral pairs are counted as one.
FORMULA
T(n,k) = (k!/4) * (S2(floor((n+1)/2),k) + S2(ceiling((n+1)/2),k)) + (k!/2n) * Sum_{d|n} phi(d) * S2(n/d,k), where S2 is the Stirling subset number A008277. G.f. for column k>1: (k!/4) * x^(2k-2) * (1+x)^2 / Product_{i=1..k} (1-i x^2) - Sum_{d>0} (phi(d)/2d) * Sum_{j} (-1)^(k-j) * C(k,j) * log(1-j*x^d).
(End)
EXAMPLE
Triangle begins with T(1,1):
1;
1, 1;
1, 2, 1;
1, 4, 6, 3;
1, 6, 18, 24, 12;
1, 11, 56, 136, 150, 60;
1, 16, 147, 612, 1200, 1080, 360;
1, 28, 411, 2619, 7905, 11970, 8820, 2520;
1, 44, 1084, 10480, 46400, 105840, 129360, 80640, 20160;
1, 76, 2979, 41388, 255636, 821952, 1481760, 1512000, 816480, 181440;
For T(4,2)=4, the arrangements are AAAB, AABB, ABAB, and ABBB, all achiral.
For T(4,4)=3, the arrangements are ABCD, ABDC, and ACBD, whose chiral partners are ADCB, ACDB, and ADBC respectively. - Robert A. Russell, Sep 26 2018
MATHEMATICA
(* t = A081720 *) t[n_, k_] := (For[t1 = 0; d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*k^(n/d)]]; If[EvenQ[n], (t1 + (n/2)*(1 + k)*k^(n/2))/(2*n), (t1 + n*k^((n+1)/2))/(2*n)]); T[n_, k_] := Sum[(-1)^i * Binomial[k, i]*t[n, k-i], {i, 0, k-1}]; Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 07 2017, after Andrew Howroyd *) Table[k! DivisorSum[n, EulerPhi[#] StirlingS2[n/#, k]&]/(2n) + k!(StirlingS2[Floor[(n+1)/2], k] + StirlingS2[Ceiling[(n+1)/2], k])/4, {n, 1, 10}, {k, 1, n}] // Flatten (* Robert A. Russell, Sep 26 2018 *)
Number of pairs of orientable necklaces with n beads and two colors; i.e., turning the necklace over does not leave it unchanged.
+10
12
0, 0, 0, 0, 0, 0, 1, 2, 6, 14, 30, 62, 128, 252, 495, 968, 1866, 3600, 6917, 13286, 25476, 48916, 93837, 180314, 346554, 666996, 1284570, 2477342, 4781502, 9240012, 17871708, 34604066, 67060746, 130085052, 252548760, 490722344
COMMENTS
Number of chiral bracelets with n beads and two colors.
LINKS
John P. McSorley and Alan H. Schoen, Rhombic tilings of (n,k)-ovals, (n, k, lambda)-cyclic difference sets, and related topics, Discrete Math., 313 (2013), 129-154. - From N. J. A. Sloane, Nov 26 2012
FORMULA
G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 2*x^n)/n - (1 + x)^2/(1 - 2*x^2))/2. - Herbert Kociemba, Nov 02 2016 For n > 0, a(n) = -(k^floor((n + 1)/2) + k^ceiling((n + 1)/2))/4 + (1/(2*n))* Sum_{d|n} phi(d)*k^(n/d), where k = 2 is the maximum number of colors. - Robert A. Russell, Sep 24 2018
EXAMPLE
For n=6, the only chiral pair is AABABB-AABBAB. For n=7, the two chiral pairs are AAABABB-AAABBAB and AABABBB-AABBBAB. - Robert A. Russell, Sep 24 2018
MATHEMATICA
nn=35; Table[CoefficientList[Series[CycleIndex[CyclicGroup[n], s]-CycleIndex[DihedralGroup[n], s]/.Table[s[i]->2, {i, 1, n}], {x, 0, nn}], x], {n, 1, nn}]//Flatten (* Geoffrey Critzer, Mar 26 2013 *) mx=40; CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-2*x^n]/n, {n, mx}]-(1+x)^2/(1-2*x^2))/2, {x, 0, mx}], x] (* Herbert Kociemba, Nov 02 2016 *) terms = 36; a29[0] = 1; a29[n_] := (1/4)*(Mod[n, 2] + 3)*2^Quotient[n, 2] + DivisorSum[n, EulerPhi[#]*2^(n/#) & ]/(2*n); Array[a29, 36, 0] - LinearRecurrence[{0, 2}, {1, 2, 3}, 36] (* Jean-François Alcover, Nov 05 2017 *) k = 2; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/(2n)(k^Floor[(n+1)/2] + k^Ceiling[(n+1)/2])/4, {n, 1, 30}], 0] (* Robert A. Russell, Sep 24 2018 *)
T(n,k) is the number of non-equivalent distinguishing colorings of the cycle on n vertices with exactly k colors (k>=1). Regular triangle read by rows, n >= 1, 1 <= k <= n.
+10
6
0, 0, 0, 0, 0, 1, 0, 0, 3, 3, 0, 0, 12, 24, 12, 0, 1, 34, 124, 150, 60, 0, 2, 111, 588, 1200, 1080, 360, 0, 6, 315, 2484, 7845, 11970, 8820, 2520, 0, 14, 933, 10240, 46280, 105840, 129360, 80640, 20160, 0, 30, 2622, 40464, 254664, 821592, 1481760, 1512000, 816480, 181440
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. Two vertex-colorings of a graph are called equivalent if there is an automorphism of the graph which preserves the colors of the vertices. Given a graph G, we use the notation phi_k(G) to denote the number of non-equivalent distinguishing colorings of G with exactly k colors. The sequence here, displays T(n,k)=phi_k(C_n), i.e., the number of non-equivalent distinguishing colorings of the cycle C_n on n vertices with exactly k colors.
First differs from A305541 at n = 6. Also the number of n-bead asymmetric bracelets with exactly k different colored beads. More precisely the number of chiral pairs of primitive (aperiodic) color loops of length n with exactly k different colors. For example, for n=4 and k = 3, there are 3 achiral loops (1213, 1232, 1323) and 3 pairs of chiral loops (1123/1132, 1223/1322, 1233/1332).
(End)
FORMULA
Let n>2. For any k >= floor(n/2) we have phi_k(C_n)=k! * Stirling2(n,k)/2n.
EXAMPLE
The triangle begins:
0
0, 0;
0, 0, 1;
0, 0, 3, 3;
0, 0, 12, 24, 12;
0, 1, 34, 124, 150, 60;
0, 2, 111, 588, 1200, 1080, 360;
0, 6, 315, 2484, 7845, 11970, 8820, 2520;
0, 14, 933, 10240, 46280, 105840, 129360, 80640, 20160;
0, 30, 2622, 40464, 254664, 821592, 1481760, 1512000, 816480, 181440;
...
For n=4, we can color the vertices of the cycle C_4 with exactly 3 colors, in 3 ways, such that all the colorings distinguish the graph (i.e., no non-identity automorphism of C_4 preserves the coloring) and that all the three colorings are non-equivalent. The color classes are as follows:
{ { 1 }, { 2 }, { 3, 4 } }
{ { 1 }, { 2, 3 }, { 4 } }
{ { 1, 2 }, { 3 }, { 4 } }
PROG
U(n, k)={sumdiv(n, d, moebius(n/d)*(k^d/n - if(d%2, k^((d+1)/2), (k+1)*k^(d/2)/2)))/2}
T(n, k)={sum(i=2, k, (-1)^(k-i)*binomial(k, i)*U(n, i))} \\ Andrew Howroyd, Aug 12 2019
Number of chiral pairs of color loops of length n with integer entries that cover an initial interval of positive integers.
+10
4
0, 0, 1, 6, 48, 370, 3341, 33966, 393468, 5111100, 73753685, 1170469192, 20263758984, 380047816638, 7676106093049, 166114206920706, 3834434320842720, 94042629507775794, 2442147034668044933, 66942194905680941268, 1931543452344523778392, 58519191359156026158522
FORMULA
Inverse Moebius transform of A326888.
PROG
(PARI) a(n)={sum(k=1, n, -k!*(stirling((n+1)\2, k, 2) + stirling(n\2+1, k, 2))/4 + k!*sumdiv(n, d, eulerphi(d)*stirling(n/d, k, 2))/(2*n))} \\ Andrew Howroyd, Sep 13 2019
Number of chiral pairs of color loops of length n with exactly 3 different colors.
+10
3
0, 0, 1, 3, 12, 35, 111, 318, 934, 2634, 7503, 21071, 59472, 167229, 472133, 1333263, 3777600, 10721837, 30516447, 87035631, 248820816, 712751271, 2045784183, 5882388956, 16942974060, 48876617790, 141204945463, 408495109005, 1183247473872, 3431451145390, 9962348798055, 28953196894668
FORMULA
a(n) = -(k!/4)*(S2(floor((n+1)/2),k) + S2(ceiling((n+1)/2),k)) + (k!/(2n))*Sum_{d|n} phi(d)*S2(n/d,k), with k=3 different colors used and where S2(n,k) is the Stirling subset number A008277. G.f.: -(3/2) * x^4 * (1+x)^2 / Product_{j=1..3} (1-j*x^2) - Sum_{d>0} (phi(d)/(2d)) * (log(1-3x^d) - 3*log(1-2x^d) + 3*log(1-x^d)).
EXAMPLE
For a(4)=3, the chiral pairs of color loops are AABC-AACB, ABBC-ACBB, and ABCC-ACCB.
MATHEMATICA
k=3; Table[(k!/(2n)) DivisorSum[n, EulerPhi[#] StirlingS2[n/#, k] &] - (k!/4) (StirlingS2[Floor[(n+1)/2], k] + StirlingS2[Ceiling[(n+1)/2], k]), {n, 1, 40}]
PROG
(PARI) a(n) = my(k=3); -(k!/4)*(stirling(floor((n+1)/2), k, 2) + stirling(ceil((n+1)/2), k, 2)) + (k!/(2*n))*sumdiv(n, d, eulerphi(d)*stirling(n/d, k, 2)); \\ Michel Marcus, Jun 06 2018
Number of chiral pairs of color loops of length n with exactly 4 different colors.
+10
3
0, 0, 0, 3, 24, 124, 588, 2487, 10240, 40488, 158220, 609078, 2333520, 8895204, 33864364, 128793627, 490027200, 1865625340, 7110959340, 27138210888, 103717720000, 396965694444, 1521562700988, 5840509760582, 22450188684288, 86412088367640, 333035003543900, 1285108410802038, 4964755661788560, 19201631174055992
FORMULA
a(n) = -(k!/4)*(S2(floor((n+1)/2),k) + S2(ceiling((n+1)/2),k)) + (k!/(2n))*Sum_{d|n} phi(d)*S2(n/d,k), with k=4 different colors used and where S2(n,k) is the Stirling subset number A008277. G.f.: -6 * x^6 * (1+x)^2 / Product_{j=1..4} (1-j*x^2) - Sum_{d>0} (phi(d)/(2d)) * (log(1-4x^d) - 4*log(1-3x^3) + 6*log(1-2x^d) - 4*log(1-x^d)).
EXAMPLE
For a(4)=3, the chiral pairs of color loops are ABCD-ADCB, ACBD-ADBC, and ABDC-ACDB.
MATHEMATICA
k=4; Table[(k!/(2n)) DivisorSum[n, EulerPhi[#] StirlingS2[n/#, k] &] - (k!/4) (StirlingS2[Floor[(n+1)/2], k] + StirlingS2[Ceiling[(n+1)/2], k]), {n, 1, 40}]
PROG
(PARI) a(n) = my(k=4); -(k!/4)*(stirling(floor((n+1)/2), k, 2) + stirling(ceil((n+1)/2), k, 2)) + (k!/(2*n))*sumdiv(n, d, eulerphi(d)*stirling(n/d, k, 2)); \\ Michel Marcus, Jun 06 2018
Number of chiral pairs of color loops of length n with exactly 5 different colors.
+10
2
0, 0, 0, 0, 12, 150, 1200, 7845, 46280, 254676, 1344900, 6892425, 34646220, 171715050, 843004688, 4110478470, 19950471120, 96525524140, 466068873900, 2247609721431, 10832163963860, 52194011649150, 251522234238000, 1212501695554920, 5848043487355752, 28223528190496380, 136307124614215660, 658800774340433025, 3186621527711606940
FORMULA
a(n) = -(k!/4)*(S2(floor((n+1)/2),k) + S2(ceiling((n+1)/2),k)) + (k!/(2n))*Sum_{d|n} phi(d)*S2(n/d,k), with k=5 different colors used and where S2(n,k) is the Stirling subset number A008277. G.f.: -30 * x^8 * (1+x)^2 / Product_{j=1..5} (1-j*x^2) - Sum_{d>0} (phi(d)/(2d)) * (log(1-5x^d) - 5*log(1-4x^d) + 10*log(1-3x^3) - 10*log(1-2x^d) + 5*log(1-x^d)).
EXAMPLE
For a(5)=12, the chiral pairs of color loops are ABCDE-AEDCB, ABCED-ADECB, ABDCE-AECDB, ABDEC-ACEDB, ABECD-ADCEB, ABEDC-ACDEB, ACBDE-AEDBC, ACBED-ADEBC, ACDBE-AEBCD, ACEDB-ABDEC, ADBCE-AECBD, ADBEC-ACEBD, and ADCBE-AEBCD.
MATHEMATICA
k=5; Table[(k!/(2n)) DivisorSum[n, EulerPhi[#] StirlingS2[n/#, k] &] - (k!/4) (StirlingS2[Floor[(n+1)/2], k] + StirlingS2[Ceiling[(n+1)/2], k]), {n, 1, 40}]
PROG
(PARI) a(n) = my(k=5); -(k!/4)*(stirling(floor((n+1)/2), k, 2) + stirling(ceil((n+1)/2), k, 2)) + (k!/(2*n))*sumdiv(n, d, eulerphi(d)*stirling(n/d, k, 2)); \\ Michel Marcus, Jun 06 2018
Number of chiral pairs of color loops of length n with exactly 6 different colors.
+10
2
0, 0, 0, 0, 0, 60, 1080, 11970, 105840, 821592, 5873760, 39705630, 258121080, 1631169900, 10096542792, 61535329380, 370709045280, 2213740488600, 13132064237040, 77509384111278, 455754440462040, 2672268921657540, 15636049474529880, 91353538645037220, 533180401444362672
FORMULA
a(n) = -(k!/4)*(S2(floor((n+1)/2),k) + S2(ceiling((n+1)/2),k)) + (k!/(2n))*Sum_{d|n} phi(d)*S2(n/d,k), with k=6 different colors used and where S2(n,k) is the Stirling subset number A008277. G.f.: -180 * x^10 * (1+x)^2 / Product_{j=1..6} (1-j*x^2) - Sum_{d>0} (phi(d)/(2d)) * (log(1-6x^d) - 6*log(1-5x^d) + 15*log(1-4x^d) - 20*log(1-3x^3) + 15*log(1-2x^d) - 5*log(1-x^d)).
EXAMPLE
For a(6) = 60, we pair up the 5! = 120 permutations of BCDEF, each with its reversal. Then put an A before each to end up with 60 chiral pairs such as ABCDEF-AFEDCB.
MATHEMATICA
k=6; Table[(k!/(2n)) DivisorSum[n, EulerPhi[#] StirlingS2[n/#, k] &] - (k!/4) (StirlingS2[Floor[(n+1)/2], k] + StirlingS2[Ceiling[(n+1)/2], k]), {n, 1, 40}]
PROG
(PARI) a(n) = my(k=6); -(k!/4)*(stirling(floor((n+1)/2), k, 2) + stirling(ceil((n+1)/2), k, 2)) + (k!/(2*n))*sumdiv(n, d, eulerphi(d)*stirling(n/d, k, 2)); \\ Michel Marcus, Jun 06 2018
Search completed in 0.014 seconds
|