2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 числа с неубывающими цифрами и пути
Сообщение24.06.2015, 16:44 
Сколько есть четырехзначных чисел, цифры которых возрастают? А неубывают?

Первый вопрос вроде совсем просто: $0$ нигде появиться не может, цифры совпадать не могут. Порядок задается требованием возрастания. Поэтому $9 \choose 4$.

Глядя на первый, на второй вопрос хочется ответить сочетаниями с повторениями. Но тут я как-то запутываюсь. Кодировать следующую цифру можно так: $0$ если повторяю, $k$ единиц, на которые увеличиваю. Вроде бы увеличить больше чем на $8$ единиц не получится. Тогда $x_1+x_2+x_3+x_4\leq 8$. Число решений неравенства совпадает с числом решений $x_1+x_2+x_3+x_4+x_5=8$. Получается $8+5-1\choose 5-1$.

Так? Исходя из неравенства и способа кодировки, кажется что тут еще можно думать об этом, как о неунывающих путях не выше чего-то, но я не могу разобраться.

 
 
 
 Re: числа с неубывающими цифрами и пути
Сообщение24.06.2015, 16:50 
Аватара пользователя
Может, проще вычесть из общего числа 4-хзначных чисел число чисел , для которых нет неубывания цифр?

 
 
 
 Re: числа с неубывающими цифрами и пути
Сообщение24.06.2015, 17:03 
Brukvalub
А это все неправильно?

Всего чисел четырехзначных $9\cdot 10^3$. А нет неубывания как найти? Как найти убывание понятно, это $9 \choose 4$, но там же еще часть где совсем как угодно

 
 
 
 Re: числа с неубывающими цифрами и пути
Сообщение24.06.2015, 17:37 
Аватара пользователя
2old в сообщении #1030458 писал(а):
А неубывают?

А тупо посчитать какими-то включениями-исключениями здесь не проще? (Сам думать не пробовал, но издали кажется, что там несложно подправленные аналоги двузначных и трёхзначных вариантов первого вопроса.)

А ответ на первый вопрос сомнений не вызывает.

 
 
 
 Re: числа с неубывающими цифрами и пути
Сообщение24.06.2015, 17:46 
grizzly
Наверное да, но мне не нравится формула включений-исключений тут потому что если спросят про $5,6...m$ значное число будет грустно. А тут если решение верное, ответ всегда готов: $8+m \choose m$

Сейчас тогда попробую с вкл-выкл и сверю результаты

 
 
 
 Re: числа с неубывающими цифрами и пути
Сообщение24.06.2015, 19:37 
Ваша формула верная. Нули выбрать не можем. Можем выбрать $x_1$ единиц, $x_2$ двоек ...$x_9$ девяток и упорядочить их единствееным образом. Для $m$ значного числа должно выполнятся

$x_1+x_2+\cdots+x_9=m$, что и есть число композиций числа $m$ длиной 9, естественно, с нулями. Или $C_{m+8}^8$

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group