Numero di combinazioni di due numeri da un elenco con numeri ripetuti? [duplicare]

Question

Ho provato a cercarlo su Google e a cercarlo su questo sito Web, ma poiché non conosco il termine tecnico per questo calcolo sono rimasto senza fortuna. Fondamentalmente, se ho una raccolta di numeri (ognuno dei quali può avere duplicati) quante combinazioni uniche di$n$ i numeri posso fare scegliendo da quella collezione?

(https://math.stackexchange.com/questions/553960/extended-stars-and-bars-problemwhere-the-upper-limit-of-the-variable-is-bounded)

Per esempio:

$C = \{ 1, 2, 2, 3, 3, 3 \}$ e voglio sapere quante combinazioni di $2$ numeri che posso fare.

Dando uno sguardo alla collezione, vedo rapidamente che posso creare solo le seguenti coppie:

$P = \{ (1,2),(1,3),(2,2),(2,3),(3,3) \}$

Il che mi dà la risposta $|P|=5$.

Ma se voglio trovare il numero di combinazioni di $4$ numeri, non posso semplicemente enumerare tutto il possibile $4$-tuple perché non c'è modo di fare $(1,1,1,1)$ o $(1,2,2,2)$, per esempio.

C'è un modo per calcolarlo in generale usando il calcolo combinatorio?

Answer 1

Riduciamo la domanda a qualcosa che sono sicuro che sarai in grado di risolvere:

Useremo la seguente notazione:

$n$ denoterà il numero di numeri diversi (assumiamo che i numeri siano esattamente $1,...,n$).

$a_k$ è il numero di copie del numero $k$.

$s$ è la lunghezza delle tuple.

Supponiamo per un secondo di non avere restrizioni, in questo caso le abbiamo $n$ scelte per ogni elemento, dobbiamo scegliere $s$ in totale e dividere per gli ordinamenti interni: $$\frac{n^s}{s!}$$ Tuttavia abbiamo contato combinazioni malvagie! quindi rimuoviamo quelli in cui abbiamo preso almeno $a_k + 1$ copie del numero $k$ per ciascuno $k\in[n]$, dobbiamo scegliere dove mettere il file $a_k+1$ copie, per quello ci sono ${s\choose a_k+1}$opzioni e moltiplichiamo per i modi di scegliere i wats rimasti. da quelli che abbiamo$$\sum_{1\leq k \leq n}{\frac{n^{s-a_k-1}}{(s-a_k-1)!}\cdot {s\choose a_k+1}}$$

Ricorda che dobbiamo rimuovere quelli dal totale: $$\frac{n^s}{s!} - \sum_{1\leq k \leq n}{\frac{n^{s-a_k-1}}{(s-a_k-1)!}\cdot {s\choose a_k+1}}$$

Ma aspetta! cosa succede se abbiamo superato il limite in più di una delle variabili? Contiamo due volte che ... Per questo tipo di problemi, abbiamo la formula di inclusione-esclusione con gli eventi$A_k$ significa che abbiamo superato l'importo con il numero $k$

$$\sum_{I \subseteq \{1,...,n\}}(-1)^{\vert I\vert}\cdot{\frac{n^{s-\sum _{k\in I}(a_k+1)}}{(s-\sum _{k\in I}(a_k+1))!}\cdot {s\choose \sum _{k\in I}(a_k+1)}}$$

Senza più assunzioni sull'insieme delle restrizioni, dubito dell'esistenza di una formula esplicita, tuttavia, l'asintotico può essere calcolato valutando i primi pochi termini.