8
$\begingroup$

Consider a generalisation of pascal's triangle of the following form $$1 \\ 1 \ 1 \\ 1\ 2\\ 1\ 3\ 2\\ 1\ 4\ 5\\ 1\ 5\ 9\ 5$$ That is to say, for even-numbered rows the $n$-th term is found by adding the $(n-1)$-th and $n$-th terms of the previous row, and for odd-numbered rows, the rule is similar, except that no new term is added on the end at all. (For example, there is no $1$ on the end of the third row above.)

Is it possible to find a explicit expression for the entries of this triangle?

Motivation: This problem is related to the following problem of enumerative geometry: 'Let $n\geq 2$, given $(n-2)$-dimensional subspaces $H_1,\ldots, H_{2(n-2)}$ of $\mathbb{P}^n$ how many lines are there, in general, intersecting all spaces?’

$\endgroup$
  • 4
    $\begingroup$ oeis.org/A008315 ? $\endgroup$ – Lord Shark the Unknown Dec 20 '19 at 7:21
  • 2
    $\begingroup$ See also the Wikipedia entry on Catalan's triangle. The table provided does include your triangle values, but with your rows appearing as rising diagonals. They moreover give a formula for the entries, suggesting a fairly definitive answer to your problem. $\endgroup$ – Semiclassical Dec 20 '19 at 7:25
7
$\begingroup$

If you start with Pascal's triangle

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1    

precede and follow with $0$s

0  1  0
0  1  1  0
0  1  2  1  0
0  1  3  3  1  0
0  1  4  6  4  1  0
0  1  5 10 10  5  1  0
0  1  6 15 20 15  6  1  0    

take differences between consecutive terms

1 -1
1  0 -1
1  1 -1 -1
1  2  0 -2 -1
1  3  2 -2 -3 -1 
1  4  5  0 -5 -4 -1
1  5  9  5 -5 -9 -5 -1

and finally drop the zero and negative values in the right-hand half

1 
1 
1  1 
1  2 
1  3  2  
1  4  5 
1  5  9  5 

you get your triangle.

So, one possibility for a formula is $${n \choose m}-{n \choose m-1}$$ assuming you start counting rows and columns that way starting from $0$. For example the $9$ here is ${6 \choose 2}-{6 \choose 1} = 15-6$

$\endgroup$
  • 1
    $\begingroup$ Very nice answer! $\endgroup$ – drhab Dec 20 '19 at 8:55
  • $\begingroup$ Do you have a proof in mind for why this method is correct? Although this solution is nicer I have accepted the one based on Catlan's triangle in the meantime. $\endgroup$ – A. Van Werde Dec 20 '19 at 15:38
  • 2
    $\begingroup$ @A.VanWerde once you have the formula it's easy to check that it satisfies the defining recurrence, after which you have your proof. (Although it's nice that you accepted my answer, I think this answer is more deserving of it!) $\endgroup$ – YiFan Dec 20 '19 at 16:10
  • $\begingroup$ @YiFan Thank you for the clarification and other answer. As you suggest I have accepted this answer. $\endgroup$ – A. Van Werde Dec 20 '19 at 16:13
  • 1
    $\begingroup$ @user21820: I recognised the numbers as coming from Catalan's Triangle which I know is based on the difference of two combinatorial coefficients $\endgroup$ – Henry Dec 20 '19 at 18:47
5
$\begingroup$

As the comment by Semiclassical indicates, this is highly relevant to Catalan's triangle, defined by the recurrences $C(n+1,k)=C(n+1,k-1)+C(n,k)$ for $1<k<n+1$, $C(n+1,n+1)=C(n+1,n)$ for $n\geq1$, and the boundary conditions $C(n,0)=1$ for $n\geq0$ and $C(n,1)=n$ for $n\geq1$. There is an explicit formula for $C(n,k)$ given by $$C(n,k)=\frac{(n+k)!(n-k+1)}{k!(n+1)!}.$$ Now, if the $k$th entry in the $n$th row of your triangle is called $D(n,k)$, then it is easy to notice that $D(n,k)=C(n-k+1,k-1).$ (You can convince yourself by looking at how $D(n,k)$ are entries along the rising diagonal on the table of values provided in the Wikipedia page, or by verifying the defining recurrence is satisfied like so.) Consequently we have $$\boxed{D(n,k)=C(n-k+1,k-1)=\frac{n!(n-2k+3)}{(k-1)!(n-k+2)!}}.$$

$\endgroup$

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.