# 2. Methodical guidelines / Методичні вказівки

This section is **self-contained**: it develops the theory of the work's theme —
combinatorial counting and descriptive statistics — together with algorithms for
the tasks in [4task.md](4task.md). No outside material is required.

## 2.1 Permutations, arrangements, combinations

Let $n$ be the number of available elements and $k$ the size of a selection
($0 \le k \le n$).

- A **permutation** is an ordering of **all** $n$ elements. Their number is
  $$P_n = n! = n\cdot(n-1)\cdots 2\cdot 1.$$
- An **arrangement** (written $A_n^k$ here; the same count is $P(n,k)$ in Lecture 13 and
  Practical 6) is an **ordered** selection of $k$ elements (order matters):
  $$A_n^k = n\cdot(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}.$$
- A **combination** is an **unordered** selection of $k$ elements (order does not
  matter):
  $$C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!\,(n-k)!} = \binom{n}{k}.$$

The single distinction is **order**: arrangements count $(A,B)$ and $(B,A)$
separately; combinations treat them as the same selection. For $n = 5,\ k = 3$:
$P_5 = 120$, $A_5^3 = \tfrac{120}{2} = 60$, and $C_5^3 = \tfrac{60}{6} = 10$.

## 2.2 Computing the counts

Compute a factorial with a simple loop. For $A_n^k$ and $C_n^k$, prefer the
**multiplicative** form over dividing two large factorials — it keeps the numbers
small and exact:

```text
function factorial(n):
    r ← 1
    for i from 2 to n: r ← r * i
    return r

function arrangements(n, k):             # A(n,k) = n·(n-1)···(n-k+1)
    r ← 1
    for i from 0 to k-1: r ← r * (n - i)
    return r

function combinations(n, k):             # C(n,k) = A(n,k) / k!
    return arrangements(n, k) / factorial(k)
```

## 2.3 Descriptive statistics

For a dataset $x_1, \dots, x_n$:

- the **mean** (mathematical expectation) is the average value
  $$\mu = E[X] = \frac{1}{n}\sum_{i=1}^{n} x_i;$$
- the **variance** measures the average squared spread about the mean
  $$D[X] = \operatorname{Var}(X) = \sigma^2 = \frac{1}{n}\sum_{i=1}^{n} (x_i - \mu)^2;$$
- the **standard deviation** is its square root, in the same units as the data,
  $\sigma = \sqrt{D[X]}$.

(The formula above is the **population** variance, dividing by $n$; a *sample*
variance divides by $n-1$.) For the dataset $\{2,4,4,4,5,5,7,9\}$: $\mu = 40/8 =
5$, the squared deviations sum to $32$, so $D[X] = 32/8 = 4$ and $\sigma = 2$.

![Expectation as the weighted-average balance point of a distribution: E[X] = 3.5 for a fair die](img/expectation.png)

## 2.4 Generating combinatorial objects

Counting says *how many*; generating produces the objects themselves. Permutations
are generated by recursion — fix each element in turn as the first, and permute
the rest:

```text
function permutations(elements):
    if length(elements) ≤ 1: return [ elements ]
    result ← empty list
    for i from 0 to length(elements) - 1:
        first ← elements[i]
        rest  ← elements without index i
        for p in permutations(rest):
            append [first] + p to result
    return result
```

If `elements` is sorted, this emits them in lexicographic order:
$(A,B,C), (A,C,B), (B,A,C), (B,C,A), (C,A,B), (C,B,A)$ — six in total ($3! = 6$).
Combinations of size $k$ are generated similarly: for each element, either include
it (and choose $k-1$ from the rest) or skip it.

## 2.5 Complexity

Computing $P_n$, $A_n^k$, or $C_n^k$ takes $O(n)$ (or $O(k)$) multiplications. The
statistics take one or two passes over the data, $O(n)$. **Generating** all
permutations is inherently $O(n \cdot n!)$ — the output alone has $n!$ items — so
explicit generation is practical only for small $n$.