Combinatory of words

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 27 · page 27.4
Combinatory of words
Rule of work · Positioning · Words with limitations · EGE type 8
Why do we need a combinatoric on the computer?
Because it explains why Shannon's entropy sets the compression boundary: the power of the code space, the number of possible messages and the optimal code length is all a combination.
GEF
PIF
EEG No. 8
EEG No. 11
Relationship to the previous topic.
The number of possible binary words length n is 2
n
That's why you need at least log 2N bits to encode N symbols -- that's the Hartley formula.
01
Rule of work
Rule of work:
If the first step can be performed n1 in ways, the second step is n2 in ways ..., k step is in nk in ways and all elections
independent
the number of sequences:
N = n₁ × n₂ × … × nₖ
Case studies
Objective
Calculation
Response
Two-digit password from 0-9
10 × 10
100
3-letter word from {A, B,B,G} with repetitions
4 × 4 × 4 = 4³
64
Twin line 8
2⁸
256
Car number: 3 letters (30) + 3 digits
30³ × 10³
27 000 000
02
Spaces without repetition
If each letter can be used
not more than once
the number of k-letters of n different letters:
A(n, k) = n × (n−1) × (n−2) × … × (n−k+1)
In the first entry of n options, in the second position of n-1, one letter is occupied, etc.
Example: 3-letter words without repetition from {A, B,B,G,D}
A(5, 3) = 5 × 4 × 3 =
60 words
Comparison.
Repeated: 53 = 125. Without repetition: A(5.3) = 60. Prohibition of repetition reduces the number of options by half.
03
Types of Tasks of the EGE: Limitations
Type of restriction
Formula
Example (n=5, k=3)
The first letter is a specific "A"
1 × n^(k−1)
1 × 5² = 25
The first is of the m vowels.
m × n^(k−1)
2 × 5² = 50
Doesn't contain the letter "X"
(n−1)^k
4³ = 64
"X" meets exactly one time.
k × (n−1)^(k−1)
3 × 4² = 48
No repetition
A(n,k) = n×(n−1)×…
5×4×3 = 60
04
Reviewing the EGE task step by step
EGE task type 8
Condition:
How many words of length 5 out of {A, B, V, G, D} start with `A' and do not contain repetitions?
Item 1:
only "A"
1
option
Item 2:
any of the remaining 4 letters
4
option
Item 3:
any of the remaining 3 letters
3
option
Item 4:
of the remaining 2
2
option
Item 5:
Last letter
1
option
Total: 1 x 4 x 3 x 2 x 1 = 24 words
Task 2: number 5 exactly once
Condition:
How many 4-digit numbers without 0, where the number 5 occurs exactly once?
Step 1:
Select the entry for "5" ♪
4
option (any of the 4 entries)
Step 2:
The other 3 entries are numbers 1 to 9, except 5 =
8
options each . 83 = 512
Total: 4 x 83 = 4 x 512 = 2,048 numbers
05
Visual word designer
🔤
Compose the Word — The Rule of Work in Action
Alphabet
Length of word
Repeats
06
EGE Trainer: Challenges with Limitations
🎲
EEG Type 8 - step-by-step review
Press "New Task" to start
07
Communication with information and entropy
The number of words k length from the power alphabet n is
n
k
. To encode one word, you need log2(n)
k
) =
k · log2n bit
- The alphabetical approach formula!
Число слов = nᵏ → I = log₂(nᵏ) = k · log₂n бит
If letters are encountered with different probabilities, the optimal code (Haffman) does not give each letter the same length — the rarer need more bits.
Entropy is like the bottom line.
H(p1,...,pn) ≤ log2n. Equality at equal probability.
Interactive: size n alphabet
The size of the alphabet n =
4
length k =
3
Number of words nk
64
Bit to word.
6.00
log2n (in letter)
2.00
🎯
Mini-test: 5 questions
XP: 0
🧩
Check yourself out.
5 questions on the combinatorial · 20 XP for each correct answer