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

Collane non periodiche (numeri di)

Matematica combinatoria 

Il numero di collane non periodiche C”(m, n) è il numero di collane distinte che si possono costruire con n perline di m colori diversi, non formate da due o più ripetizioni della stessa sequenza. Un modo equivalente di esprimere la condizione di non periodicità è che non deve esistere una rotazione minore di un giro intero che lasci la collana inalterata. Di conseguenza l’unica collana non periodica formata da perline dello stesso colore è quella formata da una sola perlina.

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.

 

La figura seguente mostra le collane differenti con 2 perline e fino a 5 colori.

 

Raffigurazione delle collane non periodiche 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 non periodiche differenti con 3 perline e fino a 4 colori

 

 

La figura seguente mostra le collane differenti con 4 perline e fino a 4 colori.

 

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

 

 

Il numero di collane non periodiche è dato dalla formula Formula per il numero di collane non periodiche 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 non periodiche con n perline e m colori, per n primo, dove C(m, n) è il numero di collane con n perline di m colori.

Il numero di collane non periodiche è legato al numero di collane C(m, n) dalla formula Formula per il numero di collane non periodiche con n perline e m colori, dove la somma va calcolata sui divisori di n.

 

Il numero di collane non periodiche C(m, n) è uguale al valore del polinomio delle collane M(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

1

1

2

3

4

5

2

0

1

3

6

10

3

0

2

8

20

40

4

0

3

18

60

150

5

0

6

48

204

624

6

0

9

116

670

2580

7

0

18

312

2340

11160

8

0

30

810

8160

48750

9

0

56

2184

29120

217000

10

0

99

5880

104754

976248

11

0

186

16104

381300

4438920

12

0

335

44220

1397740

20343700

13

0

630

122640

5162220

93900240

14

0

1161

341484

19172790

435959820

15

0

2182

956576

71582716

2034504992

16

0

4080

2690010

268431360

9536718750

17

0

7710

7596480

1010580540

44878791360

18

0

14532

21522228

3817733920

211927516500

19

0

27594

61171656

14467258260

1003867701480

20

0

52377

174336264

54975528948

4768371093720

n \ m

6

7

8

9

1

6

7

8

9

2

15

21

28

36

3

70

112

168

240

4

315

588

1008

1620

5

1554

3360

6552

11808

6

7735

19544

43596

88440

7

39990

117648

299592

683280

8

209790

720300

2096640

5380020

9

1119720

4483696

14913024

43046640

10

6045837

28245840

107370900

348672528

11

32981550

179756976

780903144

2852823600

12

181394535

1153430600

5726600880

23535749880

13

1004668770

7453000800

42288908760

195528140640

14

5597420295

48444446376

314146029564

1634056262280

15

31345665106

316504099520

2345624803704

13726075468992

16

176319264240

2077057800300

17592184995840

115813759112820

17

995685849690

13684147881600

132458812569720

981010688215680

18

5642219252460

90467419857752

1000799909722368

8338590828280440

19

32071565263710

599941851861744

7585009898729256

71097458824894320

20

182807918979777

3989613300756720

57646075176655056

607883272778506896

n \ m

10

11

12

1

10

11

12

2

45

55

66

3

330

440

572

4

2475

3630

5148

5

19998

32208

49764

6

166485

295020

497354

7

1428570

2783880

5118828

8

12498750

26793030

53745120

9

111111000

261994040

573308736

10

999989991

2593726344

6191711526

11

9090909090

25937424600

67546215516

12

83333249175

261535549220

743008120140

13

769230769230

2655593241840

8230246567620

14

7142856428565

27124986721140

91708459194066

15

66666666659934

278483211283552

1027134771622388

16

624999993750000

2871858103075830

11555266154065920

17

5882352941176470

29732178147017280

130506535690613940

18

55555555499944500

308884295062917420

1479074070873471072

19

526315789473684210

3218899497284976120

16814736808980154044

20

4999999999499999505

33637499745331128504

191687999619277886868

n \ m

13

14

15

1

13

14

15

2

78

91

105

3

728

910

1120

4

7098

9555

12600

5

74256

107562

151872

6

804076

1254435

1897840

7

8964072

15059070

24408480

8

101962770

184468830

320355000

9

1178277464

2295671560

4271484000

10

13785812040

28925411697

57664963104

11

162923672184

368142288150

786341441760

12

1941506688940

4724492067295

10812193870800

13

23298085122480

61054982558010

149707312950720

14

281241165925044

793714765724595

2085208989609360

15

3412392867581152

10371206370484778

29192926025339776

16

41588538022965570

136122083520848880

410525522071875000

17

508847995257725760

1793608631137129170

5795654431511374080

18

6247522607852670508

23715491899442676060

82105104444274758000

19

76943173177655058456

314542313628890231430

1166756747396368729440

20

950248188737147045928

4183412771249777343369

16626283650369421872480

n \ m

16

17

18

1

16

17

18

2

120

136

153

3

1360

1632

1938

4

16320

20808

26163

5

209712

283968

377910

6

2795480

4022064

5667681

7

38347920

58619808

87460002

8

536862720

871959240

1377481950

9

7635496960

13176430176

22039920504

10

109951057896

201599248032

357046533675

11

1599289640400

3115626937056

5842582734474

12

23456246655680

48551851084080

96402612275775

13

346430740566960

761890617915840

1601766528128550

14

5146970983535160

12026987582075856

26772383354990049

15

76861433640386288

190828203433892736

449776041098370870

16

1152921504338411520

3041324491793194440

7589970692848393200

17

17361641481138401520

48661191875666868480

128583032925805678350

18

262353693488939386880

781282469552728498992

2185911559727674682148

19

3976729669784964390480

12582759772902701307744

37275544492386193492506

20

60446290980676483150656

203211570332277826420896

637411810819625385355305

n \ m

19

20

1

19

20

2

171

190

3

2280

2660

4

32490

39900

5

495216

639996

6

7839780

10665270

7

127695960

182857140

8

2122929090

3199980000

9

35854187880

56888888000

10

613106378136

1023999679962

11

10590023536200

18618181818180

12

184442905990860

341333327986700

13

3234844881712080

6301538461538460

14

57071906063500860

117028571337142830

15

1012075135324821024

2184533333333119468

16

18027588346914850290

40959999998400000000

17

322375697516753069760

771011764705882352940

18

5784852794310472599780

14563555555527107556000

19

104127350297911241532840

275941052631578947368420

20

1879498672876991356348392

5242879999999487999992020

 

A parte i casi banali C”(p, 1) = p con p primo, i numeri di collane non periodiche primi sono rarissimi; gli unici inferiori a 101000 sono (M. Fiorentini, 2018):

C”(3, 2) = 3,

C”(2, 3) = 2,

C”(2, 4) = 3.

E’ possibile che non ve ne siano altri.

Contattami

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