2024-09-25

Kombinatorik

För $n \in Z_{+}$ , $x, y$ variabler

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} * y^{n - k}

Exempel:

(2 + 3)^{2} = \sum_{k = 0}^{2} (\binom{2}{k}) 2^{k} * 3^{2 - k} = (\binom{2}{0}) 2^{0} * 3^{2 - 0} + (\binom{2}{1}) 2^{1} * 3^{2 - 1} + (\binom{2}{2}) 2^{2} * 3^{2 - 2} = 9 + 12 + 4 = 25

(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n}{k + 1})

För $n \in Z_{+}$ och $p \in (0, 1)$ gäller $\sum_{k = 0}^{n} (\binom{n}{k}) p^{k} * (1 - p)^{n - k} = (p + 1 (1 - p))^{n} = 1^{n} = 1$

Beräkna för $n \in Z_{+}$ , $\sum_{k = 0}^{n} (\binom{n}{k})$

Alt 1: Sätt $x = y = 1$ i binomialsatsen:

(1 + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) 1^{k} * 1^{n - k} = \sum_{k = 0}^{n} (\binom{n}{k})

På hur många sätt kan 7 lika bollar placeras i 4 boxar?

Enklare exempel

Om ej lika (de alla går att särskilja) finns det $4^{7}$ sätt. För varje boll finns det 4 val av lådor och vi väljer 7 gånger för 7 bollar.

Lösning

För lika bollar tänk på bollarna i en följd.
Att dela in de i 4 lådor är detsamma som att bestämma 3 avgränsningar mellan bollarna:
••|•••|••|

Det är ekvivalent med att placera ut 10 objekt (7 bollar och 3 avgränsningar) vilket ges av $(\binom{10}{3}) = 120$

Allmänt gäller att $n$ lika objekt kan fördelas i $k$ "lådor" på $(\binom{n + k - 1}{k - 1})$ sätt.

$n$ saker ska placeras i $m$ "lådor". Om $n > m$ måste det finnas minst en låda med fler än 1 sak i.

$L = "mängden av lådor som vi har"$
$n \in Z \land n < | L |$
$"n saker delas in i lådorna L" ⟹ \exists l \in L, "saker i l" > 1$

A_{i} \cap A_{j} = \emptyset \forall i, j \in N ⟹ | ⋃_{i = 1}^{n} A_{1} | = \sum_{i = 1}^{n} | A_{1} |

| ⋃_{i = 1}^{n} A_{i} | = \sum_{i = 1}^{n} | A_{i} | - \sum_{i, j; i < j} | A_{i} \cap A_{j} | + \sum_{i, j, k; i < j < k} | A_{i} \cap A_{j} \cap A_{k} | - \dots \pm \sum_{i,} \dots