OFFSET
0,3
COMMENTS
We call such a partition of n a hyperfactorial partition as these are in some sense analogous to hyperbinary partitions (A002487).
This sequence also counts the possible carry sequences when adding two numbers that sum to n using the traditional algorithm for adding two factorial-base representations.
FORMULA
a(n) = 0 if n<0; a(0) = 1; a(n) = a(n-n_k*k!) + a((n_k+1)*k!-n-2) for n > 0, where n_k is the most significant digit of the factorial-base representation of n (i.e., n_k = A099563(k)).
EXAMPLE
There are 6 ways to write n = 705 in the desired fashion:
705 = 1*1! + 1*2! + 1*3! + 4*4! + 5*5!;
705 = 1*1! + 1*2! + 5*3! + 3*4! + 5*5!;
705 = 1*1! + 4*2! + 4*3! + 3*4! + 5*5!;
705 = 1*1! + 4*2! + 4*3! + 8*4! + 4*5!;
705 = 1*1! + 1*2! + 5*3! + 8*4! + 4*5!;
705 = 1*1! + 4*2! + 0*3! + 4*4! + 5*5!.
Thus a(705) = 6.
PROG
(Sage)
def factoradic(n):
if n==0:
return [0]
L=[]
i=2
while n!=0:
dm=divmod(n, i)
L.append(dm[1])
n=dm[0]
i+=1
return L
@cached_function
def carryseq(n):
if n<0:
return 0
elif n==0:
return 1
else:
L=factoradic(n)
k=len(L)
nk=L[-1]
return carryseq(n-nk*factorial(k))+carryseq((nk+1)*factorial(k)-n-2)
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Tom Edgar, Jan 10 2020
STATUS
approved