Il numero di collane C(m, n) è il numero di collane distinte che si possono costruire con n perline di m colori diversi. Due collane si considerano uguali se possono essere fatte coincidere mediante una rotazione mentre si considerano distinte due collane che siano l’una l’immagine speculare dell’altra.
Una definizione alternativa è il numero di modi di colorare i vertici (o i lati) di un poligono di n lati con m colori, considerando distinte le immagini speculari.
La figura seguente mostra le collane differenti con 2 perline e fino a 4 colori.
La figura seguente mostra le collane differenti con 3 perline e fino a 4 colori.
La figura seguente mostra le collane differenti con 4 perline e fino a 3 colori.
Il numero di collane è dato dalla formula , dove la somma va calcolata sui divisori di n; se n è un numero primo, la formula si riduce a
.
Il numero di collane è legato al numero di collane non periodiche C”(m, n) dalla formula , dove la somma va calcolata sui divisori di n.
Fissato il numero di perline n, C(m, n) è un polinomio in m che si ottiene come somma dei polinomi delle collane: , dove la somma va calcolata sui divisori di n; e C(m, n) è un polinomio delle collane.
Le tabelle seguenti mostrano i valori di C(m, n), per m e n fino a 20.
n \ m |
1 |
2 |
3 |
4 |
5 |
1 |
1 |
2 |
3 |
4 |
5 |
2 |
1 |
3 |
6 |
10 |
15 |
3 |
1 |
4 |
11 |
24 |
45 |
4 |
1 |
6 |
24 |
70 |
165 |
5 |
1 |
8 |
51 |
208 |
629 |
6 |
1 |
14 |
130 |
700 |
2635 |
7 |
1 |
20 |
315 |
2344 |
11165 |
8 |
1 |
36 |
834 |
8230 |
48915 |
9 |
1 |
60 |
2195 |
29144 |
217045 |
10 |
1 |
108 |
5934 |
104968 |
976887 |
11 |
1 |
188 |
16107 |
381304 |
4438925 |
12 |
1 |
352 |
44368 |
1398500 |
20346485 |
13 |
1 |
632 |
122643 |
5162224 |
93900245 |
14 |
1 |
1182 |
341802 |
19175140 |
435970995 |
15 |
1 |
2192 |
956635 |
71582944 |
2034505661 |
16 |
1 |
4116 |
2690844 |
268439590 |
9536767665 |
17 |
1 |
7712 |
7596483 |
1010580544 |
44878791365 |
18 |
1 |
14602 |
21524542 |
3817763740 |
211927736135 |
19 |
1 |
27596 |
61171659 |
14467258264 |
1003867701485 |
20 |
1 |
52488 |
174342216 |
54975633976 |
4768372070757 |
n \ m |
6 |
7 |
8 |
9 |
1 |
6 |
7 |
8 |
9 |
2 |
21 |
28 |
36 |
45 |
3 |
76 |
119 |
176 |
249 |
4 |
336 |
616 |
1044 |
1665 |
5 |
1560 |
3367 |
6560 |
11817 |
6 |
7826 |
19684 |
43800 |
88725 |
7 |
39996 |
117655 |
299600 |
683289 |
8 |
210126 |
720916 |
2097684 |
5381685 |
9 |
1119796 |
4483815 |
14913200 |
43046889 |
10 |
6047412 |
28249228 |
107377488 |
348684381 |
11 |
32981556 |
179756983 |
780903152 |
2852823609 |
12 |
181402676 |
1153450872 |
5726645688 |
23535840225 |
13 |
1004668776 |
7453000807 |
42288908768 |
195528140649 |
14 |
5597460306 |
48444564052 |
314146329192 |
1634056945605 |
15 |
31345666736 |
316504102999 |
2345624810432 |
13726075481049 |
16 |
176319474366 |
2077058521216 |
17592187093524 |
115813764494505 |
17 |
995685849696 |
13684147881607 |
132458812569728 |
981010688215689 |
18 |
5642220380006 |
90467424361132 |
1000799924679192 |
8338590871415805 |
19 |
32071565263716 |
599941851861751 |
7585009898729264 |
71097458824894329 |
20 |
182807925027504 |
3989613329006536 |
57646075284033552 |
607883273127192897 |
n \ m |
10 |
11 |
12 |
1 |
10 |
11 |
12 |
2 |
55 |
66 |
78 |
3 |
340 |
451 |
584 |
4 |
2530 |
3696 |
5226 |
5 |
20008 |
32219 |
49776 |
6 |
166870 |
295526 |
498004 |
7 |
1428580 |
2783891 |
5118840 |
8 |
12501280 |
26796726 |
53750346 |
9 |
111111340 |
261994491 |
573309320 |
10 |
1000010044 |
2593758618 |
6191761368 |
11 |
9090909100 |
25937424611 |
67546215528 |
12 |
83333418520 |
261535848376 |
743008623292 |
13 |
769230769240 |
2655593241851 |
8230246567632 |
14 |
7142857857190 |
27124989505086 |
91708464312972 |
15 |
66666666680272 |
278483211316211 |
1027134771672736 |
16 |
625000006251280 |
2871858129872556 |
11555266207816266 |
17 |
5882352941176480 |
29732178147017291 |
130506535690613952 |
18 |
55555555611222370 |
308884295325206986 |
1479074071447277812 |
19 |
526315789473684220 |
3218899497284976131 |
16814736808980154056 |
20 |
5000000000500012024 |
33637499747924890752 |
191687999625469653384 |
n \ m |
13 |
14 |
15 |
1 |
13 |
14 |
15 |
2 |
91 |
105 |
120 |
3 |
741 |
924 |
1135 |
4 |
7189 |
9660 |
12720 |
5 |
74269 |
107576 |
151887 |
6 |
804895 |
1255450 |
1899080 |
7 |
8964085 |
15059084 |
24408495 |
8 |
101969959 |
184478490 |
320367720 |
9 |
1178278205 |
2295672484 |
4271485135 |
10 |
13785886387 |
28925519364 |
57665115096 |
11 |
162923672197 |
368142288164 |
786341441775 |
12 |
1941507500933 |
4724493332300 |
10812195782480 |
13 |
23298085122493 |
61054982558024 |
149707312950735 |
14 |
281241174889207 |
793714780783770 |
2085209014017960 |
15 |
3412392867656149 |
10371206370593264 |
29192926025492783 |
16 |
41588538124935529 |
136122083705327370 |
410525522392242720 |
17 |
508847995257725773 |
1793608631137129184 |
5795654431511374095 |
18 |
6247522609031752867 |
23715491901739603070 |
82105104448548141080 |
19 |
76943173177655058469 |
314542313628890231444 |
1166756747396368729455 |
20 |
950248188750932939413 |
4183412771278702872288 |
16626283650427087000176 |
n \ m |
16 |
17 |
18 |
1 |
16 |
17 |
18 |
2 |
136 |
153 |
171 |
3 |
1376 |
1649 |
1956 |
4 |
16456 |
20961 |
26334 |
5 |
209728 |
283985 |
377928 |
6 |
2796976 |
4023849 |
5669790 |
7 |
38347936 |
58619825 |
87460020 |
8 |
536879176 |
871980201 |
1377508284 |
9 |
7635498336 |
13176431825 |
22039922460 |
10 |
109951267744 |
201599532153 |
357046911756 |
11 |
1599289640416 |
3115626937073 |
5842582734492 |
12 |
23456249468976 |
48551855128737 |
96402617971728 |
13 |
346430740566976 |
761890617915857 |
1601766528128568 |
14 |
5146971021883216 |
12026987640695817 |
26772383442450222 |
15 |
76861433640597376 |
190828203434178353 |
449776041098750736 |
16 |
1152921504875290696 |
3041324492665174641 |
7589970694225901484 |
17 |
17361641481138401536 |
48661191875666868497 |
128583032925805678368 |
18 |
262353693496577680816 |
781282469565908953017 |
2185911559749720272442 |
19 |
3976729669784964390496 |
12582759772902701307761 |
37275544492386193492524 |
20 |
60446290980786434434720 |
203211570332479425973857 |
637411810819982432293224 |
n \ m |
19 |
20 |
1 |
19 |
20 |
2 |
190 |
210 |
3 |
2299 |
2680 |
4 |
32680 |
40110 |
5 |
495235 |
640016 |
6 |
7842250 |
10668140 |
7 |
127695979 |
182857160 |
8 |
2122961770 |
3200020110 |
9 |
35854190179 |
56888890680 |
10 |
613106873542 |
1024000320168 |
11 |
10590023536219 |
18618181818200 |
12 |
184442913865600 |
341333338694740 |
13 |
3234844881712099 |
6301538461538480 |
14 |
57071906191197010 |
117028571520000180 |
15 |
1012075135325318539 |
2184533333333762144 |
16 |
18027588349037812060 |
40960000001600020110 |
17 |
322375697516753069779 |
771011764705882352960 |
18 |
5784852794346334629910 |
14563555555584007112140 |
19 |
104127350297911241532859 |
275941052631578947368440 |
20 |
1879498672877604463254424 |
5242880000000512000352088 |
A parte i casi banali C(p, 1) = p con p primo, i numeri di colane primi sono rarissimi; gli unici inferiori a 101000 sono (M. Fiorentini, 2018):
C(3, 3) = 11,
C(5, 15) = 2034505661,
C(31, 31) = 550618520345910837374536871905139185678862431,
C(31, 217) = 1945484738011463598783866154765136005408698659971399713195116422610637560398299812681465716983625126091098044984877495820284081358864296926132842969178451534857538395161662390482707178534396321591896617906033117060769535601502411280477196444631736570505436771387796776894810799450705571253267100746431032112325829379287071.
Il numero di collane con perline tutte diverse tra loro è dato dalla formula , per m ≥ n.
Le tabelle seguenti mostrano i valori di C’(m, n), per m e n fino a 20.
n \ m |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
2 |
0 |
1 |
3 |
6 |
10 |
15 |
21 |
28 |
36 |
45 |
3 |
0 |
0 |
2 |
8 |
20 |
40 |
70 |
112 |
168 |
240 |
4 |
0 |
0 |
0 |
6 |
30 |
90 |
210 |
420 |
756 |
1260 |
5 |
0 |
0 |
0 |
0 |
24 |
144 |
504 |
1344 |
3024 |
6048 |
6 |
0 |
0 |
0 |
0 |
0 |
120 |
840 |
3360 |
10080 |
25200 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
720 |
5760 |
25920 |
86400 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5040 |
45360 |
226800 |
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
40320 |
403200 |
10 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
362880 |
n \ m |
11 |
12 |
13 |
14 |
15 |
1 |
11 |
12 |
13 |
14 |
15 |
2 |
55 |
66 |
78 |
91 |
105 |
3 |
330 |
440 |
572 |
728 |
910 |
4 |
1980 |
2970 |
4290 |
6006 |
8190 |
5 |
11088 |
19008 |
30888 |
48048 |
72072 |
6 |
55440 |
110880 |
205920 |
360360 |
600600 |
7 |
237600 |
570240 |
1235520 |
2471040 |
4633200 |
8 |
831600 |
2494800 |
6486480 |
15135120 |
32432400 |
9 |
2217600 |
8870400 |
28828800 |
80720640 |
201801600 |
10 |
3991680 |
23950080 |
103783680 |
363242880 |
1089728640 |
11 |
3628800 |
43545600 |
283046400 |
1320883200 |
4953312000 |
12 |
0 |
39916800 |
518918400 |
3632428800 |
18162144000 |
13 |
0 |
0 |
479001600 |
6706022400 |
50295168000 |
14 |
0 |
0 |
0 |
6227020800 |
93405312000 |
15 |
0 |
0 |
0 |
0 |
87178291200 |
n \ m |
16 |
17 |
18 |
1 |
16 |
17 |
18 |
2 |
120 |
136 |
153 |
3 |
1120 |
1360 |
1632 |
4 |
10920 |
14280 |
18360 |
5 |
104832 |
148512 |
205632 |
6 |
960960 |
1485120 |
2227680 |
7 |
8236800 |
14002560 |
22913280 |
8 |
64864800 |
122522400 |
220540320 |
9 |
461260800 |
980179200 |
1960358400 |
10 |
2905943040 |
7057290240 |
15878903040 |
11 |
15850598400 |
44910028800 |
115482931200 |
12 |
72648576000 |
247005158400 |
741015475200 |
13 |
268240896000 |
1140023808000 |
4104085708800 |
14 |
747242496000 |
4234374144000 |
19054683648000 |
15 |
1394852659200 |
11856247603200 |
71137485619200 |
16 |
1307674368000 |
22230464256000 |
200074178304000 |
17 |
0 |
20922789888000 |
376610217984000 |
18 |
0 |
0 |
355687428096000 |
n \ m |
19 |
20 |
1 |
19 |
20 |
2 |
171 |
190 |
3 |
1938 |
2280 |
4 |
23256 |
29070 |
5 |
279072 |
372096 |
6 |
3255840 |
4651200 |
7 |
36279360 |
55814400 |
8 |
380933280 |
634888800 |
9 |
3724680960 |
6772147200 |
10 |
33522128640 |
67044257280 |
11 |
274271961600 |
609493248000 |
12 |
2011327718400 |
5028319296000 |
13 |
12996271411200 |
37132204032000 |
14 |
72407797862400 |
241359326208000 |
15 |
337903056691200 |
1351612226764800 |
16 |
1267136462592000 |
6335682312960000 |
17 |
3577797070848000 |
23851980472320000 |
18 |
6758061133824000 |
67580611338240000 |
19 |
6402373705728000 |
128047474114560000 |
20 |
0 |
121645100408832000 |
A parte i casi banali C’(p, 1) = p con p primo, l’unico numero della forma C’(m, n) primo è C’(3, 2) = 3.