0

We have to create a binary sequence from left to right .

Each $'0'$ gives 1 point to person-'B' and each $'1'$ gives 1 point to person 'A'.

Length of the sequence will be $n$

We are also given an integer $k$ such that $n>=k>=1$

(Maximum possible value of 'n' in this problem:-1000)

The binary sequence should satisfy the following condition :-

1)At each point(index) of the binary sequence(we start from the leftmost index) the total score of person 'A' should be greater than or equal to $k$ times the score of person 'B' .

Example :- n=4 and k=2 .

Possible sequences :-

(1)1111

(2)1110

(3)1101 (At the third step of sequence (3) , score of 'A'=2, and score of 'B'=1 ,as 2>= k*(score of 'B') , 3rd index is valid, similarly we check for all the indices , and the sequence is valid only if all the indices are satisfied from left to right)

Given any n and k , how to find the number of possible binary sequences ?

I am trying to find an efficient algorithm which can solve the problem in $O(N)$ or a closed-form(formula) for this question.

Quadratic DP will also be fine for me.

What have I figured out :-

1)Whenever, $k=1$ , this formula works for any 'n' :- https://oeis.org/search?q=1+2+3+6+10+20+35&sort=&language=english&go=Search

2)Whenever $k=2$, this formula always works for any 'n' : - https://oeis.org/search?q=1+2+3+4+8+13+19+38+64+98+196&sort=&language=english&go=Search

How to figure out the common formula for other(any) values of $k$ ?

Firex Firexo
  • 295
  • 2
    This is a duplicate of https://math.stackexchange.com/q/3342318/5676 , although since this one is the better question (not only because it shows effort but because of the clear goal which rules out the easy dynamic programming approach) I'm tempted to vote to close the other as a duplicate of this. – Peter Taylor Sep 03 '19 at 18:22
  • 1
    I have a conjectured generating function $$g(x) = \frac{h(x)^2}{1 - (x+1)h(x) + (x+1)h(x)^2 - xh(x)^3}$$ where $$h(x) = \sum_n \frac{1}{kn+1} \binom{(k+1)n}{n} x^{(k+1)n}$$ but I'm not sure how to extract its coefficients so that they can be calculated faster than the quadratic DP. – Peter Taylor Sep 03 '19 at 22:17
  • @PeterTaylor Quadratic DP will be fine for me . – Firex Firexo Sep 04 '19 at 06:26
  • Can you tell me the function in easy way, in this form :--> Answer is binomial(x1,x2)....like the said here:- https://oeis.org/A001405 – Firex Firexo Sep 04 '19 at 06:53
  • Can you write this as an answer ? Your answer is what I actually wanted . Say, for n=4,the value of coefficients of h(x) for (k=0,1,2,3,4) are :--> 1,14,55,140,285. .. now what do I do in the next step if I want answer for say, k=2 ? – Firex Firexo Sep 04 '19 at 07:29

0 Answers0