Sequence A059117 in the OEIS is $\lambda(k, n)$, the number of ways to place $n$ distinct intervals with exactly $k$ starting and stopping points. (See the entry for clarification on what that means.) The $\lambda$-numbers are defined by

\begin{align*} \lambda(k, n) &= {k \choose 2} (\lambda(k, n - 1) + 2 \lambda(k - 1, n - 1) + \lambda(k - 2, n - 1)) \\ \lambda(k, 0) &= [k = 0], \end{align*} where $[k = 0]$ is an Iverson bracket. The comments at the OEIS note that $\lambda$ can be expressed as $$\lambda(k, n) = \sum_j {k \choose j} {j \choose 2}^n (-1)^{k - j} .$$ How can you derive this sum from the recurrence relation?

I can check that the given sum satisfies the recurrence, but I can't derive it. I've tried ordinary and exponential generating functions, but they get really messy. For example, the ordinary generating function $A_k(x) = \sum_{n \geq 0} \lambda(k, n) x^n$ satisfies the three-term recurrence $$(1 - {k \choose 2} x) A_k = x {k \choose 2} (2 A_{k - 1} + A_{k - 2}).$$

  • $\begingroup$ All the entry says is, "Number of ways of placing n identifiable positive intervals with a total of exactly k starting and/or finishing points." I don't see how that clarifies what you have said at all. What is a starting or finishing point? Can you give an example? $\endgroup$
    – saulspatz
    Jul 9 '19 at 23:32
  • $\begingroup$ @saulspatz I don't actually care about the combinatorial interpretation. I'm only interested in how to derive the sum from the recurrence. Both are stated in the "FORMULA" section of the OEIS entry, but without proof. $\endgroup$
    – Robert D-B
    Jul 9 '19 at 23:36
  • 1
    $\begingroup$ The exponent in the formula should be $n$ instead of $m$. $\endgroup$
    – saulspatz
    Jul 9 '19 at 23:45
  • $\begingroup$ @saulspatz Thanks for the catch! Fixed now. $\endgroup$
    – Robert D-B
    Jul 9 '19 at 23:47

Define with initial values $\, a_0(n) = \delta_{0n}\,$ the recursion $$ a_k(n) = {n \choose 2} (a_{k-1}(n) + 2 a_{k-1}(n - 1) + a_{k-1}(n - 2)). \tag1$$

Define the exponential generating function $$ f_k(x) := \sum_{n=0}^\infty a_k(n)x^n/n! \tag2 $$ and the related e.g.f. $$ g_k(x) = \sum_{n=0}^\infty b_k(n)x^n/n! := f_k(x) \exp(x) \tag3$$ where $\,b_k\,$ is the Binomial transform of $\,a_k\,$ in OEIS terminology.

Notice that $$ g_k'(x) = (f_k(x) + f_k'(x))\exp(x) \tag4 $$ and $$ g_k''(x) = (f_k(x) + 2f_k'(x) + f_k''(x))\exp(x). \tag5 $$ Notice that equation $(1)$ implies that $$ g_k(x) = x^2/2\; g_{k-1}''(x). \tag6 $$ Referring back to equation $(3)$ this implies that $$ b_k(n) = {n \choose 2}b_{k-1}(n) \tag7$$ and given the initial value of $\, b_0(n)=1\,$ this implies $$ b_k(n) = {n \choose 2}^k. \tag8$$ Applying the inverse binomial transform gives us the result $$ a_k(n) = \sum_{j=0}^n (-1)^{n - j}{n \choose j} {j \choose 2}^k .\tag9$$

  • $\begingroup$ This is an excellent example of the generating function approach! The sum made it clear that exponential generating functions were useful somehow, but I couldn't work it out. Thanks for showing me. $\endgroup$
    – Robert D-B
    Jul 10 '19 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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