Combinations of a sequence with any adjacent product no more than a given number

Question

I was wondering whether there is an analytic solution or recursive solution of the combination calculation of natural number sequence with length X, where the multiplications of any adjacent numbers in the sequence is no more than Y?

For example when X = 3, Y = 3, the sequences are (1,1,1)(1,1,2)(1,1,3)(1,2,1)(2,1,1)(1,3,1)(3,1,1),(3,1,2)(2,1,3)(3,1,3)(2,1,2).

I know when X = 2, such combination is

Y + [Y/2] + [Y/3] + ... +[Y/Y]

how to recursively derive from X to X+1 then? Or is there some direct expression of the solution?

Answer 1

Let's P(Y, X, K) is number of combinations with length X, ending with K. Then

P(Y, X + 1, M) = Sum(k=1..[Y/M] P(Y, X, K))

with starting point:

P(Y, 1, K = 1..Y) = 1