1
$\begingroup$

Background: The binomial coefficients $C(n,k)$ satisfy the recurrence $C(n,k)=C(n-1,k)+C(n-1,k-1)$ and some terminating conditions, for more information check here.

$C(n,k)$ doesn't appear to be efficiently computable via the recurrence even with caching, but it can be computed in time $O(n)$ via the factorial formula.

For natural $n,k$, define $G(n,k)=G(n-2,k)+G(n,k-2)$ if $n,k>2$, otherwise the terminating conditions are $G(n,k)=n+k$. If necessary, change the terminating conditions for the questions below.

Q1 What is the time complexity of computing $G(n,k)$? Is it $O(n)$ (we have $G(n,k)=G(k,n)$).

Q2 How is $G(n,n)$ growing? Is it $c^n$ for some constant $c$?

Q3 Is there combinatorial interpretation of $G(n,k$), is it counting something?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Note that $G(2n,2k),G(2n+1,2k),G(2n,2k+1),G(2n+1,2k+1)$ satisfy the same recurrence as $C(n,k)$ so should be expressible as their linear combinations. I don't have a notebook on me though so I can't give you the formulas. $\endgroup$
    – Wojowu
    Commented Nov 4, 2019 at 12:00

1 Answer 1

Reset to default
6
$\begingroup$

The sequence $G(2n,2k)$ is $T(n,k)/2$, where $T(n,k)$ is A051601. For $G(2n,2k+1)$ boundary conditions $1,3,5,7,\ldots$ can be replaced by $0,2,4,6$ (minus one Pascal triangle). It gives $G(2n,2k)$ again. Almost the same for $G(2n+1,2k+1)$ (minus two Pascal triangles).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you. Do you require $k \le n$? $\endgroup$
    – joro
    Commented Nov 4, 2019 at 15:52
  • $\begingroup$ @joro No, everything is like in Pascal triangle $(n,k \ge 0).$ $\endgroup$
    – Alexey Ustinov
    Commented Nov 4, 2019 at 15:56
  • $\begingroup$ @joro Sorry, probably it was not clear. In this case Pascal triangle fills the first coordinate quarter: $C(n,0)=C(0,k)=1,$ $C(n,k)=C(n-1,k)+C(n,k-1).$ $\endgroup$
    – Alexey Ustinov
    Commented Nov 4, 2019 at 16:25
  • $\begingroup$ Is the following generalization solvable: for natural A,B define $G(n,k)=G(n-A,k)+G(n,k-B)$? $\endgroup$
    – joro
    Commented Nov 5, 2019 at 7:38
  • $\begingroup$ @joro Yes, because in this case the answer is the sum of 2 trangles. First one has 0, 0, 0, ... and 0, A, 2A, 3A,... on it's sides, second one has 0, B, 2B,... and 0, 0, 0,... respectively. In both cases you'll get Pascal triangle multiplied by A or by B and shifted. For n and k not divisable by A and B one should correct boundary conditions using additional Pascal triangles. $\endgroup$
    – Alexey Ustinov
    Commented Nov 5, 2019 at 7:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .