Chaitanya's Random Pages

December 14, 2014

Basic combinatorics results

Filed under: mathematics — ckrao @ 8:11 pm

The following lists most of the introductory combinatorics formulas one might see in a first course expressed in terms of the number of arrangements of letters in which repetition or order matters.

number of letters alphabet size letters repeated? order matters? formula comments
k n yes yes n^k samples with replacement
k  n no yes \begin{aligned} & n(n-1)\ldots (n-k+1)\\ &= \frac{n!}{(n-k)!} = P(n,k) = (n)_k\end{aligned} samples without replacement (permutations)
n  n no  yes n! if letters in a line

(n-1)! if letters in a ring and rotations are considered equivalent

(n-1)!/2 if letters in a ring and rotations & reflections are considered equivalent

 k n no no \frac{n!}{k!(n-k)!} = \binom{n}{k} = C(n,k) binomial coefficient

(combinations)

n 2 yes: k of type 1, n-k of type 2 yes \binom{n}{k}
n m yes: k_1 of type i for i = 1,\ldots, m yes \frac{n!}{k_1! k_2! \ldots k_m!} = \frac{(k_1 + k_2 + \ldots + k_m)!}{k_1! k_2! \ldots k_m!} = \binom{n}{k_1, k_2, \ldots, k_m} multinomial coefficient (multiset permutations)

e.g. number of arrangements of “BANANA” is \frac{6!}{3!2!1!}

n k yes no \binom{n+k-1}{k-1} = \binom{n+k-1}{n} = \left(\!\!{n \choose k}\!\!\right) multiset coefficient (combinations with repetition):

number of non-negative integer solutions to n_1 + n_2 + \ldots + n_k = n

n 2 no two consecutive letters of type 1 yes F_{n+2} Fibonacci number where F_{n+2} = F_{n+1} + F_n and F_1 = F_2 = 1

e.g. number of sequences of 6 coin tosses with no two consecutive heads is F_8 = 21

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: