# 6. Control questions and tasks / Контрольні запитання і завдання

## Combinatorics

1. Define a **permutation**, an **arrangement**, and a **combination**. Which of
   them depend on the **order** of the selected elements?
2. Write the formulas for $P_n$, $A_n^k$, and $C_n^k$. Derive $C_n^k$ from
   $A_n^k$.
3. Compute $P_5$, $A_5^3$, and $C_5^3$, showing the arithmetic.
4. What are $C_n^0$ and $C_n^n$? Explain why.

## Descriptive statistics

5. Define the **mean** (mathematical expectation), the **variance**, and the
   **standard deviation** of a dataset.
6. What is the difference between the **population** variance ($\div n$) and the
   **sample** variance ($\div (n-1)$)?
7. Why does the standard deviation, rather than the variance, have the same units
   as the data?

## Implementation and complexity

8. Why is the **multiplicative** form of $A_n^k$ preferable to computing
   $n! / (n-k)!$ directly?
9. Outline a **recursive** algorithm that generates all permutations of a set.
   What is its output size for $n$ elements?
10. Why is explicitly **generating** all permutations feasible only for small
    $n$, even though **counting** them is instant?

## Tasks by hand

11. Compute $P_4$, $A_6^2$, and $C_6^2$.
12. For the dataset $\{1, 3, 5, 7\}$, compute the mean, the (population) variance,
    and the standard deviation.
13. List all $C_4^2$ two-element combinations of the set $\{A, B, C, D\}$.