Naive Combinatorics

Here is a list of all problems that occur in Combinatorics that is really useful for arranging polynomials :

Problem 1) Arranging n people (Permutation)

Supposed we have 3 people in a line, what is the total number of ways to arrange them? Ex ) Let Alice, Bob, Carl be people, how many different ways can we arrange them in a line $3!$ . Why? 3 choices for the first slot, 2 choices for the second slot, 1 choice the the 3rd slot : $3! = 3 \cdot 2 \cdot 1 = 6$

In general, to arrange n people, we have n! steps

Alice	Bob	Carl
Alice	Carl	Bob
Bob	Alice	Carl
Bob	Carl	Alice
Carl	Alice	Bob
Carl	Bob	Alice

Problem 2) Picking k people from a group of n people

Suppose there are 4 people, what is the number of ways we can pick to people? $(2 4) = 6$ Ex) Lets Say Alice, Bob, Carl, Dan Note : Alice + Bob = Bob + Alice

Alice + Bob, Alice + Carl, Alice + Dan, Bob + Carl, Bob + Dan, Carl + Dan We have 6 different unique combination!

General Formula : $(k n) =_{n} C_{k} = \frac{n !}{k ! ( n - k )!}$ : This describes the problem of choosing k people for a group of n people. Also referred to as “N choose K”

Pascals Reccurance

$(k - 1 n) + (k n) = (k + 1 n + 1) ⟺ (k - 1 n - 1) + (k n - 1) = (k n)$

Problem 3) Filling boxes with balls (Compositions)

Suppose you have 4 balls and 2 boxes, how many total ways can you fill the 2 boxes with all 4 balls such that at least every box has a ball? ex) Let $B_{1}$ be box 1, $B_{2}$ be box 2 Method 1) Balls and Boxes $(B_{1}, B_{2}) : (3, 1), (2, 2), (1, 3)$ General Form : Given $# B a ll s$ and $# B o x es$ such that $# B a ll s \geq # B o x es$ is $(# b o x es - 1 # ba ll s - 1)$ So from the previous example we get : $(2 - 1 4 - 1) = (1 3) = 3$ This problem is also known as the number of compositions of a number. For example, what is the number of ways you can create 4 using positive integers : $4 3 + 1 1 + 3 2 + 2 2 + 1 + 1 1 + 2 + 1 1 + 1 + 2 1 + 1 + 1 + 1$ And if you notice, there are 3 ways to decompose 4 into 2 numbers! Question 4 : Suppose we have the equation $x_{1} + x_{2} + x_{3} + x_{4} = 6, x_{1}, x_{2}, x_{3}, x_{4} > 0$ . What is the total number of solutions to solve this equation? Answer : 6 balls, 4 boxes,, $(4 - 1 6 - 1) = (3 5) = 10$

Problem 4) Filling boxes with balls, but boxes can be empty (Weak Compositions)

Suppose you have 4 balls and 2 boxes, how many ways can we put balls in boxes. (boxes can be empty!) Ex) $(B_{1}, B_{2}) = (4, 0), (0, 4), (3, 1), (1, 3), (2, 2)$ , 5 ways! General problem : If we are given $# ba ll s$ and $# b o x es$ , then $(# b o x es - 1 # ba ll s + # b o x es - 1) = (# ba ll s # ba ll s + # b o x es - 1)$ From our example we should get that $(2 - 1 4 + 2 - 1) = (1 5) = 5 = (4 5) = (4 4 + 2 - 1)$

Question 2) Suppose we have the equation $x_{1} + x_{2} + x_{3} + x_{4} = 10, x_{1}, x_{2}, x_{3}, x_{4} \geq 0$ . What are the total number of solutions: Answer : let $# ba ll s = 10, # b o x es = 4$ . Now suppose we add 4 more balls into our system, and put 1 in every box. Our total number of balls are now 14! it now becomes a Problem 3 question with 14 balls and 4 boxes : $(4 - 1 14 - 1) = (3 13) = 286$

Problem 5) Partitions

Source : https://www.whitman.edu/mathematics/cgt_online/book/section03.03.html Suppose we have 5, what is the number of unique ways to partition 5 into positive integers? $5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1$ We denote the number of partitions for a number p ad $p_{n}$ , so $p_{5} = 7$ In this example, there is no clear way to find the number of total partitions for a given integers, however there are analogies to something called generating functions. Example : examine $P_{8}$ : $(1 + x^{2} + x^{3} + x^{4} + x^{5} + x^{6} + x^{7} + x^{8}) (1 + x^{2} + x^{4} + x^{6} + x^{8}) (1 + x^{4} + x^{8})$ If we expand it out, then it looks like this $1 + x + 2 x^{2} + 3 x^{3} + 5 x^{4} + 7 x^{5} + 11 x^{6} + 15 x^{7} + 22 x^{8} + \dots + x^{56}$

	WIth Exculsion	Without Exclusion
Distinguishable Balls Distinguishable Boxes	$(n)_{k} = n \cdot ... \cdot (n - k + 1)$	$n^{k}$
Indistinguishable Balls Distinguishable Boxes	$(k n)$	$(k n + k - 1)$

Sources :

https://physics.byu.edu/faculty/berrondo/docs/physics-731/ballsinboxes.pdf

Math Matrix

Explorer

Naive Combinatorics

Graph View

Backlinks