Skip to main content
\(\renewcommand{\chaptermark}[1]{\markboth{\MakeUppercase{ #1}}{\thechapter~ #1}} \renewcommand{\sectionmark}[1]{} \newcommand{\abs}[1]{\left|#1\right|} \renewcommand{\theenumi}{5.\arabic{enumi}} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\norma}[1]{\left\|#1\right\|} \newcommand{\BM}[1]{\text{\boldmath$#1$}} \newcommand{\halmaz}[1]{\left\{\,#1\,\right\}} \newcommand{\halmazvonal}[2]{\left\{\,#1\mid #2\,\right\}} \newcommand{\halmazpont}[2]{\left\{\,#1:#2\,\right\}} \newcommand{\N}{\mathbb{N}} \newcommand{\len}{\norm} \newcommand{\var}[2][]{v_{#1}\left(#2\right)} \newcommand{\vari}[2]{v_{#1}\left(#2\right)} \newcommand{\size}[2][]{s_{#1}\left(#2\right)} \newcommand{\dep}[2][]{d_{#1}\left(#2\right)} \newcommand{\sizestar}[2][]{s_{#1}^*\left(#2\right)} \newcommand{\depstar}[2][]{d_{#1}^*\left(#2\right)} \renewcommand{\headrulewidth}{0pt} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section2.1Sequences

In Section 1.4 we have learned how to write a number in different numeral systems. We are now interested in how many \(n\)-digit numbers exist in a certain numeral system. Let us start with base 10. We know that there are 9 one-digit positive integers: 1, 2, 3, 4, 5, 6, 7, 8, 9. How many two digit positive integers exist? One way to count them is that we know that there are 99 positive integers which are one-digit or two-digit long. We have already counted that there are 9 one-digit positive integers. Therefore there are \(99-9=90\) two-digit positive integers.

We could have calculated this differently: there are 9 possibilities for a first digit of a two-digit number, and there are 10 possibilities (independently from the first digit) for the second digit. That is, there are \(9 \cdot 10\) two-digit positive integers.

Now, what about three-digit positive integers? There are 999 ‘at most three-digit numbers’, and 99 are ‘at most two-digit numbers’. Thus there are \(999-99=900\) three-digit positive integers. But we can obtain this result by using the other idea, as well. There are 9 possibilities for the first digit of a three-digit number, 10 possibilities for the second digit and 10 possibilities for the third digit, that makes \(9 \cdot 10 \cdot 10 = 900\) possibilities for three digit positive integers.

Let us generalize this argument for \(n\)-digit positive integers. There are 9 possibilities for the first digit, and 10 possibilities for every other digit. Altogether, the number of \(n\)-digit positive integers (in base 10) is

\begin{equation*} 9 \cdot \underbrace{10 \cdot \dots \cdot 10}_{n-1} = 9\cdot 10^{n-1}\text{.} \end{equation*}

How many \(n\)-digit base 2 positive integers exist?

We could generalize this idea for arbitrary bases.

There are \((k-1)\)-many possibilities for the first digit (it cannot be 0, only \(1, 2, \dots, k-1\)), and there are \(k\) possibilities for every other digit. Thus, the number of \(n\)-digit positive integers in base \(k\) is

\begin{equation*} (k-1) \cdot \underbrace{k \cdot \dots \cdot k}_{n-1} = (k-1) \cdot k^{n-1}\text{.} \end{equation*}

And what about the “at most” \(n\)-digit non-negative integers in base \(k\) (including 0)? In this case, we can consider them as \(n\)-digit numbers, where the first digit can be 0, as well. Thus, there are \(k\) possibilities for the first digit, \(k\) possibilities for the second digit, etc. Thus,

In a very similar way we can count the number of possible 5 letter long words. (Here, we count the not necessarily meaningful words, as well.) Indeed, as the English alphabet consists of 26 letters, we have 26 possibilities for the first letter, 26 possibilities for the second letter, etc. That is, the number of 5 letter long words is

\begin{equation*} 26 \cdot 26 \cdot 26 \cdot 26 \cdot 26 = 26^5\text{.} \end{equation*}

It seems, that it is easy to calculate sequences of letters (i.e. possible words), as long as we know how long they should be and how many letters the alphabet has. Indeed, we can formulate our main theorem.

There are \(k\) possibilities to choose the first letter. Then, there are \(k\) possibilities to choose the second letter (no matter how we have chosen the first letter), etc. Altogether there are \(n\) letters to choose (with possible repetitions), thus the number of \(n\) letter long sequences is

\begin{equation*} \underbrace{k \cdot k \cdot \dots \cdot k}_{n} = k^n\text{.} \end{equation*}

Sometimes this theorem needs to be combined for different alphabets for each letter. We already saw an example: for calculating the number of \(n\)-digit long base 10 numbers, the first digit is an element of an alphabet of size 9, and every other \((n-1)\) digit can be an element of size 10. As the choice of the digits is independent to each other, the number of \(n\)-digit base 10 numbers is \(9 \cdot 10^{n-1}\text{.}\)

Another possible example is the mobile phone number of a person. In Hungary, there are three mobile providers, and each provider issues 7 digit long numbers. Thus altogether there are \(3 \cdot 10^7\) possibilities for a mobile phone number in Hungary.

How many 3 digit palindrome numbers exist (in base 10)? (Palindrome numbers are numbers which are the same if read backwards. How many at most 3 digit palindrome numbers exist (in base 10)? Generalize the result to \(n\)-digit base \(k\) palindrome numbers.

The Hungarian alphabet contains 44 letters. How many 5, 7, 10 letter long (not necessarily meaningful) words can be created using Hungarian letters?

In Hungary there is a game called “TOTÓ”, where one bets on the outcome of certain football games. There are \(13+1\) games one can bet on, and there are 3 choices for each of them: one writes ‘1’ if they think that the first team wins, one writes ‘2’ if they think that the second team wins, and ‘X’ means that the result is a draw. How many TOTÓ tickets should be filled out to make sure that one of them will be correct for all \(13+1\) games?

In a company the following system is used to record the people working there: in the first record the name of the person is written as a 20 long string with possible spaces. Then the gender of the person is put into the next record (male/female). Then follows the person's job title in a 10 letter long string, and finally comes the payment of the person as an at most 8 digit non-negative integer in base 10. How many people records can be stored in this system if we allow empty names/job titles, as well?