Tag combinatorics

Catalan Numbers

Suppose we want to populate \(2n\) positions with exactly \(n\) 1’s and \(n\) -1’s. But we have a constraint. For any given \(k\) where...

Probability

Sample Spaces and Events The sample space \(\mathcal{S}\) is a set. An event is a subset of the sample space. A simple event is an event...

Number of Binary Trees of Size \(n\)

Problem How many bits are needed to represent a binary tree with \(n\) nodes? A lower bound is given by the fact that \(m\) bits can...

Dealing With Recurrence Relations

Useful Identities \begin{equation*} \sum_{k=m}^{n}\dbinom{k}{m}=\dbinom{n+1}{m+1} \end{equation*} The mnemonic for this is: Suppose you...