Combinatorics

Types of selection

	With rearrangement	Without rearrangement
With repeat	n^k	${n + k - 1 \choose{k}}$
Without repeat	$n!$	${n\choose{k}}$

See 9. Urval med återläggning

Multiplication principle

The basis for all combinatorics.

Sequence

An array of numbers.

arithmetic

geometric

Series

The "sum" of an array of numbers.

arithmetic

An arithmetic sequence changes by the same amount per term.

Let's describe some arbitrary series. Each term is made up of the "initial amount" plus the indice times the "step size".

To teach clearly, we won't use the variable i for the indice, but instead say n − 1, n − 2 and so on.

Writing it out – if there are n terms where the first term is a, the sum can be expressed:

[a]  +  [a + 1]  +  [a + 2]  + ... +  [a + (n-2)]  +  [a + (n-1)]

Note how this series does not reach a + n, and falls just short, because the very first term is at indice zero. You can of course write this differently, counting from indice one to indice n, rather than from zero to (n-1). You must change the initial amount (or "starting value").

It is common for the "step size", or increment, to be just one. If you have a different increment, you have to multiply the indice. Say the increment is d and we get the general expression (the one above was specifically for d=1 so that d disappeared):

[a]  +  [a + d]  +  [a + 2d]  + ... +  [a + (n-2)d]  +  [a + (n-1)d]

On our quest to sum this thing, we're going to place an indentical line below it, with the order reversed. Then think about what happens if you add the lines together.

 S =            a   +    a + 1d       +    a + 2d       + ... +    a + (n-1)d
 S =   a + (n-1)d   +    a + (n-2)d   +    a + (n-3)d   + ... +    a
2S =  2a + (n-1)d   +   2a + (n-1)d   +   2a + (n-1)d   + ... +   2a + (n-1)d

What just happened? The indice in the first row increases, but the indice of the second row decreases, so the summed indice stays.

You know how to factor. I hand the reins to you. Do this every time you need the summation formula, derive it.

n(a) + n (n-1) d 1/2
n(a) + n(n-1)d
(n + n)(a + nd/2-d/2)

geometric

A geometric sequence increases by the same factor per term. (?)

Binomial theorem

You can expand (x + y)ⁿ as follows.

${n\choose0} x^n y^0 + {n\choose1} x^{n-1} y^1 + {n\choose2} x^{n-2} y^2 + \dots + {n\choose{n-1}} x^1 y^{n-1} + {n\choose n} x^0 y^n$

This is not the same thing as (xⁿ + yⁿ)! That is a sum of e.g. cubes like x³ + 1, where the exponents are "inside the parentheses", for which there is a different formula (Sum/difference of cubes).

Explanation

Binomials are expressions like (x + y)². You memorize quadratics in high school, but how do you expand (x + y)¹⁴?

You can use Pascal's Triangle, but suppose you have (x + y)¹²⁷³³. Find facts about a specific term in that massive polynomial.

Uses the notion of Combination.

Pascal's Triangle

    1       zeroth row -- a constant: (x + y)^0
   1 1      first row --- a binomial
  1 2 1     second row -- a binomial to the second degree
 1 3 3 1    third row
1 4 6 4 1   fourth row

Explanation

You can write Pascal's Triangle from scratch – for each entry, add the two entries above it.

Take an example binomial of fourth degree, (x + y)⁴. When expanded, it produces a polynomial with coefficients from the fourth row.

We have the row, 1 4 6 4 1. Place your x'es and y'es. The fourth-degree x-term goes to the left, the fourth-degree y goes go the right.

$\begin{align*} \textrm{Pascal's Triangle fourth row: } & \textrm{$1$ \ \ \ \ \ $4$ \ \ \ \ \ \ $6$ \ \ \ \ \ $4$ \ \ \ \ \ $1$} \\ \textrm{Writing just the $x$-factors gives us: } & 1x^4 + 4x^3 + 6x^2 + 4x + 1 \\ \textrm{Writing just the $y$-factors gives us: } & 1 + 4y + 6y^2 + 4y^3 + 1y^4 \end{align*}$

Once both are placed out, we end up with the completed polynomial:

$x^4 + 4 x^3 y + 6 x^2 y^2 + 4 x y^3 + y^4$

Which can be viewed with redundancy, for clarity:

$1 x^4 y^0 + 4 x^3 y^1 + 6 x^2 y^2 + 4 x^1 y^3 + 1 x^0 y^4$

Combination🔗

Finding combinations of k items from n, ${n\choose k},$ "n choose k", is ${ n!\over{k!(n - k)!} }.$

For example, ${10 \choose 2} = { 10!\over{2!8!}}.$

A startling symmetry is that ${10 \choose 8} = { 10!\over{8!2!}},$ which is the same as the previous identity. This symmetry, that ${n \choose{k}} = {n \choose{n-k}},$ works for any numbers $n$ and $k$ you want.

Permutation

A combination lock should be called a permutation lock. The order matters, 2-7-1 isn't 2-1-7.

There are more permutations than combinations.

Factorials

Note that 10! / 8! is the same as 10 * 9. If it's not obvious why, think.

What links here

Math