Given two numbers $N$ and $K$, where $N$ is the size of an array $A$ - initially filled with all zeroes.
For every $1, 2, \cdots, K$, you have to choose a non-empty subarray and assign all elements in that subarray to be equal to $K$.
Find a formula for the number of distinct possibilities of array $A$.
Example:
$N = 2, K = 2$.
Initially, $A = [0, 0]$.
For $K = 1$, $A$ can attain one of $3$ possibilities : $[0, 1]$, $[1, 0]$ or $[1, 1]$.
Then, for $K = 2$, $A$ can assume one of $5$ distinct sequences : $[0, 2]$, $[1, 2]$, $[2, 0]$, $[2, 1]$ or $[2, 2]$.
Thus, for $N = 2$ and $K = 2$, our answer is $5$.
I tried boiling this problem down to known sequences.
For $N = 1$, our answer is always $1$.
For $N = 2$, our answer for every $K$ is equal to $2\cdot K + 1$.
For $N = 3$, our answers go according to the sequence A056109 on OEIS. (For ($N = 3, K = 1$) the answer is 6, and for ($N = 3, K = 2$) the answer is 17 and so on)
Couldn't find any for $N > 3$. I was trying to find a recursive relation but I'm completely lost!
N = 2 : = $2 K +1$
N = 3 : = $3 K^2 + 2 K + 1$
N = 4 : = $4 K^3 + 3 K^2 + 2 K + 1$
Hope you can see the pattern
1,2,3,4..... in expansion comes from the sizes of sub array
for example N = 4 :{a,b,c,d} === {a}{b}{c}{d}{a,b}{b,c}{c,d}{a,b,c}{b,c,d}{a,b,c,d} = total of 10 arrays = $4 + 3 + 2 + 1$
what we are doing is back tracking the cases where we can get such arrays
For example (N=4 k=3) {0,0,0,0}
if we choose {a} = {3}
the other places for b,c,d can be filled with any of the 3 choices (0,1,2)
therefore = 3*3*3
Similarly if we choose {a,b,c} ={3,3,3}
option d can only be filled by (0,1,2)
total choices = 3
Note: I dont know much about array, i just solve the pattern given from the examples you have provided and using the basic definition of sub array. I have doubts such that why the rest of options can only be filled with (0,...,K-1) numbers, why not K,K+1,...