Ну, аналитическую формулу не выведу, но посчитать можно...
Рассмотрим D(k,l) - число k-значных чисел (с ведущими нулями в том числе) с суммой цифр l.
А теперь посмотрим общее число почти счастливых билетов (для k=n/2)...
Для суммы слева 0 справа годится D(k,1) чисел - итого D(k,0)*D(k,1)
Для суммы слева 1 справа годится D(k,0)+D(k,2) чисел - итого D(k,1)*D(k,0)+D(k,1)*D(k,2)
Для суммы слева 2 справа годится D(k,1)+D(k,3) чисел - итого D(k,2)*D(k,1)+D(k,2)*D(k,3)
...
Для суммы слева 9k справа годится D(k,9k-1) чисел - итого D(k,9k)*D(k,9k-1)
Суммируя, получаем общее количество как

Теперь как считать D(k,l) - простое динамическое программирование:

из того соображения, что к числу с k-1 цифрой приписываем цифры от 0 до 9. Начальные условия для D(0,l) очевидны - при l==0 получаем 1, для остальных - 0.
Собственно, все. Пишем программу. Мемоизацию (или ДП снизу вверх) дописывайте сами :)
long long int D(int k, int l)
{
if (k==0) return (l==0);
long long int sum = 0;
for(int j=0; j<=9; ++j) sum += D(k-1,l-j);
return sum;
}
long long int res(int k)
{
long long int sum = 0;
for(int l = 1; l <= 9*k; ++l)
sum += D(k,l)*D(k,l-1);
return 2*sum;
}
int main(int argc, const char * argv[])
{
for(int n = 2; n <= 12; n+=2)
cout << setw(2) << n << ": " << res(n/2) << endl;
}
Результаты для небольших n:
2: 18
4: 1320
6: 109494
8: 9564720
10: 860000900
12: 78783456336
14: 7312306950130
Для очень больших n нужна длинная арифметика...
P.S. Не выдержал - переписал... См. тут.
Для n==100 - 277195334834500944669228740375357778944913131715952295846893641728073727377808583283711688841134000 почти счастливых билетов...