Don't take life too seriously: it's just a temporary situation

Collane (numeri di)

Matematica combinatoria 

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.

 

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

 

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

 

Raffigurazione delle collane differenti con 4 perline e fino a 4 colori

 

 

Il numero di collane è dato dalla formula Formula per il numero di collane con n perline e m colori, dove la somma va calcolata sui divisori di n; se n è un numero primo, la formula si riduce a Formula per il numero di collane con n perline e m colori, per n primo.

Il numero di collane è legato al numero di collane non periodiche C”(m, n) dalla formula Formula per il numero di collane con n perline e m colori, 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: Formula per il numero di collane con n perline e m colori, 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 Formula per il numero di collane con n perline di colori differenti e m colori, 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.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.