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. 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:

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$.

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:

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$.

Laboratory/Laboratory7/2method.md · 3.6 KB · updated 2026-08-01 18:44