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

Permutazioni non decomponibili (numero di)

Matematica combinatoria 

Una permutazione di n elementi si dice “decomponibile” se esiste un intero m, minore di n, tale che i primi m elementi siano permutati tra loro. Una permutazione decomponibile è quindi composta da due permutazione separate, dei primi m elementi e dei restanti, dove gli esementi di ciascun gruppo restano separati.

Le permutazioni non decomponibili sono anche dette “permutazioni connesse”. Per esempio, il numero di permutazioni non decomponibili di 4 è 13, perché le permutazioni non decomponibili sono: { 2, 3, 4, 1 }, { 2, 4, 1, 3 }, { 2, 4, 3, 1 }, { 3, 1, 4, 2 }, { 3, 2, 4, 1 }, { 3, 4, 1, 2 }, { 3, 4, 2, 1 }, { 4, 1, 2, 3 }, { 4, 1, 3, 2 }, { 4, 2, 1, 3 }, { 4, 2, 3, 1 }, { 4, 3, 1, 2 } e { 4, 3, 2, 1 }. Non vale { 2, 1, 4, 3 }, perché inizia con una permutazione dei primi 2.

 

Il numero di permutazioni non decomponibili pn può essere calcolato con la ricorrenza p1 = 1, Ricorrenza per il calcolo del numero di permutazioni non decomponibili per n > 1.

Un’altra ricorrenza è p1 = 1, Ricorrenza per il calcolo del numero di permutazioni non decomponibili per n > 1 (R.J. Martin e M.J. Kearney, 2011).

 

Altre formule, di interesse puramente teorico, sono:

Formula per il calcolo del numero di permutazioni non decomponibili (R.J. Martin e M.J. Kearney, 2011);

Formula per il calcolo del numero di permutazioni non decomponibili.

 

Al crescere di n, pn tende a Limite asintotico cui tende il numero di permutazioni non decomponibili (Comtet, 1969), quindi “quasi tutte” le permutazioni sono non decomponibili.

 

I numeri di permutazioni non decomponibili sono tutti dispari.

 

I numeri di permutazioni non decomponibili primi noti sono: p3 = 3, p4 = 13, p5 = 71, p6 = 461, p22 = 1018705098450570562877 e p720 = 2593988282446862968430662827012261747659026947588421405778860907714811952299477143869924154225394194823430904896800535963114808433853741660250714238443857248975886189726328301939683652830259802714057263369657664439157251390310632004678931363974664199508428548209035425880472415600410534545829924427207913569344501027223488882411505476331854330308228081037542736706019119073822219206412200614981814958922524218267000413534381999445631697209301557132184023423357910747649652384667013332288241359180533615889204246456745988684062847091165168800564761028388099583685328388831775013742447152235633482472820242325833821835192381645078239837801047653572720730163265172157851029240325940791083662808968264984388889995233420030564307474629232518132531924571006022244819580382273292665253682046266908717941692712747889706874126105294558226194684093973225744314769153329231098616683135972069235717340634476570472834911634548496736448160076383908392835510553663143871175969612334875883683412149278289293636862404151098190877695062906949980430850847481883523867432743444987018795196040918868232764068673722130788646051163377933258128802769107182998087268771381187491695851031493407616984035270962901739391286297578807378673832098885923630919717771006343787580984260592568517105079072838799674235326626274378074408241388681093509801210214286866719829096018370559649294379817933857103093935336960711496142200654699296078006512093054543972637624271578613443449069517835069860791609030159363750542707666636553105144015526759640105551285194268418369868755453493435601359979953236382308675225502686106189359624202791058035579010810971008971151753015978931122133089701549885045730485162139713342230797663897342100249677408496117967228271933007979505863381854926087909; se ve ne sono altri, il loro indice è maggiore di 1000 (M. Fiorentini, 2014).

 

La tabella seguente mostra il numero di permutazioni non decomponibili di n, per n fino a 20.

n

pn

1

1

2

1

3

3

4

13

5

71

6

461

7

3447

8

29093

9

273343

10

2829325

11

31998903

12

392743957

13

5201061455

14

73943424413

15

1123596277863

16

18176728317413

17

311951144828863

18

5661698774848621

19

108355864447215063

20

2181096921557783605

 

Contattami

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