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

Partizioni non incrociate (numero di)

Matematica combinatoria 

Una partizione non incrociata di un insieme linearmente ordinato è una partizione nella quale gli elementi appartenenti a sottoinsiemi differenti non si “incrociano”, ovvero, se a e b appartengono a un sottoinsieme e x e y a un altro, non vi sono nell’insieme sottosequenze (composte anche da elementi non contigui) come a x b y.

Il numero di partizioni non incrociate di un insieme di n elementi è il numero di Catalan Cn.

Per esempio, vi sono C4 = 14 partizioni non incrociate di un insieme di 4 elementi { A, B, C, D }:

  • { A, B, C, D };

  • { A }, { B, C, D };

  • { B }, { A, C, D };

  • { C }, { A, B, D };

  • { D }, { A, B, C };

  • { A, B } { C, D };

  • { A, D } { B, C };

  • { A, B } { C }, { D };

  • { A, C } { B }, { D };

  • { A, D } { B }, { C };

  • { B, C } { A }, { D };

  • { B, D } { A }, { C };

  • { C, D } { A }, { B };

  • { A }, { B } { C }, { D }.

E’ esclusa la partizione { A, C } { B, D }, perché contiene un “incrocio”.

 

Il numero di partizioni non incrociate di un insieme di n elementi in k sottoinsiemi è il numero di Narayana N(n, k).

Per esempio, vi sono N(4, 2) = 6 partizioni non incrociate di un insieme di 4 elementi { A, B, C, D } in 2 sottoinsiemi:

  • { A }, { B, C, D };

  • { B }, { A, C, D };

  • { C }, { A, B, D };

  • { D }, { A, B, C };

  • { A, B } { C, D };

  • { A, D } { B, C }.

 

Il numero di partizioni non incrociate di un insieme di n elementi, nelle quali elementi consecutivi appartengono a sottoinsiemi diversi è il numero di Motzkin Mn – 1.

Per esempio, vi sono M4 = 9 partizioni del genere di un insieme di 5 elementi { A, B, C, D, E }:

  • { A }, { B }, { C }, { D }, { E };

  • { A }, { B }, { C, E }, { D };

  • { A }, { B, D }, { C }, { E };

  • { A }, { B, E }, { C }, { D };

  • { A, C }, { B }, { D }, { E };

  • { A, D }, { B, } { C }, { E };

  • { A, E }, { B }, { C }, { D };

  • { A, E }, { B, D }, { C };

  • { A, B, E }, { C }, { D }.

 

Il numero di partizioni non incrociate di un insieme in n sottoinsiemi, nelle quali elementi consecutivi appartengono a sottoinsiemi diversi è il numero di Schröder Sn – 1.

Per esempio, vi sono S2 = 6 partizioni del genere di un insieme di caratteri alfabetici a partire da A in 3 sottoinsiemi:

  • { A }, { B }, { C };

  • { A }, { B, D }, { C };

  • { A, C }, { B }, { D };

  • { A, D }, { B, } { C };

  • { A, E }, { B, D }, { C };

  • { A, B, E }, { C }, { D }.

Vedi anche

Numero di partizioni.

Contattami

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