You have room for n fruits in your basket, and there are k different types of fruit. How many ways can you fill up your basket with n fruits?
You can partition your basket into k groups so that placing a fruit in a group indicates that you take a fruit of that type. This partitioning can be accomplished using k−1 bars as the boundaries. Then the number of configurations is the number of ways to place the n fruits and k−1 bars in a sequence, or (nn+k−1).
Example: a basket with capacity n=5 fruits and k=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=5.
LHS: the number of ways to choose k+1 players from a team of n+1 people
RHS: Suppose the n+1 people on the team are numbered from 1 to n+1. Then you can count the number of ways to choose k+1 players by considering the disjoint cases of what the greatest number selected is.
Case n+1 is the greatest number selected: there are (kn) ways to choose k from the players {1,2,3,⋯,n}
Case n is the greatest number selected: there are (kn−1) ways to choose k from the players {1,2,⋯,n−1}
⋮
Case k+1 is the greatest number selected: there are (kk) ways to choose the rest of the team from {1,2,⋯,k}
Since these are disjoint cases, you can find the total number of ways to choose k+1 players by summing up the individual ways to choose players.
Combinatorics
Stars and Bars
apples oranges bananas
● ● | | ● ● ●
Inclusion-exclusion
Combinatorial Proofs
Hockey Stick Identity