A331128 Number of ways to write n as n = h_1*1! + h_2*2! + ... + h_k*k! where 0 <= h_i <= 2*i for all i.

1, 1, 2, 1, 2, 1, 3, 2, 4, 2, 3, 1, 3, 2, 4, 2, 3, 1, 3, 2, 4, 2, 3, 1, 4, 3, 6, 3, 5, 2, 6, 4, 8, 4, 6, 2, 6, 4, 8, 4, 6, 2, 5, 3, 6, 3, 4, 1, 4, 3, 6, 3, 5, 2, 6, 4, 8, 4, 6, 2, 6, 4, 8, 4, 6, 2, 5, 3, 6, 3, 4, 1, 4, 3, 6, 3, 5, 2, 6, 4, 8, 4, 6, 2, 6

Offset: 0

Author

Tom Edgar, Jan 10 2020

Keywords

• nonn
• base

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.

Examples

			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.
		

Crossrefs

Cf. A108731, A084558, A099563.

Programs

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)

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)).