Задача. Зростаючий порядок цифр у натуральному
числі
Скільки існує n-цифрових чисел, усі цифри яких записані в строго зростаючому
порядку, якщо вважати правильними n-цифрові записи чисел: 000..01 =1, 00..0012=12, 000…000123=123 і так
далі
Розв'язання. Зрозуміло, що треба розглядати випадок, коли n<11.
Спочатку знайдемо
кількість 10-цифрових чисел, у яких усі цифри різні і розташовані у
довільному порядку.
В розряд одиниць такого 10-цифрового числа можна записати
10-ма способами будь-яку цифру, бо різних цифр 10: {0;1;2;3;4;5;6;7;8;9}.
В розряд десятків
такого 10-цифрового числа можна записати
9 способами деяку цифру, бо 10-1=9 цифр, так як одна цифра уже стоїть
в розряді одиниць, тобто використана.
В розряд сотень такого
10-цифрового числа можна записати
8 способами деяку цифру, бо 10-2=8 цифр, так як дві цифри уже стоять в розряді
одиниць та десятків, тобто використані.
Аналогічно міркуємо
до розряду одиниць мільярдів, в який можна буде
записати лише одним способом цифру. Скористаємося правилом добутку, отримаємо, що існує 10!=1*2*3*4*5*6*7*8*9*10=3628800 чисел, у яких усі цифри різні і розташовані у
довільному порядку.
Порахуємо
кількість десятицифрових чисел, усі цифри яких записані в строго зростаючому
порядку.
З десяти різних
цифр можна утворити 3628800 10-цифрових чисел,
у яких цифри не повторюються і розташовані в довільному порядку, серед яких лише
в одному випадку цифри розташовані в зростаючому порядку. Тому шукані числа
становитимуть 1/3628800 всіх 10-цифрових
чисел з різними цифрами.
Тепер знайдемо кількість
9-цифрових чисел, у яких усі цифри
різні і розташовані у довільному порядку.
В розряд одиниць такого 9-цифрового числа можна записати
10-ма способами будь-яку цифру, бо різних
одна цифра уже
стоїть в розряді одиниць, тобто використана.
В розряд сотень такого
9-цифрового числа можна записати
8 способами деяку цифру, бо 10-2=8 цифр, так як дві цифри уже стоять в розряді
одиниць та десятків, тобто використані.
Аналогічно міркуємо
до розряду сотень мільйонів, в який можна буде
записати лише одним способом цифру, бо
різних цифр 10: {0;1;2;3;4;5;6;7;8;9}.
В розряд десятків
такого 9-цифрового числа можна записати
9 способами деяку цифру, бо 10-1=9 цифр, так як. Скористаємося правилом добутку, отримаємо, що існує 2*3*4*5*6*7*8*9*10=3628800 чисел, у яких усі цифри різні і розташовані у
довільному порядку.
Порахуємо
кількість дев'ятицифрових чисел, усі цифри яких записані в строго зростаючому
порядку.
З десяти різних
цифр можна утворити 3628800 9-цифрових чисел,
у яких цифри не повторюються і розташовані в довільному порядку. З дев'яти різних цифр утворюємо різні
перестановки, серед яких лише в одному випадку цифри розташовані в
зростаючому порядку. Тому шукані числа становитимуть 1/9! всіх 9-цифрових чисел з різними цифрами.
3628800/9!=10 чисел, що мають 9 різних
цифр і розташовані в зростаючому порядку.
Тепер знайдемо кількість
8-цифрових чисел, у яких усі цифри
різні і розташовані у довільному порядку.
В розряд одиниць такого 8-цифрового числа можна записати
10-ма способами будь-яку цифру, бо різних 10 цифр.
В розряд десятків
такого 9-цифрового числа можна записати
9 способами деяку цифру, бо 10-1=9 цифр, так як одна цифра уже стоїть
в розряді одиниць, тобто використана.
В розряд сотень такого
8-цифрового числа можна записати
8 способами деяку цифру, бо 10-2=8 цифр, так як дві цифри уже стоять в розряді
одиниць та десятків, тобто використані.
Аналогічно міркуємо
до розряду десятків мільйонів, в який можна буде записати лише одним
способом цифру, бо різних цифр 10: {0;1;2;3;4;5;6;7;8;9}.
Скористаємося
правилом добутку, отримаємо, що існує 3*4*5*6*7*8*9*10=1814400
чисел, у яких усі цифри різні і
розташовані у довільному порядку.
Порахуємо
кількість 8-цифрових чисел, усі цифри яких записані в строго зростаючому
порядку.
З десяти різних
цифр можна утворити 1814400 8-цифрових чисел,
у яких цифри не повторюються і розташовані в довільному порядку. З восьми різних цифр утворюємо різні перестановки,
серед яких лише в одному випадку цифри розташовані в
зростаючому порядку. Тому шукані числа становитимуть 1/8! всіх 9-цифрових чисел з різними цифрами.
1814400/8!=45 чисел, що мають 8 різних
цифр і розташовані в зростаючому порядку.
Тепер знайдемо кількість
7-цифрових чисел, у яких усі цифри
різні і розташовані у довільному порядку.
В розряд одиниць такого 7-цифрового числа можна записати
10-ма способами будь-яку цифру, бо 10 різних цифр.
В розряд десятків
такого 7-цифрового числа можна записати
9 способами деяку цифру, бо 10-1=9 цифр.
В розряд сотень такого
7-цифрового числа можна записати
8 способами деяку цифру, бо 10-2=8 цифр, так як дві цифри уже стоять в розряді
одиниць та десятків, тобто використані.
Аналогічно міркуємо
до розряду одиниць мільйонів, в який можна буде записати лише одним
способом цифру, із різних цифр 10: {0;1;2;3;4;5;6;7;8;9}.
Скористаємося
правилом добутку, отримаємо, що існує 4*5*6*7*8*9*10=604800 чисел, у яких усі цифри
різні і розташовані у довільному порядку.
Порахуємо
кількість 7-цифрових чисел, усі цифри яких записані в строго зростаючому
порядку.
З десяти різних
цифр можна утворити 604800 7-цифрових чисел,
у яких цифри не повторюються і розташовані в довільному порядку. З 7 різних цифр утворюємо різні перестановки,
серед яких лише в одному випадку цифри розташовані в
зростаючому порядку. Тому шукані числа становитимуть 1/7! всіх 9-цифрових чисел з різними цифрами.
604800/7!=120 чисел, що мають 8 різних
цифр і розташовані в зростаючому порядку.
І так далі.
Для 6-цифровиих
отримаємо: 151200/6!=210 чисел, у яких цифри розташовані у зростаючому порядку.
Для 5-цифровиих
отримаємо: 30240/5!=252 чисел, у яких цифри розташовані у зростаючому порядку.
Для 4-цифровиих
отримаємо: 5040/4!=210 чисел, у яких цифри розташовані у зростаючому
Для 3-цифровиих отримаємо: 720/3!=120 чисел, у
яких цифри розташовані у зростаючому порядку.
Для 2-цифровиих
отримаємо: 90/2!=45 чисел, у яких цифри розташовані у зростаючому порядку.
Для 1-цифровиих
отримаємо: 10/1!=10 чисел, у яких цифри розташовані у зростаючому порядку.
Загальна
кількість натуральних чисел, у яких
цифри розташовані у зростаючому порядку: 2(10+45+120+210)+252 =1022 (враховуючи
і одноцифрові натуральні числа та нуль)
