String (Discrete Math) — Definition, Formula & Examples
A string is a finite, ordered list of symbols written one after another, such as 1011 or cat. A bit string is a string that uses only the symbols 0 and 1.
Let be a finite nonempty set called an alphabet. A string (or word) of length over is a finite sequence with each . Equivalently, it is an element of written without commas or parentheses. Its length is . The empty string, written or , is the unique string of length . The set of all strings over is . A bit string is a string over .
Key Formula
Where:
- = number of distinct strings of length n
- = number of symbols in the alphabet (k = 2 for bit strings)
- = length of each string, a nonnegative integer
How It Works
Two strings are equal only when they have the same length and the same symbol in every position, so order and repetition both matter. You join strings by concatenation: if and , then and . Counting problems about strings usually reduce to the product rule, because each position is an independent choice from the alphabet. When a problem fixes some positions or the number of a certain symbol, you count the remaining free choices or use binomial coefficients to pick positions.
Worked Example
Problem: Let be a bit string and let be the empty string. (a) Find . (b) List all prefixes of . (c) Find . (d) Is a substring of ?
Step 1: The length counts the symbols: .
Step 2: A prefix is the first symbols, for . The empty string is the prefix with , so a string of length 5 has 6 prefixes.
Step 3: Concatenating with the empty string adds nothing, so .
Step 4: A substring is a block of consecutive symbols. Symbols 2 through 4 of are .
Answer: ; the prefixes are , , , , and ; ; and is a substring of (symbols 2 to 4).
Another Example
Problem: How many strings of length 3 over the alphabet contain at least one ?
Step 1: Count all strings of length 3. Each of the 3 positions can hold any of the 3 letters.
Step 2: Count the strings with no : each position holds or .
Step 3: Subtract to count the strings with at least one .
Answer: There are 19 strings of length 3 over that contain at least one . Counting by positions works for bit strings too: choosing which 3 of 8 positions hold a 1 gives bit strings of length 8 with exactly three 1s.
Why It Matters
Bit strings are the standard model for data in computer science, and counting them is a core skill in a college Discrete Mathematics course. Strings over an alphabet are also the basic objects of formal language and automata theory, where a language is defined as a subset of . Error-correcting codes, binary encodings, and Huffman coding all describe information as bit strings.
Common Mistakes
Mistake: Treating a string like a set, so that 0110 and 1100 are counted as the same, or 0110 is said to have length 2 because it uses only two distinct symbols.
Correction: Order and repetition matter in a string. 0110 and 1100 are different strings, and each has length 4 because length counts positions, not distinct symbols.
Mistake: Treating a bit string as a binary number, so that 0011 is considered equal to 11, or forgetting the empty string when counting strings of length at most .
Correction: Leading zeros are part of the string: 0011 has length 4 and 11 has length 2, so they are different strings. When lengths start at 0, include the empty string, which contributes .
