|
Примеры палиндромических представлений числа $%2$% (симметричной относительно центра суммы, равной $%2$%): $%0,2,0$%; Сколько подобных представлений у числа $%n$%? задан 5 Ноя '14 20:06 
stander |
|
Пусть $%f(n)$% -- искомое число представлений. Ясно, что $%f(1)=1$%. Удобно также считать, что $%f(0)=1$%, имея в виду, что $%0$% представим одним способом в виде суммы без слагаемых. Пусть $%n > 1$%. Одно из представлений состоит из слагаемого, равного $%n$%. Оно подходит. У остальных представлений получается $%n=k+\cdots+k$%, где $%k$% натуральное, а внутри находится палиндромическая сумма для числа $%n-2k$%. При этом возможно, что она пуста. Число $%k$% удовлетворяет неравенствам $%1\le k\le n/2$%, где дробь можно заменить её целой частью. Из сказанного следует такая рекуррентная формула: $%f(n)=1+f(n-2)+f(n-4)+\cdots$%. Для начальных значений $%n$% одинаковые числа идут парами. Эта закономерность сохраняется и далее. По индукции легко доказывается, что $%f(2k)=f(2k+1)=2^k$% (можно параллельно разбирать оба случая), то есть общий ответ можно записать как $%f(n)=2^{[n/2]}$%. отвечен 5 Ноя '14 22:36 
falcao |
|
Пускай $%n$% - чётно. Тогда количество палиндромических представлений числа - это сумма композиций чисел (https://ru.wikipedia.org/wiki/Композиция_числа) $%n/2,n/2-1,...,1$% плюс 1 (собственно число $%n$%). Итого: $%2^{n/2-1}+2^{n/2-2}+...+2+1+1=2^{n/2}$%. Случай нечётного $%n$% аналогичен. отвечен 5 Ноя '14 22:26 
EdwardTurJ |
Я пока что не совсем понимаю условие. Какова роль нулей слева и справа?
Например, для числа 5 можно рассмотреть суммы типа самого 5 (из одного слагаемого), 1+3+1, 2+1+2, а также 1+1+1+1+1. Всего 4 варианта. Я правильно интерпретировал?
@falcao: Да, абсолютно верно.