Задача:

Cкoлькo имeeтcя 7-знaчныx чиceл, у кoтopыx кaждaя cлeдующaя цифpa (cлeвa нaпpaвo) нe большe пpeдыдущeй?

Я решал, не применяя формулы комбинаторики, а вручную: т.е. на последнюю позицию ставил 1, 2, 3,.. 7 соответственно и считал, сколько при каждой последней цифре вариантов. Получилась такая последовательность: 1, 7, 28, 84. Далее я нашел в Интернете, что это некая определенная последовательность, подчиняющаяся неким правилам, и следующие члены - 210, 462, 924. В итоге все числа я сложил и получил 1716, что, судя по всему, является ответом. Кстати, интересны два факта:

1) все эти числа как-то связаны с числом сочетаний;

2) следующий член последовательности и есть 1716 (!).

В общем, решил я эту задачу вручную. А хотелось бы понять, как решать, применяя комбинаторные методы (формулу числа сочетаний и т.д.). Прошу помочь.

задан 14 Сен '14 15:43

изменен 14 Сен '14 18:09

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
1

Эта задача решается стандартными комбинаторными методами. Прежде всего, число из условия полностью определяется набором своих цифр, которые мы упорядочиваем по невозрастанию. При этом берётся 7 цифр из 10, причём цифры могут повторяться. А это не что иное как число сочетаний с повторениями из 10 по 7. В комбинаторике доказывается общая формула, что число сочетаний с повторениями из $%n$% по $%m$%, обозначаемое в виде $%\bar{C}$% с нижним индексом $%n$% и верхним индексом $%m$%, равно обычному числу сочетаний из $%m+n-1$% по $%m$%. В данном случае это $%C_{16}^7=11440$%. Ответом же будет число, на единицу меньшее, поскольку мы не можем брать все 7 нулей: из них 7-значное число не составить. А все остальные варианты годятся, поэтому в ответе получается $%11439$%.

Та величина, которая получилась у Вас -- это число сочетаний с повторениями из 7 по 7, то есть $%C_{13}^7=1716$%. Это соответствует случаю, когда 7-значное число составляется из цифр от 1 до 7. Но ведь это не обязательно так, потому что можно использовать и цифры 0, 8, 9.

ссылка

отвечен 14 Сен '14 16:00

изменен 14 Сен '14 16:03

А почему цифру 0 можно использовать? Ведь если ноль где-то стоит, то слева должно стоять число меньшее либо равное, а равное - это 0, продолжая рассуждение, приходим к тому, что 0 стоит на первом месте, но этого не может быть.

(14 Сен '14 17:04) Leva319

Здесь говорится о числах типа, скажем, 9955210: каждая следующая цифра не больше предыдущей. Тогда нули стоят в конце. Если бы в условии говорилось о числах, где следующая цифра не меньше предыдущей, то тогда нулей бы не было совсем, и надо было брать число сочетаний с повторениями из 9 по 7.

(14 Сен '14 17:18) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,370

задан
14 Сен '14 15:43

показан
945 раз

обновлен
14 Сен '14 17:18

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru