1
$\begingroup$

Observe the following Wolfram Mathematica code which results in a table of integers:

b[n_, k_] := b[n, k] = If[n == 0, 1, If[n == 1, If[k > 0, 1, 0],
Sum[Binomial[n-1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}] ] ];
t [n_, k_] := b[n, k] - If[k > 0, b[n, k-1], 0];
Table[Table[t[n, k], {k, 0, n}], {n, 0, 10}]

I'm struggling to interpret what this is actually doing. Clearly it's quite a complicated mess of if statements, but I'm not entirely sure if they are necessary or not. I obtained the expression from the OEIS.

I wanted to determine an expression (dependent on the two variables n and k) which would result in the table of integers seen there. Would somebody please convert the Mathematica code above into a simpler mathematical expression so that it's easier to understand? If this is not possible, can you at least try to explain what's going on, and perhaps give an expression which models the above under most conditions?

$\endgroup$

2 Answers 2

2
$\begingroup$

The b[n_, k_] := b[n, k] = (* stuff *) part is a common idiom for memoization; see this thread for more details.

The definition for t[n, k], which I will denote $t_{n,k}$, is just

$$t_{n,k}=b_{n,k}-\begin{cases}b_{n,k-1}&k>0\\0&\text{otherwise}\end{cases}$$

which leaves us with defining the recurrence for $b_{n,k}$:

$$b_{n,k}=\begin{cases}\sum\limits_{r=1}^n\binom{n-1}{r-1}b_{r-1,k-1}b_{n-r,k-1}&n>1\\1&n=0\text{ or }(n=1\text{ and }k>0)\\0&\text{otherwise}\end{cases}$$

$\endgroup$
2
  • $\begingroup$ So then, I think the key here is that the terms in the $b_n,_k$ are a product, correct? $\endgroup$ Commented Nov 16, 2017 at 7:46
  • $\begingroup$ Right, you have a sum of products of previous terms multiplied by a binomial coefficient to generate the next term. $\endgroup$ Commented Nov 16, 2017 at 8:13
1
$\begingroup$
b[n_, k_] := If[n == 0, 1, If[n == 1, If[k > 0, 1, 0],
Sum[Binomial[n-1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}] ] ];
t [n_, k_] := b[n, k] - If[k > 0, b[n, k-1], 0];
Table[Table[t[n, k], {k, 0, n}], {n, 0, 10}]

Ok. you can see b[n,k] before first if is not needed.

It says:

If n is 0 then no matter what k is, give me 1.

So b[0,k]=1 for any k.

Then it says if n is not 0 but it is 1, then check and see if k is positive or not, if k > 0 then give me 1, if k is 0 or less than 0, give me zero.

So,

b[1,k > 0] = 1 

and

b[1,k = 0] = b[1,k < 0] = 0.

up to here we are still in the condition of checking n==1. So next it says if n is not 1, the evaluate the

Sum[Binomial[n-1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}]

and return its value.

So

b[n,k] = Sum[Binomial[n-1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}]

for when n is not 1. we already check n=0 so it is obviously excluded here.

Then,

t[n,k] = b[n, k]-b[n, k-1]

for k>0 and it is b[n,k] for otherwise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.