Conteggio delle k-combinazioni escludendo matematicamente i duplicati

Aug 23 2020

Diciamo che ho un multinsieme di numeri interi acon una dimensione n(qui n = 10)

$$a = \{1, 1, 2, 2, 3, 4, 5, 6, 6, 10\}$$

Mi piacerebbe conoscere il conteggio delle k-combinazioni che posso ottenere con un kvalore fornito ed escludendo le combinazioni duplicate

Dal articolo dedicato So che la formula per contare il numero di duplicati tra cui è$\frac{n!}{k! (n - k)!}$, ma non ho trovato alcun accenno a un possibile modo per ottenere un conteggio escludendoli ovunque. Esiste solo una formula matematica che consente di calcolarlo o è l'unica soluzione a fare affidamento su qualche algoritmo?

Risposte

1 Vepir Aug 23 2020 at 20:06

Possibili strategie

Come discusso in Numero di k-combinazioni di un multinsieme , il tuo problema di conteggio$k$-combinazioni $\mathcal C_k$ di qualche multiset $\{a_1^{(r_i)},a_2^{(r_i)},\dots,a_n^{(r_i)}\}$ dove $(r_i)$ conta quanti elementi di genere $a_i$ sono lì, equivale a contare il numero di soluzioni intere dell'equazione

$$ x_1+x_2+x_3+\dots+x_n=k, 0\le x_i\le r_i, $$

dove $x_i$ rappresenta il numero di volte in cui l'elemento di $a_i$ tipo è stato utilizzato in una combinazione.

Nota che se $k=0,1$ allora la risposta è semplicemente $1,n$. Altrimenti, questo problema non ha una soluzione in forma chiusa, ma ci sono ancora modi diversi per risolverlo.

Vedi le risposte date al problema esteso di stelle e barre (dove il limite superiore della variabile è limitato) . Come dimostrato qui, è possibile utilizzare ad esempio il principio di inclusione-esclusione o esaminare i coefficienti del polinomio corrispondente.

Applicare possibili strategie al tuo esempio

Nel caso del tuo esempio: $$\{1^{(2)},2^{(2)},3^{(1)},4^{(1)},5^{(1)},6^{(2)},10^{(1)}\}\implies n=7,$$ Proverò entrambe le risposte menzionate alla domanda precedentemente collegata.

$$\text{I}.$$Ad esempio, possiamo utilizzare il principio di inclusione-esclusione: (vedi una risposta dal post collegato)

$$\begin{align} \mathcal C_k = \sum_{S\subseteq \{1,2,\dots,n\}}(-1)^{|S|}\binom{k+n-1-\sum_{i\in S}(r_i+1)}{n-1} \end{align}$$

Che è per la corrispondenza $k$ ampliato e semplificato come:

$$\begin{align} \cal C_{2} = C_{8} &= \binom{8}{6} - 4\cdot\binom{6}{6} &= 24 \\ \cal C_{3} = C_{7} &= \binom{9}{6} - \left(3\cdot\binom{6}{6}+4\cdot\binom{7}{6}\right) &= 53 \\ \cal C_{4} = C_{6} &= \binom{10}{6} - \left(3\cdot\binom{7}{6}+4\cdot\binom{8}{6}\right) + 6\cdot\binom{6}{6} &= 83 \\ \cal C_{5} = C_{5} &= \binom{11}{6} - \left(3\cdot\binom{8}{6}+4\cdot\binom{9}{6}\right) + \left(12\cdot\binom{6}{6}+6\cdot\binom{7}{6}\right) &= 96 \\ \end{align}$$

Nota che se il numero totale di elementi è $m$, poi $\cal C_i = C_{m-i}$, che è $m=10$ nel tuo esempio.

$$\text{II}.$$In alternativa, se non vuoi utilizzare il principio di inclusione-esclusione, puoi guardare i coefficienti di (vedi l'altra risposta dal post collegato):

$$ P(x) = \prod_{i=1}^n (1-x^{(r_i+1)}) = \sum_ic_ix^{e_i} $$

Quindi la tua risposta diventa:

$$ {\cal{C}}_k = \sum_{i=0}^kc_i\binom{k-e_i+n-1}{n-1} $$

Nel caso del tuo esempio, il polinomio che ho ottenuto è:

$$P(x) = -x^{17}+\dots+18 x^{10}+11 x^9-11 x^8-18 x^7-x^6+12 x^5+6 x^4-3 x^3-4 x^2+1 $$

E quando sostituisco i coefficienti, ottengo le stesse identiche equazioni del metodo precedente.

$$\text{III}.$$A volte, se il tuo multiset è abbastanza semplice, puoi usare trucchi o principi di conteggio per ottenere un risultato senza dover fare affidamento su cose come i due metodi precedenti. Oppure, se il tuo multiset è di tipo speciale, allora ci sono formule più belle. Ad esempio, se tutti$r_i$ sono uguali o se tutti $r_i$ siamo $\infty$.

Se desideri esplorare tali esempi, puoi cercare le domande contrassegnate [multisets] [combinations].

Ad esempio, la risposta accettata a Impossibile pensare a 10 combinazioni di un multinsieme è in grado di ridurre il problema a un problema "Stelle e barre" che ha una formula chiusa. Anche l'altra risposta è carina perché la risolve graficamente.