Calcolatore di stelle e barre
Utilizza il metodo delle stelle e delle barre per contare le combinazioni con ripetizione x1 + ... + xk = n, inclusi casi non negativi, positivi, con limite inferiore e limitati.
Come utilizzare (3 passaggi)
- Entra nn (totale) e k (numero di variabili/caselle).
- Seleziona la condizione: xi ≥ 0, xi ≥ 1, o xi ≥ ai (facoltativo: limitato).
- Copia un URL condivisibile per riprodurre lo stesso stato.
Nota: questa calcolatrice conta identico palle. Se le palle sono distinte, il modello è diverso.
Guida visiva
Per dati in ingresso piccoli, questo mostra un esempio di codifica con stelle (*) e barre (|). È un esempio, non “l’unico accordo”.
Risultati
Passi (brevi)
Mostra il ragionamento
Esempi (soluzioni)
Mostra soluzioni per piccoli n,k
Suggerimento: l'elenco delle soluzioni è limitato (prestazioni). Per dati in ingresso di grandi dimensioni, utilizzare solo il conteggio.
Formule ed errori comuni
- Non negativo (xi≥0):
C(n+k−1, k−1) - Ciò equivale a “combinazioni con ripetizione” (scelta multipla):
k multichoose n = C(n+k−1, n). - Positivo (xi≥1):
C(n−1, k−1)(sen<kallora0) - Limiti inferiori (xi≥ai): convertire in
n−Σai, quindiC((n−Σai)+k−1, k−1)
Errori comuni
- Mescolare “palle identiche” e “palle distinte”. Questa calcolatrice è per identico palline (soluzioni intere).
- Per xi≥1, ricorda
n<kdà0. - Per i limiti inferiori, assicurati di sottrarre
Σai(non solo un singolo a a meno che tutti i ai non siano uguali).
Calcolatori correlati
Come scegliere la giusta configurazione a stelle e barre
Questa calcolatrice è per articoli identici distribuiti su riquadri o variabili. Se l'ordine è importante o se gli articoli sono distinti, utilizza un modello di conteggio diverso.
Perché le sbarre contano
Nell'immagine classica, ogni stella è un elemento e ogni barra è un divisore tra le caselle. Una volta deciso dove k−1 le barre vanno tra le n+k-1 posizioni, hai descritto in modo completo una soluzione.
Usalo in 3 passaggi
- Entra nn per il numero totale di articoli identici e k per il numero di caselle o variabili.
- Scegli la condizione che corrisponde al problema: xi ≥ 0, xi ≥ 1, limiti inferiori o valori limitati.
- Leggi prima il conteggio, quindi controlla i brevi passaggi e gli esempi per confermare di aver scelto il modello giusto.
Come scegliere la modalità
- Utilizzare xi ≥ 0 quando sono consentite scatole vuote.
- Utilizzare xi ≥ 1 quando ogni scatola deve ricevere almeno un articolo.
- Utilizzare xi ≥ ai quando ciascuna variabile ha un minimo.
- Utilizzare ai ≤ xi ≤ bi solo quando sia il limite inferiore che quello superiore costituiscono parte del problema.
Confronti funzionanti
Se metti 7 palline identiche in 3 caselle in cui sono consentite caselle vuote, il conteggio è C(9,2). Se ogni scatola deve contenere almeno una pallina, passa al caso positivo e conta C(6,2) invece. Questo contrasto è solitamente il modo più rapido per stabilire se un problema in classe è positivo o non negativo.
Errori comuni da evitare
- Utilizzare questa pagina per elementi distinti quando il modello corretto è permutazioni, conteggio multinomiale o composizione intera.
- Raccolta xi ≥ 0 quando il problema dice davvero che ogni scatola deve contenere almeno un oggetto.
- Inserimento di limiti inferiori o superiori senza verificare se la somma può ancora raggiungere nn.
- Leggere un esempio visivo come l'insieme completo di soluzioni.
Vedi anche
Domande frequenti
Cos'è il metodo stelle e barre?
Conta il numero di modi per distribuire n elementi identici in k scatole, che è il numero di soluzioni di x1+…+xk=n in condizioni come xi≥0.
Perché il caso non negativo diventa C(n+k−1, k−1)?
Posiziona n stelle e k−1 barre in fila. La scelta delle posizioni delle barre determina in modo univoco una soluzione, fornendo C(n+k−1, k−1).
Come cambia la formula quando xi≥1?
Sia yi=xi−1. Allora y1+…+yk=n−k con yi≥0, quindi il conteggio è C(n−1, k−1) quando n≥k, altrimenti 0.
Come funzionano i limiti inferiori xi≥ai?
Sia yi=xi−ai. Allora y1+…+yk=n−Σai con yi≥0. Se n≥Σai, il conteggio è C((n−Σai)+k−1, k−1); altrimenti 0.
Quando dovrei usare positivo anziché non negativo?
Utilizzare il caso positivo quando ogni variabile o casella deve ricevere almeno un elemento. Utilizzare il caso non negativo quando è consentito lo zero. Quel singolo cambiamento di formulazione è la fonte più comune di risposte sbagliate nei problemi a stelle e barre.
E se le palline fossero distinguibili?
Questo calcolatore presuppone palline identiche. Se le palline sono distinguibili, il modello cambia (spesso k^n o multinomiale), quindi utilizzare un calcolatore diverso a seconda del problema.