Calcolatore del coefficiente multinomiale

Il coefficiente multinomiale risponde a una domanda fondamentale di conteggio: dati n elementi distinti ripartiti in k gruppi etichettati di dimensioni n1, n2, fino a nk, quante assegnazioni distinte esistono quando l'ordine all'interno di ciascun gruppo non conta? Quella quantità si scrive come il multinomiale di n su n1,n2,…,nk ed è uguale al fattoriale di n diviso per il prodotto dei fattoriali di ciascun gruppo. Quando ci sono solo due gruppi si riduce al noto coefficiente binomiale; con tre o più gruppi conta i riordinamenti di parole con lettere ripetute, le celle delle tabelle di contingenza e i modi di distribuire carte in mani fisse. Questa capacità valuta l'identità con aritmetica BigInt affinché i grandi coefficienti restino esatti invece di superare il floating-point o i limiti degli interi sicuri.

Cosa significa il coefficiente multinomiale e come si calcola

Un coefficiente multinomiale conta il numero di modi per partizionare un insieme di n oggetti distinti in k gruppi etichettati di dimensioni prescritte n1, n2, fino a nk che sommano esattamente a n. La forma chiusa è il fattoriale di n sul prodotto dei fattoriali di quelle dimensioni di gruppo.

Esempi classici di aula rendono concreta la definizione: il numero di riordinamenti distinti delle lettere di MISSISSIPPI è undici fattoriale su quattro fattoriale per quattro fattoriale per due fattoriale per un fattoriale, e il numero di modi per distribuire un mazzo di cinquantadue carte in quattro mani etichettate da tredici carte è cinquantadue fattoriale su tredici fattoriale alla quarta. Quando k vale due la formula si riduce al coefficiente binomiale C(n,n1), quindi i multinomiali sono una generalizzazione stretta di n scegli r.

Valutare i fattoriali in modo ingenuo è disastroso per n grandi perché i valori intermedi esplodono molto prima che il rapporto finale sia moderato. Questo strumento moltiplica quindi binomiali sequenziali—C(n,n1) per C(n−n1,n2) per il choose restante successivo, e così via—usando JavaScript BigInt affinché ogni intermedio resti esatto e il conteggio finale sia restituito come stringa decimale.

Quel contratto coincide con i manuali standard di combinatoria e con i giudici dei contest di programmazione, così Lei può fidarsi del numero rispetto ai calcoli a mano per n piccoli e alle tabelle note per i più grandi senza deriva in virgola mobile né wraparound silenzioso.

Come eseguire il calcolo e leggere il risultato

Il campo n è il numero totale di elementi—l'indice superiore del multinomiale—e deve essere un intero non negativo da zero a diecimila. Il campo groups è un array non vuoto di interi non negativi n1, n2, fino a nk che formano una partizione di n: la loro somma deve uguagliare n esattamente, e ogni dimensione deve essere un intero tra zero e n inclusi.

Una risposta di successo restituisce n come numero, groups come l'array di interi coercizzato, count come stringa decimale del valore multinomiale esatto, e formula come la stringa n! /(n1! n2! … nk!) così i client possono mostrare o registrare l'identità senza codificarla a mano.

Lo usi da correttori di compiti, validatori di contest di programmazione, sandbox di preparazione ai colloqui, job di arricchimento di fogli di calcolo, demo di probabilità multinomiale che necessitano del coefficiente prima di moltiplicare per potenze di probabilità, strumenti didattici di tabelle di contingenza, o qualsiasi flusso che necessiti di un conteggio multinomiale riproducibile senza installare pacchetti multiprecisione su ogni macchina che esegue la pipeline.