Зростаючий порядок цифр

Задача. Зростаючий порядок цифр у натуральному числі

Скільки існує  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 (враховуючи і одноцифрові натуральні числа та нуль)