|
%I #36 Oct 27 2023 22:00:46
%S 0,0,0,0,300,1296,4116,9984,21384,40800,72600,120960,192660,294000,
%T 434700,623616,873936,1197504,1611504,2131200,2778300,3571920,4538820,
%U 5702400,7095000,8744736,10690056,12964224,15612324,18673200,22199100,26234880,30840480,36067200,41983200,48646656,56134476
%N 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.
%C 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.
%C 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
%H Charlie Neder, <a href="/A054026/b054026.txt">Table of n, a(n) for n = 0..1000</a>
%H <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-8,6,6,-8,0,3,-1).
%F a(n) = (n+1)^2 * (n*(n-1)*(n-2) - 6*A002620(n-1)). - _Charlie Neder_, Jan 13 2019
%e 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.
%o (PARI) a(n) = (1+n)^2*(3*(-1)^n+4*n^3-18*n^2+20*n-3)/4; \\ _Jinyuan Wang_, Jun 27 2020
%Y Cf. A045991 (similar for a - b - c), A047929 (similar for a - b - c - d).
%K nonn,nice,easy
%O 0,5
%A _Asher Auel_, Jan 27 2000
%E a(9)-a(36) from _Charlie Neder_, Jan 13 2019
%E Incorrect formula removed by _Jinyuan Wang_, Jun 27 2020
|
