3
$\begingroup$

I am not sure if this is an appropriate puzzle for this site, but I searched and found 1 or 2 other types of puzzles like this. This is an original puzzle.

Find the missing numbers in rows 8 through 11 of this triangular array:

1
1 1
-3 2 1
15 -7 3 1
-105 40 -12 4 1
945 -315 78 -18 5 1
-10395 3150 -693 132 -25 6 1
? -38115 7749 -1317 205 -33 7 1
-2027025 ? -103950 16416 -2280 300 -42 8 1
34459425 -8783775 ? -243540 31470 -3690 420 -52 9 1
-654729075 160810650 -28783755 4169880 ? 55980 -5670 568 -63 10 1
$\endgroup$
0
3
$\begingroup$

I have an answer but you're not going to like it. Write $a_{nm}$ for the entry in row n, column m. The 1 at top left is (0,0). Then $a_{nm}$ is

1 if $m=n$ and otherwise is
$(-1)^{m+n+1}(2(n-m)-1)!!\sum_{k=1}^{n-m}\frac{\binom{n-m-1}{k-1}\binom{m+1}{k}}{2k-1}$.

Here

$n!!=n(n-2)\ldots$ where the product stops just before the first nonpositive number (which for odd $n$ as here is the same as "stops at 1"). Instead of $(2(n-m)-1)!!$ we could write $\frac{2(n-m)!}{2^{n-m}(n-m)!}$.

Accordingly, the missing numbers (left to right) are

135135, 540540, 1621620, -513150.

I am dissatisfied with this because

I have this annoying special case for when m=n; the alternating signs have been shoved in by force rather than falling out naturally; the answer is a sum rather than something more explicit; there is no obvious combinatorial interpretation. I expect there is a nicer closed form that makes it more apparent what is actually going on here.

It feels as if

there's some sort of multinomial thing going on here -- imagine dividing $n-1$ things into a set of $m$ and a set of $n-1-m$; then we're choosing $k$ things from one of those sets and $k-1$ from the other; perhaps we should somehow be re-expressing this in terms of first choosing $2k-1$ things and then splitting them up somehow, which might let us get rid of the annoying $2k-1$ in the denominator via the usual binomial-coefficient identities.

$\endgroup$
1
  • $\begingroup$ I didn't expect anyone would find a formula for the terms. Bravo! I will post the easier solution ASAP. $\endgroup$
    – John L
    Jan 9 at 19:14
0
$\begingroup$

Partial answer

Writing the 3rd row of the numbers: -3, -7, -12, -18, ...., letting the starting number be $\epsilon$, the difference of the first and second number in the series be $\lambda$, the difference of difference be $\delta$, ignoring the negative signs, we get:

+-------------+-----+-----+----+
| n-th series | ϵ | λ | δ |
+-------------+-----+-----+----+
| 3 | 3 | 4 | 1 |
| 4 | 15 | 25 | 3 |
| 5 | 105 | 105 | 63 |
+-------------+-----+-----+----+

The question is:

Will this help?

$\endgroup$
0
$\begingroup$

The numbers in the first column are: $1, 1, -3, 15, -105, 945, ...$
Except at the beginning, these alternate in sign and are found by multiplying all the odd numbers up to a certain point. $1, 1, -1*3, 1*3*5, -1*3*5*7, 1*3*5*7*9, ...$
Like @Gareth-McCaughan points out, these have a notation using the double factorial symbol. $(-1)!!=-1$, so the first number is $-(-1)!!$.
The second number is $1!!$, the third is $-3!!$, etc. There are some other patterns that can be spotted on the diagonals such as all the 1's on the first diagonal.
The second and third diagonal also seem to follow a simple pattern. The key to finding all the other numbers is the diagonals.
A pattern can be seen if you take repeated differences.
The first diagonal is: $1, 1, 1, 1, 1, 1, ...$
the differences between terms in this sequence are: $0, 0, 0, 0, ...$

The second diagonal is: $1, 2, 3, 4, 5, ...$
and the differences between successive terms are: $1, 1, 1, 1, 1, ...$
the differences of the differences (i.e. the second differences) are: $0, 0, 0, 0, 0, ...$


The third diagonal is: $-3, -7, -12, -18, -25, -33, ...$
the differences are: $-4, -5, -6, -7, -8, ...$
the second differences are: $-1, -1, -1, -1, -1, ...$
the third differences are: $0, 0, 0, 0, 0, ...$


The fourth diagonal is: $15, 40, 78, 132, 205, ...$
differences: $25, 38, 54, 72, ...$
That doesn't look so promising, but maybe if we take the differences again?
second differences: $13, 16, 19, 22, ...$
That looks better; the successive terms differ by 3.
third differences: $3, 3, 3, 3, 3, ...$
fourth differences: $0, 0, 0, 0, 0,...$

The numbers are getting bigger, but there seems to be something to this. Let's keep pressing on.

The fifth diagonal is: $-105, -315, -693, -1317, -2280, -3690,...$
differences: $-210, -378, -624, -963, -1410,...$
second differences: $-168, -246, -339, -447, ...$
third differences: $-78, -93, -108, ...$
fourth differences: $-15, -15, -15, -15, ...$
fifth differences: $0, 0, 0, 0, 0, ...$

Maybe in the sixth diagonal, the sixth differences will all be 0? Let's see.
$945, 3150, 7749, 16416, 31470, 55980, 93870,...$
differences: $2205, 4599, 8667, 15054, 24510, 37890, ...$
second differences: $2394, 4068, 6387, 9456, 13380, ...$
third differences: $1674, 2319, 3069, 3924, ...$
fourth differences: $645, 750, 855, ...$
fifth differences: $105, 105, 105, ....$
sixth differences: $0, 0,0,0,0,...$

So, that's the pattern.

In the $k^{th}$ diagonal, the $k^{th}$ successive differences are 0. The $(k-1)^{th}$ differences in the cases calculated above (for diagonals 3 through 6) were: $-1, 3, -15, 105$. Look familiar? These are the products of the odd numbers again just like in the first column! They have to be those numbers to make the pattern of the differences and everything else work out. Knowing everything about the differences now, you can work backwards to find out what all the original numbers in the triangle have to be.

All those calculations made me hungry. Luckily, my wife is making the world's best spaghetti using a recipe she and her friend stole from some rich guy in a local mansion. It's a funny story how they got the recipe.

$\endgroup$
7
  • $\begingroup$ The pattern you describe doesn't sound as if it's enough to determine the whole triangle, but maybe I'm misunderstanding something. Suppose $a_{nm}=(2(n-m)-1)!!\binom{n}{n-m}$. Then the $d$th diagonal is a polynomial of degree $d$ (so its $d$th differences are zero) whose leading coefficient is $(2d-1)!!d!$ (so its $(d-1)$th differences are all $(2d-1)!!$), and the entries for $m=0$ are $(2m-1)!!$. If we multiply this by $(-1)^{m+n+1}$ then don't we get all the properties you describe here? But it's not the same triangle. $\endgroup$
    – Gareth McCaughan
    Jan 9 at 21:53
  • $\begingroup$ @GarethMcCaughan Yes! those properties are not enough to characterize the whole triangular sequence. But, that and the filled in numbers given already should be enough to fill in the missing numbers. $\endgroup$
    – John L
    Jan 9 at 22:56
  • $\begingroup$ It's not obvious to me how this would suffice to fill in the second and third numbers. For that diagonal you know that the first number must be 135135, that the 7th differences must be constant at -10395, and that the fourth number must be 4169880. But that doesn't come close to determining the others. There must be more to how you obtained this triangle, even if you didn't use a formula like mine. How was it constructed, exactly? $\endgroup$
    – Gareth McCaughan
    Jan 10 at 0:06
  • $\begingroup$ I'm not sure if those two observations alone (i.e. the first column is the double factorial of the odd numbers with alternating minus signs + the observation about the repeated differences) and the given numbers is enough to uniquely identify the missing numbers. I thought it would be enough. I just deleted a few of the numbers to make the puzzle. I discovered the triangular sequence as a solution of a problem in probability-the coefficients of a polynomial that arises in calculating average Euclidean distance between a fixed point and a multivariate normal random variable. $\endgroup$
    – John L
    Jan 10 at 0:36
  • $\begingroup$ There is a different polynomial for each dimension and each row represents a different dimension. But, the sequence is just interesting by itself I think. If my paper is accepted, will post a link. Thank you for being interested. $\endgroup$
    – John L
    Jan 10 at 0:36

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.