|
Задача:
Я решал, не применяя формулы комбинаторики, а вручную: т.е. на последнюю позицию ставил 1, 2, 3,.. 7 соответственно и считал, сколько при каждой последней цифре вариантов. Получилась такая последовательность: 1, 7, 28, 84. Далее я нашел в Интернете, что это некая определенная последовательность, подчиняющаяся неким правилам, и следующие члены - 210, 462, 924. В итоге все числа я сложил и получил 1716, что, судя по всему, является ответом. Кстати, интересны два факта: 1) все эти числа как-то связаны с числом сочетаний; 2) следующий член последовательности и есть 1716 (!). В общем, решил я эту задачу вручную. А хотелось бы понять, как решать, применяя комбинаторные методы (формулу числа сочетаний и т.д.). Прошу помочь. задан 14 Сен '14 15:43 
Leva319 |
|
Эта задача решается стандартными комбинаторными методами. Прежде всего, число из условия полностью определяется набором своих цифр, которые мы упорядочиваем по невозрастанию. При этом берётся 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 
falcao А почему цифру 0 можно использовать? Ведь если ноль где-то стоит, то слева должно стоять число меньшее либо равное, а равное - это 0, продолжая рассуждение, приходим к тому, что 0 стоит на первом месте, но этого не может быть.
(14 Сен '14 17:04)
Leva319
Здесь говорится о числах типа, скажем, 9955210: каждая следующая цифра не больше предыдущей. Тогда нули стоят в конце. Если бы в условии говорилось о числах, где следующая цифра не меньше предыдущей, то тогда нулей бы не было совсем, и надо было брать число сочетаний с повторениями из 9 по 7.
(14 Сен '14 17:18)
falcao
|