Combinazioni senza ripetizione

Le combinazioni senza ripetizione rispondono a una domanda di conteggio fondamentale in statistica e matematica discreta: dati n elementi distinti, quanti gruppi diversi di dimensione k può formare Lei quando nessun elemento compare due volte e l'ordine della selezione non conta? Quella quantità è il coefficiente binomiale C(n,k), anche scritto n sceglie k. Non c'è campionamento, né rete, né arrotondamento dipendente dalla data: ogni coppia valida (n, k) produce sempre lo stesso intero.

Che cosa contano le combinazioni senza ripetizione

Le combinazioni senza ripetizione contano in quanti modi si può scegliere un sottoinsieme di k elementi da un insieme di n elementi distinti quando ciascun elemento compare al più una volta e l'ordine della selezione non conta. Nel linguaggio d'aula questo è n sceglie k; nella notazione statistica è il coefficiente binomiale C(n,k). L'identità classica afferma che C(n,k) è il fattoriale di n diviso il fattoriale di k per il fattoriale di (n meno k).

Quella stessa quantità compare come coefficiente nello sviluppo binomiale di (x più y) alla n, e come il numero di k-sottoinsiemi di un insieme a n elementi. Poiché l'ordine è ignorato, scegliere Alice e poi Bob è la stessa combinazione che scegliere Bob e poi Alice, quindi il conteggio è strettamente minore della permutazione corrispondente P(n,k) ogni volta che k è almeno due.

Poiché la ripetizione è vietata, Lei non può scegliere la stessa persona due volte: questa è la differenza rispetto alle combinazioni con ripetizione, dette anche combinazioni di multiinsiemi, il cui conteggio è C(n+k−1, k). I casi al contorno fanno parte della definizione: C(n,0) e C(n,n) valgono entrambi uno, C(n,1) uguaglia n, e C(0,0) è uno per la convenzione del prodotto vuoto. Se k è maggiore di n non esiste un k-sottoinsieme di un n-insieme, quindi questa calcolatrice rifiuta la coppia invece di restituire zero o un binomiale generalizzato.

L'implementazione non campiona mai, non dipende dall'orologio e non arrotonda mai: valuta il prodotto ridotto da (n meno k più uno) fino a n, diviso passo dopo passo da uno fino a k, con aritmetica BigInt esatta così i coefficienti grandi restano interi precisi invece di superare la mantissa di un numero in virgola mobile.

Usi in aula, campionamento e gare

Quei problemi condividono lo stesso intero C(n,k); questa pagina è scritta per chi cerca quella frase in modo esplicito, compresi gli studenti a cui è appena stato detto di non confonderla con combinazioni che ammettono ripetizioni. I generatori di esami possono fissare il percorso di successo con n uguale a dieci e k uguale a tre, che produce centoventi, e il percorso di rifiuto con qualsiasi k che superi n, che deve fallire invece di restituire zero.

I programmatori di gare e le sandbox di colloquio necessitano di un oracolo esatto per i problemi di conteggio delle combinazioni senza reimplementare un'aritmetica a multiprecisione in ogni harness di linguaggio. Landing fratelli possono trattare permutazioni, combinazioni con ripetizione o un calcolatore nCr generico; questo atterraggio è specificamente la formulazione senza ripetizione. Abbini il conteggio al proprio codice di elenco se le servono i sottoinsiemi stessi; questa capacità restituisce soltanto l'intero.