Discussion 7A

Combinatorics

Stars and Bars

You have room for nn fruits in your basket, and there are kk different types of fruit. How many ways can you fill up your basket with nn fruits?

You can partition your basket into kk groups so that placing a fruit in a group indicates that you take a fruit of that type. This partitioning can be accomplished using k1k-1 bars as the boundaries. Then the number of configurations is the number of ways to place the nn fruits and k1k-1 bars in a sequence, or (n+k1n)\binom{n+k-1}{n}.

Example: a basket with capacity n=5n=5 fruits and k=3k=3 types of fruits: apples, oranges, and bananas.
   apples          oranges          bananas
    ●  ●      |             |      ●  ●  ●

This is the same as the number of nonnegative integer solutions to napple+norange+nbanana=5n_{\text{apple}} + n_{\text{orange}} + n_{\text{banana}} = 5.

Inclusion-exclusion

AB=A+BAB| A \cup B | = |A| + |B| - |A \cap B|
Draw a Venn diagram.
Generalization to more sets:
i=1nAi=i=1nAii,jAiAj+±A1An\vert \bigcup_{i=1}^n A_i \vert = \sum_{i=1}^n | A_i| - \sum_{i, j} | A_i \cap A_j | + \cdots \pm | A_1 \cap \cdots \cap A_n |

Combinatorial Proofs

Given an identity, LHS=RHS\text{LHS} = \text{RHS}, come up with a story to equate both sides.

Hockey Stick Identity

(n+1k+1)=(nk)+(n1k)++(k+1k)+(kk)\binom{n+1}{k+1} = \binom{n}{k} + \binom{n-1}{k} + \cdots + \binom{k+1}{k} + \binom{k}{k}
Comes from Pascal’s Triangle
LHS\text{LHS}: the number of ways to choose k+1k+1 players from a team of n+1n+1 people
RHS\text{RHS}: Suppose the n+1n+1 people on the team are numbered from 11 to n+1n+1. Then you can count the number of ways to choose k+1k+1 players by considering the disjoint cases of what the greatest number selected is. 
  • Case n+1n+1 is the greatest number selected: there are (nk)\binom{n}{k} ways to choose kk from the players {1,2,3,,n}\{1, 2, 3, \cdots, n \}
  • Case nn is the greatest number selected: there are (n1k)\binom{n-1}{k} ways to choose kk from the players {1,2,,n1}\{1, 2, \cdots, n-1 \}
  • \vdots
  • Case k+1k+1 is the greatest number selected: there are (kk)\binom{k}{k} ways to choose the rest of the team from {1,2,,k}\{ 1, 2, \cdots, k \}
Since these are disjoint cases, you can find the total number of ways to choose k+1k+1 players by summing up the individual ways to choose players.