A054026 a(n) is the number of sets of natural numbers [a,b,c,d,e] that can be produced with the numbers [0..n] such that the values of all the distinct parenthesized expressions of a-b-c-d-e are different.

0, 0, 0, 0, 300, 1296, 4116, 9984, 21384, 40800, 72600, 120960, 192660, 294000, 434700, 623616, 873936, 1197504, 1611504, 2131200, 2778300, 3571920, 4538820, 5702400, 7095000, 8744736, 10690056, 12964224, 15612324, 18673200, 22199100, 26234880, 30840480, 36067200, 41983200, 48646656, 56134476

Offset: 0

Author

Asher Auel, Jan 27 2000

Keywords

• nonn
• nice
• easy

Comments

There are 14 ways to put parentheses in the expression a - b - c - d - e: ((a - (b - c)) - d) - e, (((a - b) - c) - d) - e, ((a - b) - (c - d)) - e, etc. This sequence describes how many sets of natural numbers [a,b,c,d,e] can be produced with the numbers {0,1,2,3,...,n} such that the values of all the distinct expressions are different.

It can be shown that in the set of expressions obtained this way, for any number of variables, a is always positive, b is always negative, and the other variables appear with every possible combination of signs. Therefore, the valid k-tuples of numbers in [0..n] are precisely those such that every subset of {c,d,e,...}, including the empty subset, has a distinct sum. For 5 variables, there are n*(n-1)*(n-2) ways to choose distinct, nonzero values for c, d, and e. For each k, there are floor((n-1)/2) ways to choose distinct numbers x and y in [0..n] such that x + y = k. Summing over all k in [0..n], allowing arbitrary permutations of {x,y,k}, and allowing a and b to be any value gives the formula below. - Charlie Neder, Jan 13 2019

Examples

			For example, no such sets can be produced with only 0's, only 0's and 1's, only 0's and 1's and 2's, only 1's and 2's and 3's; with {0,1,2,3,4}, 300 such sets can be produced.
		

Links

• Charlie Neder, Table of n, a(n) for n = 0..1000
• Index entries for sequences related to parenthesizing
• Index entries for linear recurrences with constant coefficients, signature (3,0,-8,6,6,-8,0,3,-1).

Crossrefs

Cf. A045991 (similar for a - b - c), A047929 (similar for a - b - c - d).

Programs

Mathematica

LinearRecurrence[{3,0,-8,6,6,-8,0,3,-1},{0,0,0,0,300,1296,4116,9984,21384},40] (* Harvey P. Dale, May 25 2025 *)

PARI

a(n) = (1+n)^2*(3*(-1)^n+4*n^3-18*n^2+20*n-3)/4; \\ Jinyuan Wang, Jun 27 2020

Formula

a(n) = (n+1)^2 * (n*(n-1)*(n-2) - 6*A002620(n-1)). - Charlie Neder, Jan 13 2019

Extensions

a(9)-a(36) from Charlie Neder, Jan 13 2019

Incorrect formula removed by Jinyuan Wang, Jun 27 2020