Neural Sync Active

Advanced Counting

Registry Synced

121 words

1 min read

Reading compass

Now · Stars and Bars (Combinations with Repetition)

Stars and Bars (Combinations with Repetition)

Number of ways to distribute

n

identical objects into

k

distinct boxes:

\binom{n + k - 1}{k - 1}

Example: Number of solutions to

x_1 + x_2 + x_3 = 10

with

x_i \geq 0

integers:

\binom{10+3-1}{3-1} = \binom{12}{2} = 66

\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!}

A derangement is a permutation with no fixed points. Number of derangements of

n

items:

D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}

D_4 = 9

D_5 = 44

D_6 = 265

C_n = \frac{1}{n+1}\binom{2n}{n}