B15:f.01 Consideriamo due interi positivi k ed s e un insieme di k oggetti A = {a1, ..., ak} da pensare distinguibili e semplici; A potrebbe essere un alfabeto.
Le sequenze di lunghezza s di elementi sopra A, cio`e gli elementi della potenza cartesiana s-esima di A A×s, le chiamiamo anche disposizioni con ripetizioni di lunghezza s sopra A.
Le sequenze binarie si possono considerare come casi particolari di queste configurazioni riguardanti il semplice alfabeto {0, 1} formato da k = 2 caratteri.
Per disporre di scritture omogenee con altre notazioni che stiamo per introdurre, denoteremo l’insieme delle disposizioni con ripetizioni di lunghezza s su A anche con la notazione DspsrA,s; possiamo quindi scrivere DspsrA,s := A×s.
Per il loro numero introduciamo anche la notazione
DspsrNA,s := A×s .
Segnaliamo che a notazioni come DspsrA,s e DspsrNA,s, quando l’argomento A o l’argomento s devono essere dati da espressioni elaborate, sono preferibili notazioni come Dspsr[A, s] e DspsrN[A, s] da consi-derare sinonime, risp., alle precedenti.
(1) Prop.: Il numero delle disposizioni con ripetizioni di lunghezza s su A `e DspsrNA,s = |A|s = ks .
Dim.: Basta descrivere come si pu`o procedere alla costruzione della totalit`a delle sequenze in esame. Descriviamo queste come sequenze o allineamenti di s “scatole” in ciascuna delle quali si pu`o collocare una copia di un carattere appartenente all’alfabeto A. In ciascuna scatola di un allineamento si pu`o porre uno qualsiasi dei k caratteri dell’alfabeto, indipendentemente dai caratteri che sono presenti nelle altre posizioni. Nella prima posizione si possono porre k caratteri, per le prime due posizioni si hanno k2possibili scelte, nelle prime 3 k3 e cos`ı via. Dunque | A×s | = | A |s
Va ricordato che il segno introdotto sopra abbrevia l’espressione latina “quod erat demonstrandum” (abbreviata con QED), o la equivalente “come dovevasi dimostrare”; esso viene usato preferibilmente per segnalare la conclusione di ogni dimostrazione.
Evidentemente l’espressione precedente generalizza l’espressione 2strovata in d04 per il numero delle sequenze binarie di lunghezza s.
Segnaliamo anche la possibilit`a di descrivere visivamente mediante una delle arborescenze che sono presentate in D30c04 per l’organizzazione del processo costruttivo di tutte le sequenze, processo che si pu`o leggere tra le righe della dimostrazione precedente.
B15:f.02 Vediamo alcuni esempi di situazioni chiarite dal risultato precedente.
L’insieme delle notazioni decimali di interi naturali s = 3 cifre, quando per gli interi minori di 100 si chiedono scritture con zeri iniziali come per tanti contatori, `e Dspsr10,3e quindi consiste, non sorprend-entemente, di 103 elementi.
Le scritture decimali formate da 4 cifre dispari costituiscono l’insieme Dspsr{1,3,5,7,9},4il cui cardinale `e 54= 625. Pu`o essere significativo confrontare questo valore con il numero dei numeri interi compresi tra 1 000 e 9 999 che ammonta a 8 000.
Il numero delle stringhe di 3 caratteri, i trigrammi, sull’alfabeto di 26 caratteri `e 263= 17 576 , mentre le stringhe di lunghezza 26 su un alfabeto di 3 caratteri sono molte di pi`u, 326= 2 541 865 828 329 .
A questo proposito segnaliamo che si dimostra che se k ed n sono interi con 2 ≤ k < n si ha l’implicazione k < n =⇒ nk< kn con sole due eccezioni.
In particolare si dimostra senza difficolt`a che n > 2 =⇒ n + 1n< nn+1e che 1 ≤ h =⇒ (n+h)n< nn+h. `
E significativa anche la seguente tabellina dell’esponente con le eccezioni in evidenza.
2 3 4 5 6 7 8 9 10 2 4 8< 16= 32 64 128 256 512 1024 3 9> 27 81 243 729 2187 6561 19683 59049 4 16= 64 256 1024 4096 16384 65536 262144 1048576 5 25 125 625 3125 15625 78125 390626 1953125 9765625 6 36 216 1296 7776 46656 279936 1679616 10077696 60466176 7 49 343 2401 16807 117649 82353 5764801 40353607 282475249 8 64 512 4096 32768 262144 2097152 16777216 134217728 1073741824 9 81 729 6561 59049 531441 4782969 43046721 387420489 3486784401 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 10000000000 Si osserva che quando i parametri s e k non sono piccoli gli insiemi della forma DspsrA,s sono molto estesi e presentano elementi ciascuno dei quali piuttosto simile a molti altri.
In effetti tali insiemi interessano soprattutto in quanto definiscono ambienti nei quali conviene collocare come sottoinsiemi degli insiemi di oggetti (sequenze) pi`u specifici, cio`e dotati di propriet`a che li rendono adatti per applicazioni specifiche e quindi presentino buoni motivi di interesse applicativo.
Gi`a nei paragrafi che seguono avremo modo di incontrare alcuni di questi insin particolare in D20 e D33.
Ricordiamo anche che rivestono interesse, in particolare per precisare algoritmi e programmi, i proce-dimenti che consentono di passare in rassegna tutte le sequenze di insiemi estesi e poco differenziati come DspsrA,s. Procedimenti di questo genere sono chiamati procedure di visita; ne incontreremo altri, per esempio in B21j, D30 e C14f.
B15:f.03 Alcune considerazioni sui nomi usati per gli elementi di un insieme della forma DspsrNA,s. Con il termine “disposizioni con ripetizioni” non si intende escludere che le componenti di una di tali sequenze siano tutte diverse: a Dspsr8,4 appartengono stringhe come 1234, 2468 e 3574. Il termine pi`u corretto, ma pi`u prolisso, “disposizioni con la possibilit`a di ripetizioni”, non sembra sia usato. Per queste sequenze sono solitamente usate denominazioni diverse da quella qui proposta. Nella mag-gior parte dei testi si usano termini come “disposizioni con ripetizioni di elementi di A di classe s”. La dizione qui preferita intende assegnare al parametro s il ruolo ben definito e ampiamente utilizzabile di lunghezza di una sequenza, mentre l’altra dizione si serve del termine “classe” che in matematica viene usato per oggetti, purtroppo pi`u d’uno, che nulla hanno a che fare con le semplici configurazioni qui esaminate (classe di equivalenza, classe come parametro che esprime un livello di complessit`a, classe entit`a che generalizza la nozione di insieme per la quale qui preferiamo usare il termine classe:E. Un’altra denominazione usata `e “disposizioni con ripetizioni di elementi di A presi ad s ad s”; qui viene giudicata meno chiara di quella che ricorre alla lunghezza.
Preferenze analoghe rispetto a nomi pi`u diffusi saranno adottate per le configurazioni combinatorie che seguono, in quanto tutte possono vedersi come sequenze di stringhe o di oggetti appartenenti a un insieme finito caratterizzate da una determinata propriet`a peculiare e in ogni caso caratterizzabili con la loro lunghezza.
Quando l’insieme A `e l’insieme di numeri positivi {1, 2, ..., k} useremo le notazioni Dspsrk,s e DspsrNk,s o le rispettive equivalenti Dspsr[k, s] e DspsrN[k, s] .
B15:f.04 Le notazioni DspsrA,s e DspsrNA,s si possono vedere come esempi di notazioni formate da una sigla di lettere (ma useremo anche qualche cifra e qualche altro segno) seguita da parametri o da semplici espressioni che possono essere attribuiti a tipi ben definiti in precedenza.
La sigla vuole essere una abbreviazione di un termine caratterizzante e i parametri intendono indivi-duare in modo completo l’insieme degli oggetti definiti.
Nella presente esposizione viene adottato ampiamente questo genere di notazioni.
Queste notazioni che intendono essere precise ed esaurienti vogliono poter essere usate come identificatori globali delle entit`a che denotano, utilizzabili anche in contesti lontani da quelli in cui vengono definiti. Esse per`o sono piuttosto impegnative alla scrittura e alla lettura.
In contesti nei quali gli insiemi identificati sono frequentemente citate conviene poterle individuare anche con notazioni locali pi`u concise e maneggevoli.
In particolare in molti contesti in luogo di Dspsrk,s e DspsrNk,s si usano le notazioni D0k,s e D0k,s che evidentemente consentono di presentare formule ed espressioni pi`u nitide.
In effetti `e evidente che se si facesse assumere visibilit`a globale a una notazione concisa si rischierebbero momenti di bassa distinguibilit`a e possibili confusioni.
Per esempio potrebbe accadere che una notazione come D0[k, s] vengano percepita come la derivata di una funzione bivariata.
Le notazioni globali tendono ad assumere il ruolo di notazioni standard. Ci`o nonostante risulta oppor-tuno usarle con una certa elasticit`a. Abbiamo gi`a visto che in certi contesti si usa un identificatore di insieme per identificare anche il suo cardinale.
Pu`o anche accadere di individuare insiemi di sequenze appartenenti a un insieme della forma DspsrA,s
nel quale A e/o s devono essere individuate da espressioni elaborate; in questi casi conviene utilizzare una notazione nella quale queste espressioni non sono costrette a stare a deponente, ma possono collocarsi entro una coppia di parentesi specifiche da usare come delimitatori di espressioni. Per esempio si potrebbero usare notazioni come
Dspsr−E ˙∪ (F ∩ G) , 3 n3+ 4 n2+ 12 o DspsrN− E \ (F ∪ G) , m! + n2+ 144 m + 12 |K| . Non sono rare le situazioni nelle quali si rendano necessarie notazioni della forma sigla(specificazioni) con 3 o pi`u specificazioni.
Per queste notazioni talora pu`o essere opportuno adottare semplificazioni locali nelle quali qualche parametro viene meramente ignorato negli sviluppi sui quali non ha alcuna influenza, confidando che tale abbreviazione sia capita dal lettore anche in assenza di dichiarazione esplicita. In molti di questi casi sarebbe per`o preferibile introdurre una variante tipografica della sigla in gioco.questi
Nei casi di 3 o pi`u specificazioni entro una coppia parentesi pu`o risultare vantaggioso servirsi di diversi separatori e anche di successivi nidi delimitati da diverse coppie di parentesi coniugate.
Infine segnaliamo che in presenza di parecchie specificazioni pu`o essere conveniente presentarle non mediante una loro sequenza ma con notazioni che si estendono in due bidimensioni. In particolare si usano delle matrici e tabelle simili per le funzioni ipergeometriche e per coefficienti associati a rotazioni di sistemi studiati dalla meccanica quantistica.
B15:f.05 Iniziamo ora a occuparci di sequenze che sono disposizioni con ripetizione che devono sott-ostare a vincoli tendenzialmente semplici. Anche per questi insiemi di configurazioni daremo le carat-teristiche principali ed in particolare le espressioni dei loro cardinali.
Le sequenze di data lunghezza s le cui componenti appartengono ad un insieme definito A = {a1, ..., ak} e che non presentano componenti ripetuti, sono dette anche disposizioni [senza ripetizioni] di lunghezza s dei k oggetti a1, ..., ak.
Il loro insieme lo denotiamo con DspsA,s e per il loro numero scriviamo DspsNk,s := |DspsA,s| . Nel caso l’insieme A sia l’insieme dei primi k interi positivi useremo la notazione pi`u semplice Dspsk,s := Dsps(k],s e per il loro cardinale introduciamo DspsNk,s := DspsN(k],s.
Alcuni esempi
Dsps{a,b,c,d},2 = {ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc} ; Dsps{a,b,c,d},3 = {abc, abd, acb, acd, adb, adc,
bac, bad, bca, bcd, bda, bdc, cab, cad, cba, cbd, cda.cdb, dab, dac, dba, dbc, dca, dcb} B15:f.06 Segnaliamo che in luogo della denominazione “disposizioni senza ripetizioni” comunemente si usano termini come “disposizioni ad s ad s” e “disposizioni di classe s” e che talora si parla di “disposizioni semplici”.
Anche per le notazioni utilizzate per le disposizioni senza ripetizioni valgono considerazioni simili a quelle svolte in f04.
Una lista che rappresenta DspsA,s si pu`o ottenere scorrendo una lista che presenta il pi`u esteso insieme di sequenze DspsrA,se per ciascuna di esse stabilire se presenta o meno qualche componente ripetuta e conseguentemente rifiutarla o mantenerla. Troveremo tuttavia un procedimento meno inefficiente che permette di individuare le permutazioni senza ripetizioni in modo pi`u diretto.
B15:f.07 (1) Prop.: Il numero delle delle disposizioni senza ripetizioni di lunghezza s degli elementi dell’insieme A = {a1, a2, ..., ak} `e dato da
(1) DspsNA,s = k · (k − 1) · ... · (k − s + 1) .
Dim.: Pensiamo ancora di procedere alla costruzione di tutte le sequenze di DspsNA,s. Per occupare la prima posizione si pu`o scegliere liberamente uno dei k elementi di A; per la seconda posizione la scelta `
e ridotta ai k − 1 elementi di A diversi dal primo scelto, per la terza si hanno k − 2 possibili scelte e cos`ı via; chiaramente per la s-esima posizione rimangono solo k − s + 1 possibilit`a
Per il secondo membro della (1) si usano anche le due seguenti notazioni chiamate, risp., fattoriale decrescente dall’intero k per s passi
(2) ks := k · (k − 1) · ... · (k − s + 1) = s Y i=1 (k − i + 1) = s−1 Y i=0 (k − i) e fattoriale crescente dall’intero h per s passi
(3) hs := h(h + 1) · · · (h + s − 1) = s Y i=1 (h + i − 1) = s−1 Y i=0 (h + i) . Si pu`o quindi enunciare
(4) DspsNk,s = ks = (k − s + 1)s .
Conviene segnalare esplicitamente che
Conviene ricordare che oltre alle precedenti notazioni ne sono usate molte altre; per esempio invece della ks si usa spesso la scrittura (k)s chiamata, un po’ impropriamente, simbolo di Pochhammer. Nella dimostrazione della (1) abbiamo anche mostrato come, dati l’insieme A di k elementi e il numero s, se s ≤ k risulta possibile costruire tutte le sequenze costituenti DspsNA,s. `E anche evidente che se s < k non si possono avere sequenze di elementi di A senza componenti ripetute. Si pu`o quindi affermare che si hanno disposizioni senza ripetizioni di lunghezza s di k oggetti sse s ≤ k.
Osserviamo anche che le disposizioni senza ripetizioni di lunghezza s sull’insieme A si possono consi-derare anche come le funzioni da (s] in A che sono invertibili. In effetti abbiamo gi`a visto che ogni funzione finita `e invertibile sse la sequenza dei valori che assume non presenta ripetizioni.
B15:f.08 Quando s = k le disposizioni senza ripetizioni di elementi di A sono le sequenze che presentano ciascuno dei k = s valori una e una sola volta, cio`e esprimono le permutazioni degli elementi di A. L’insieme delle permutazioni di A si denota con PermA e si pu`o scrivere
Per ogni insieme finito A si pone PermA := DspsA,|A| . Il numero di queste permutazioni quindi `e evidentemente
(1) |Permk| = k! :=
k
Y
i=1
i = 1k = kk .
Qui abbiamo introdotta l’espressione k! che si legge fattoriale dell’intero naturale k, detto anche in breve k fattoriale.
Osserviamo anche che eliminando l’ultimo componente delle permutazioni di A si ottengono esatta-mente le disposizioni senza ripetizioni degli elementi di A di lunghezza |A| − 1; questa manovra di eliminazione quindi individua una biiezione tra PermAe DspsA,|A|−1. In effetti si trasforma una dispo-sizione senza ripetizione di |A| − 1 elementi di A in una permutazione di A aggiungendole un elemento la cui scelta `e obbligata.
Come si `e gi`a detto, le permutazioni di un insieme finito sono configurazioni discrete estremamente importanti che incontreremo in molte delle pagine che seguono e in particolare in B41, D35, D48 e D63. B15:f.09 Si osserva che gli anagrammi di una parola w che non presenta lettere ripetute si pu`o dire che costituiscono le permutazioni dei caratteri che si incontrano nella stessa w.
Si possono quindi trovare facilmente i numeri degli anagrammi di parole come parole, dante, rem-brandt, bach, mozart e gandhi.
Le permutazioni consentono di valutare i numeri di situazioni come le seguenti:
le diverse modalit`a di far sedere a un lato di una lunga tavola con s posti i membri di un gruppo di s persone;
i diversi modi di collocare s libri sopra uno scaffale destinato a questi soli libri;
i diversi modi di disporre le 40 carte di un mazzo usuale in uno schieramento di 4 file di dieci carte ciascuna;
i diversi modi di depositare sopra un binario morto 7 carrozze ferroviarie.
B15:f.10 Altri casi particolari di disposizioni con ripetizioni sono le combinazioni con ripetizioni. Per introdurre queste sequenze, occorre presentare l’insieme A = {a1, ..., ak} con gli elementi ordinati secondo un ordinamento totale che in linea di principio pu`o scegliersi ad arbitrio, ma che nell’ambito di certe applicazioni viene imposto da una convenzione o viene privilegiato dalla consuetudine.
Conveniamo di esprimere la relazione di precedenza tra gli elementi di A con il segno ≺ e stabiliamo che valga la catena di relazioni a1≺ a2≺ ... ≺ ak .
In particolare pu`o essere vantaggioso assumere che A sia l’insieme dei primi k interi positivi (k] con-siderati nel solito ordine crescente, cio`e si pu`o assumere che ≺ sia la relazione numerica <; inoltre scriviamo a b per esprimere che “aut a ≺ b aut a = b”.
Diciamo combinazione con ripetizioni di lunghezza s dei k oggetti di A, ogni sequenza haj1, aj2, ..., ajsi tale che aj1 aj2 ... ajs .
L’insieme di tali sequenze lo denotiamo con CombrA,so con Combr[A, s] e il loro numero con CombrNA,s
o con CombrN[A, s].
Nel caso dei primi s interi positivi scriviamo pi`u semplicemente
Combrk,s := Combr{1,2,...,k},s e CombrNk,s := |Combrk,s| . Per esempio le combinazioni con ripetizioni di lunghezza 3 degli interi 1, 2 e 3 sono:
111 112 113 122 123 133 222 223 233 333 ; Abbiamo invece
Combr4,3 = {111 , 112 , 113 , 114 , 122 , 123 , 124 , 133 , 134 , 144 , 222 , 223 , 224 , 233 , 234 , 244 , 333 , 334 , 344 , 444} .
B15:f.11 Si osserva che le combinazioni con ripetizioni di una data lunghezza s degli elementi di un insieme A dotato di un ordine totale si possono interpretare come funzioni da (s] in A nondecrescenti. In effetti le combinazioni con ripetizioni di interi positivi precedentemente usate come esempi sono state presentate come stringhe nondecrescenti di interi.
Si osserva inoltre che per l’insieme delle funzioni finite nondecrescenti di (s] in A si trovano facilmente due biiezioni con l’insieme delle funzioni finite noncrescenti di (s] in A. Per esse conviene dare due trasformazioni involutive applicabili a tutte le funzioni costituenti {(s] 7−→ A} definendole con le loro rispettive azioni sopra una funzione f ∈ {(s] 7−→ A} che rappresentiamo con la sequenza φ = ha1, a2, ..., as−1, asi.
Definiamo come funzione riflessa della funzione a dominio finito f e scriviamo f← la funzione che si rappresenta con la sequenza riflessa della precedente φ← = has, as−1, ..., a2, a1i .
Definiamo funzione complementare della funzione a valori interi limitati f ∈ {(s] 7−→ (k]} e scriviamo fcmpl la funzione che si rappresenta con la sequenza complementare della precedente
φcmpl := hk + 1 − a1, k + 1 − a2, ..., k + 1 − as−1, k + 1 − asi .
Per esempio la funzione riflessa della h1, 2, 2, 3, 5, 7i `e la h7, 5, 3, 2, 2, 1i e la complementare nell’ambito di {(6] 7−→ (8]} `e h8, 7, 7, 6, 4, 2i .
Evidentemente queste trasformazioni sono due involuzioni (e quindi sono particolari permutazioni) applicabili all’insieme delle funzioni tra i due insiemi ordinati (s] e A = (k].
Conviene segnalare che queste involuzioni si collegano significativamente alle due endofunzioni che trasformano nell’opposto l’ordine di (s] e l’ordine di A = (k]. Introduciamo per esse le notazioni locali
JA := ai∈ A ak−i+1 e Js := i k + 1 − i .
Chiaramente la prima `e una involuzione entro il dominio (s] e la seconda una involuzione entro il codominio A ed entrambe trasformano l’ordinamento dell’insieme sul quale agiscono nell’opposto.
Si verificano facilmente le due espressioni f← = y 1 2 ... s − 1 s as as−1 ... 2 1 y = Js◦lrf = f ◦lrJA .
Si constata inoltre che entrambe le involuzioni scambiano le funzioni crescenti con le funzioni decrescenti e scambiano le funzioni nondecrescenti con le funzioni noncrescenti.
Quindi in particolare sia il numero delle funzioni nondecrescenti che il numero delle funzioni noncre-scenti di {(s] 7−→ A = (k]} sono dati da CombrNk,s.
B15:f.12 Insiemi di sequenze pi`u ridotti degli insiemi di combinazioni con ripetizioni sono gli insiemi delle sequenze che chiamiamo combinazioni senza ripetizioni. Queste spesso sono chiamate “combinazioni semplici”, mentre in contesti nei quali non si temono ambiguit`a esse vengono anche dette semplicemente combinazioni.
Pi`u precisamente diciamo combinazione [senza ripetizioni] di lunghezza s di elementi dell’insieme A = {a1, a2, ..., ak} che vengono considerati ordinati secondo la catena-to a1 ≺ a2 ≺ ... ≺ ak , ogni sequenza haj1, aj2, ..., ajsi per la quale vale la catena-to aj1 ≺ aj2 ≺ ... ≺ ajs .
L’insieme di tali sequenze lo denotiamo con CombA,s o con Comb[A, s] e il loro numero con CombNA,s o con CombN[A, s].
Pi`u specificamente per A = {1, 2, ..., k} scriviamo
Combk,s := Comb[|(k]|, s] e CombN[(k], s] := |CombA,s| . Per esempio le combinazioni di lunghezza 3 degli interi 1, 2, 3, 4 e 5, sono:
123 124 125 134 135 145 234 235 245 345 ; si scrive dunque
Comb5,3 = {123, 124, 125, 134, 135, 145, 234, 235, 245, 345} .
Si osserva che, mentre le combinazioni con ripetizioni di lunghezza s su A = (k] rappresentano le funzioni nondecrescenti di {(s] 7−→ (k]}, le pi`u specifiche combinazioni senza ripetizioni rappresentano le sole funzioni crescenti.
`
E importante osservare anche che CombA,s`e in corrispondenza biunivoca con l’insieme dei sottoinsiemi di A aventi s elementi. In effetti, una scrittura come 125 si pu`o considerare come una semplificazione della scrittura {1, 2, 5} e in generale una c combinazione senza ripetizioni di lunghezza s di elementi di un insieme A di k = |A| oggetti si pu`o considerare una scrittura semplificata del sottoinsieme di A contenente gli oggetti che si incontrano nella c.
B15:f.13 Il numero CombNk,s delle combinazioni senza ripetizioni di determinata lunghezza s di k dati oggetti ordinati, per una ben definita ragione che vedremo in D20b, viene chiamato coefficiente binomiale k su s e viene denotato con k
s
, scrittura che presenta vari vantaggi.
Il complesso di questi numeri `e molto importante in quanto gode di molte propriet`a conseguentemente consente di affrontare e risolvere molteplici problemi che risultano collegati alle accennate propriet`a. I singoli valorik
s
si possono considerare i valori di una funzione di due variabili intere naturali a valori interi positivi e si possono ottenere come numeri dei sottoinsiemi di cardinale s di un insieme di k ≥ s elementi.
Troveremo inoltre che sar`a utile descrivere questi sottoinsiemi come cammini crescenti nel piano dei punti a coordinate intere [D21b] .
Ora ci limitiamo a trovare un’espressione per i valorik s
collegando le combinazioni senza ripetizioni di k oggetti di lunghezza s alle disposizioni senza ripetizioni degli stessi k oggetti della stessa lunghezza s.
A ciascuna delle suddette disposizioni senza ripetizioni si pu`o quindi associare facilmente la combina-zione senza ripetizioni ottenuta disponendo le s componenti in ordine crescente. Per questa trasfor-mazione, ogni combinazione semplice haj1, aj2, ..., ajsi `e ottenibile delle s! disposizioni senza ripetizioni ottenute permutando in tutti i modi le s componenti. Per esempio alla combinazione 2 4 5 9 corri-spondono le 24 disposizioni senza ripetizioni
2 4 5 9 , 2 4 9 5 , 2 5 4 9 , 2 5 9 4 , 2 9 4 5 , 2 9 5 4 , 4 2 5 9 , 4 2 9 5 , 4 5 2 9 , 4 5 9 2 , 4 9 2 5 , 4 9 5 2 , 5 2 4 9 , 5 2 9 4 , 5 4 2 9 , 5 4 9 2 , 5 9 2 4 , 5 9 4 2 , 9 2 4 5 , 9 2 5 4 , 9 4 2 5 , 9 4 5 2 , 9 5 2 4 , 9 5 4 2 .
Abbiamo quindi che il numero delle disposizioni senza ripetizioni di lunghezza s di k elementi `e uguale ad s! per il numero delle combinazioni di lunghezza s di k elementi. Dunque per quest’ultimo numero si ha: (1) CombNk,s = k s = DspsNk,s s! = k(k − 1) · · · (k − s + 1) s! .
Servendoci delle notazioni fattoriale crescente e fattoriale decrescente introdotte in e02 e osservando che k! = ks(k − s)!, abbiamo anche
(2) k s = k s s! = (k − s + 1)s s! = k! s! (k − s)! .
B15:f.14 Anche il numero delle combinazioni con ripetizioni si esprime facilmente servendosi di una espressione gi`a trovata, quella per le combinazioni senza ripetizioni, dopo aver individuata una opp-ortuna biiezione tra questi insiemi di sequenze.
Per questo, per maggiore scorrevolezza, supponiamo che sia A = {a1 = 1, a2 = 2, ..., ak = k} e ricordiamo che le sequenze crescenti (in senso stretto) haj1, aj2, ..., ajsi di lunghezza s si possono porre in corrispondenza biunivoca con le sequenze haj1, aj2−1, aj3−2, ..., ajs−s+1i , sequenze nondecrescenti dei k − s + 1 interi 1, ..., k − s + 1, sequenze che forniscono le combinazioni con ripetizioni di tali numeri. Per esempio, l’insieme di combinazioni Comb(3, 5) = {123, 124, 125, 134, 135, 234, 235, 245, 345} `e posto in corrispondenza biunivoca con l’insieme di combinazioni con ripetizione Combr(3, 5 − 3 + 1) = Combr(3, 3) dalla funzione
y 123 124 125 134 135 234 235 245 345 111 112 113 122 123 222 223 233 333 y .
A questo proposito conviene segnalare esplicitamente il meccanismo che a un elenco di sequenze numeriche nondecrescenti associa un elenco di sequenze crescenti: per ogni sequenza di s numeri si lascia invariato il primo, si aumenta di 1 il secondo, si aumenta di 2 il terzo, ... , si aumenta di i − 1 l’-i-esimo, ..., si aumenta di s − 1 l’ultimo.
Si esplicita facilmente anche il meccanismo che effettua la trasformazione inversa della precedente. Quindi l’insieme delle sequenze nondecrescenti, degli interi a1, ..., ak di lunghezza s `e in biiezione