login
The coefficients of the Girard-Waring formula; irregular array T(n,k), read by rows, for n >= 1 and 1 <= k <= A000041(n).
13

%I #65 Dec 21 2019 18:26:48

%S 1,1,-2,1,-3,3,1,-4,4,2,-4,1,-5,5,5,-5,-5,5,1,-6,6,9,-6,-12,6,-2,6,3,

%T -6,1,-7,7,14,-7,-21,7,-7,14,7,-7,7,-7,-7,7,1,-8,8,20,-8,-32,8,-16,24,

%U 12,-8,24,-16,-16,8,2,-8,-8,8,8,8,-8,1,-9,9,27,-9,-45

%N The coefficients of the Girard-Waring formula; irregular array T(n,k), read by rows, for n >= 1 and 1 <= k <= A000041(n).

%C Assume we have N <= n variables x_1, x_2, ..., x_N, and let S_n^{(N)} = x_1^n + x_2^n + ... + x_N^n be the n-th power sum of these variables. Following Gould (1999, p. 135), define the elementary symmetric polynomials e_1^{(N)}, e^2^{(N)}, ..., e_N^{(N)}, where e_j^{(N)} is the sum of all products of x_1, x_2, ..., x_N taken j at a time.

%C Since N <= n, without loss of generality, we may assume we have the extra variables x_{N+1}, ..., x_n, define e_1^{(n)}, e_2^{(n)}, ..., e_N^{(n)}, e_{N+1}^{(n)}, ..., e_n^{(n)}, and then set x_{N+1} = x_{N+2} = ... = x_n = 0. In such a case, we get e_j^{(N)} = e_j^{(n)} for j = 1..N, and e_j^{(n)} = 0 for j = (N+1)..n. Thus, we may drop the superscripts N and n on power sum and on the elementary symmetric polynomials and write S_n, and e_1, e_2, ..., e_n with the understanding that e_{N+1} = ... = e_n = 0. (See also the comments for A115131.)

%C The numbers T(n,k) are the coefficients of the power sum expansion in terms of the elementary symmetric polynomials, which is the Girard-Waring formula. That is, S_n = Sum(c(t_1,...,t_n) * e_1^t_1 * e_2^t_2 *...* e_n^t_n), summed over integer partitions of n, t_1 + 2*t_2 + ... + n*t_n = n with t_i >= 0 for i = 1..n. Here c(t_1,t_2,...,t_n) = n * (-1)^(t_2 + t_4 + ... + t_{2*floor(n/2)}) * (t_1 + ... + t_n - 1)!/(t_1!*...*t_n!).

%C Given a partition (t_1,...,t_n) of n (as defined above), we may use only those j's in {1,...,n} for which t_j > 0 and write the partition in the usual notation by repeating each such j t_j times (and place these j's in a non-descending order). E.g., the partition 1*3 + 2*1 + 3*0 + 4*0 + 5*0 of 5 can be written as [1,1,1,2]. Similarly, the partition 1*5 + 2*0 + 3*0 + 4*0 + 5*0 of 5 can be written as [1,1,1,1,1].

%C Instead of using the Abramowitz-Stegun order of partitions (as it is done in A115131), we use the usual notation for partitions (in terms of the positive integers that add up to n) and order them in lexicographic order. Unfortunately, this order of partitions does not correspond to any of the orders in the web link below.

%C If we let a(m) be the m-th term of the array, read as sequence, then

%C a(1) = T(1,1) = c([1]) = c(1),

%C a(2) = T(2,1) = c([1,1]) = c(2,0) with sign(T(2,1)) = (-1)^0 = 1,

%C a(3) = T(2,2) = c([2]) = c(0,1) with sign(T(2,2)) = (-1)^1 = -1,

%C a(4) = T(3,1) = c([1,1,1]) = c(3,0,0) with sign(T(3,1)) = (-1)^0 = 1,

%C a(5) = T(3,2) = c([1,2]) = c(1,1,0) with sign(T(4,1)) = (-1)^1 = -1,

%C a(6) = T(3,3) = c([3]) = c(0,0,1) with sign(T(3,3)) = (-1)^0 = 1,

%C a(7) = T(4,1) = c([1,1,1,1]) = c(4,0,0,0) with sign(T(4,1)) = (-1)^(0+0) = 1,

%C a(8) = T(4,2) = c([1,1,2]) = c(2,1,0,0) with sign(T(4,2)) = (-1)^(1+0) = -1,

%C a(9) = T(4,3) = c([1,3]) = c(1,0,1,0) with sign(T(4,3)) = (-1)^(0+0) = 1,

%C a(10) = T(4,4) = c([2,2]) = c(0,2,0,0) with sign(T(4,4)) = (-1)^(2+0) = 1,

%C a(11) = T(4,5) = c([4]) = c(0,0,0,1) with sign(T(4,5)) = (-1)^(0+1) = -1,

%C a(12) = T(5,1) = c([1,1,1,1,1]) = c(5,0,0,0,0),

%C a(13) = T(5,2) = c([1,1,1,2]) = c(3,1,0,0,0),

%C a(14) = T(5,3) = c([1,1,3]) = c(2,0,1,0,0),

%C a(15) = T(5,4) = c([1,2,2]) = c(1,2,0,0,0),

%C a(16) = T(5,5) = c([1,4]) = c(1,0,0,1,0),

%C a(17) = T(5,6) = c([2,3]) = c(0,1,1,0,0),

%C a(18) = T(5,7) = c([5]) = c(0,0,0,0,1), ...

%C (ascending ordered compositions in lexicographic order).

%H Kahtan H. Alzubaidy, <a href="https://www.maplesoft.com/applications/view.aspx?SID=153837">Symmetric polynomials by Maple</a>, 2015 (requires Maple 13).

%H Henri W. Gould, <a href="http://www.fq.math.ca/Scanned/37-2/gould.pdf">The Girard-Waring power sum formulas for symmetric functions and Fibonacci sequences</a>, Fibonacci Quart. 37(2) (1999), 135-140. [He uses a signed version of the elementary symmetric polynomials: a_j = (-1)^j*e_j. This is why here we have (-1)^(t_2 + t_4 + ... + t_{2*floor(n/2)}) in the formula for c(t_1,...,t_n) rather than (-1)^(t_1 + ... + t_n).]

%H OEIS, <a href="https://oeis.org/wiki/Orderings_of_partitions">Orderings of partitions</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Newton%27s_identities">Newton's identities</a>.

%e Array T(n,k) (with rows n >= 1 and columns k >= 1) begins as follows:

%e S_1: 1;

%e S_2: 1, -2;

%e S_3: 1, -3, 3;

%e S_4: 1, -4, 4, 2, -4;

%e S_5: 1, -5, 5, 5, -5, -5, 5;

%e S_6: 1, -6, 6, 9, -6, -12, 6, -2, 6, 3, -6;

%e S_7: 1, -7, 7, 14, -7, -21, 7, -7, 14, 7, -7, 7, -7, -7, 7;

%e ...

%e With N = n = 6, we have S_6 = 1*(e_1)^6 - 6*(e_1)^4*(e_2) + 6*(e_1)^3*(e_3) + 9*(e_1)^2*(e_2)^2 - 6*(e_1)^2*(e_4) - 12*(e_1)*(e_2)*(e_3) + 6*(e_1)*(e_5) - 2*(e_2)^3 + 6*(e_2)*(e_4) + 3*(e_3)^2 - 6*(e_6) = Sum_{i = 1..6} x_i^6.

%e If N = 4 < n = 6, we set e_5 = e_6 = 0 in the above expression, and we get that S_6 = 1*(e_1)^6 - 6*(e_1)^4*(e_2) + 6*(e_1)^3*(e_3) + 9*(e_1)^2*(e_2)^2 - 6*(e_1)^2*(e_4) - 12*(e_1)*(e_2)*(e_3) - 2*(e_2)^3 + 6*(e_2)*(e_4) + 3*(e_3)^2 = Sum_{i = 1..4} x_i^6.

%Y Cf. A115131 (Abramowitz-Stegun order of partitions).

%K sign,tabf

%O 1,3

%A _Mircea Merca_, Mar 19 2012

%E Various sections edited by _Petros Hadjicostas_, Dec 14 2019