Сошлось с моим - сегодня в маршрутке около часа ехал.
Идея примерно та же. Это число всех матриц

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