On an Integer Sequence Related to a Product

of Trigonometric Functions, and its Combinatorial Relevance

Dorin Andrica

“Babeş–Bolyai” University Faculty of Mathematics and Computer Science Str. M. Kogǎlniceanu nr. 1 3400 Cluj–Napoca, Romania

               dandrica@math.ubbcluj.ro

Ioan Tomescu

University of Bucharest Faculty of Mathematics and Computer Science Str. Academiei, 14 R-70109 Bucharest, Romania

               ioan@math.math.unibuc.ro

Abstract

In this paper it is shown that for n ≡ 0 or 3 (mod 4), the middle term S(n) in the expansion of the polynomial (1 + x)(1 + x^{2}) ⋯ (1 + x^{n}) occurs naturally when one analyzes when a discontinuous product of trigonometric functions is a derivative of a function. This number also represents the number of partitions of T_{n}/2 = n(n + 1)/4, (where T_{n} is the nth triangular number) into distinct parts less than or equal to n. It is proved in a constructive way that S(n) ≥ 6S(n − 4) for every n ≥ 8, and an asymptotic evaluation of S(n)^{1/n} is obtained as a consequence of the unimodality of the coefficients of this polynomial. Also an integral expression of S(n) is deduced.

1 Notation and preliminary results

In a paper of Andrica [3] the following necessary and sufficient condition that some product of derivatives is also a derivative is deduced:

Theorem 1.1 Let n_{1}, …, n_{k} ≥ 0 be integers with n_{1} + … + n_{k} ≥ 1 and let α_{1}, …, α_{k} be real numbers different from zero. The function f_{n_{1},...,n_{k}}^{α_{1},...,α_{k}} : ℝ → ℝ, defined by

f_{n_{1},...,n_{k}}^{α_{1},...,α_{k}}(x) = \{ \begin{matrix}cos^{n_{1}}(α_{1}/x) ⋯ cos^{n_{k}}(α_{k}/x), & if x ≠ 0; \\ α, & if x = 0; \end{matrix}

is a derivative if and only if

α = \frac{1}{2^{n_{1}+...+n_{k}}} S(n_{1}, …, n_{k}; α_{1}, …, α_{k}),

where S(n_{1}, …, n_{k}; α_{1}, …, α_{k}) is the number of all choices of signs + and − such that

\underbrace{±α_{1} ± … ± α_{1}}_{n_{1} times} \underbrace{±α_{2} ± … ± α_{2}}_{n_{2} times} ± … \underbrace{±α_{k} ± … ± α_{k}}_{n_{k} times} = 0.  (1)

Note that this theorem extends one previously published in [2].

We shall present another combinatorial interpretations of the numbers

S(n_{1}, …, n_{k}; α_{1}, …, α_{k})

and an integral representation, while the last section is devoted to the sequence S(n) =

S(\underbrace{1, …, 1}_{n times}; 1, 2, 3, …, n) for n ≥ 1.

Let M be a multiset of type α_{1}^{n_{1}}α_{2}^{n_{2}} … α_{k}^{n_{k}}, i.e., a multiset containing α_{i} with multiplicity n_{i} for every 1 ≤ i ≤ k. It is clear that S(n_{1}, …, n_{k}; α_{1}, … α_{k}) is the number of ordered partitions having equal sums of M, i.e., of ordered pairs (C_{1}, C_{2}) such that C_{1} ∪ C_{2} = M, C_{1} ∩ C_{2} = ∅ and ∑_{x∈C_{1}} x = ∑_{y∈C_{2}} y = \frac{1}{2} ∑_{i=1}^{k} n_{i}α_{i}. Indeed, there exists a bijection between the set of all choices of + or − signs in (1) and the set of all ordered partitions with equal sums of M defined as follows: We put α_{i} from (1) in C_{1} if its sign is + and in C_{2} otherwise.

It is also clear that S(n_{1}, …, n_{k}; α_{1} …, α_{k}) is the term not depending on z in the expansion

F (z) = (z^{α_{1}} + \frac{1}{z^{α_{1}}} )^{n_{1}} (z^{α_{2}} + \frac{1}{z^{α_{2}}} )^{n_{2}} … (z^{α_{k}} + \frac{1}{z^{α_{k}}} )^{n_{k}} .  (2)

Wilf [10] outlines a proof that for n_{1} = n_{2} = … = n_{k} = 1, the coefficient of z^{n} in F (z) represents the number of ways of choosing + or − signs such that ±α_{1} ± α_{2} ± … ± α_{k} = n. If α_{1}, …, α_{k} are positive integers, from (2) one gets

F (z) = S(n_{1}, …, n_{k}; α_{1}, …, α_{k}) + ∑_{α≠0} a_{α}z^{α},  (3)

where the sum has only a finite number of terms and α and a_{α} are integers. By substituting z = cos t + i sin t, t ∈ ℝ in (3) one deduces

2^{n_{1}+...+n_{k}} ∏_{j=1}^{k}(cos α_{j}t)^{n_{j}} = S(n_{1}, …, n_{k}; α_{1}, …, α_{k}) + ∑_{α≠0} a_{α}(cos αt + i sin αt)

By integration on [0, 2π] we find the following integral expression of S(n_{1}, …, n_{k}; α_{1}, …, α_{k}):

S(n_{1}, …, n_{k}; α_{1}, …, α_{k}) = \frac{2^{n_{1}+...+n_{k}}}{2π} ∫_{0}^{2π}(cos α_{1}t)^{n_{1}} ⋯ (cos α_{k}t)^{n_{k}}dt.

2 A particular case and its connection with polynomial unimodality

An interesting particular case is obtained for n_{1} = n_{2} = … = n_{k} = 1 and α_{i} = i for every 1 ≤ i ≤ k. In this case S(n) is the number of ways of choosing + and − signs such that ±1 ± 2 ± … ± n = 0. Since now M = {1, 2, …, n} has sum T_{n} = n(n + 1)/2 and every class of an ordered bipartition of M must have sum T_{n}/2, it follows that S(n) = 0 for n ≡ 1 or 2 (mod 4) and S(n) ≠ 0 for n ≡ 0 or 3 (mod 4). The following theorem proposes several equivalent definitions of the sequence S(n) for n ≥ 1.

Theorem 2.1 For every n ≥ 1 the following properties are equivalent:

(i) S(n) is the number of choices of + and − signs such that ±1 ± 2 ± … ± n = 0; (ii) S(n) is the number of ordered bipartitions into classes having equal sums of {1, 2, …, n}; (iii) S(n) is the term not depending on x in the expansion of

(x + \frac{1}{x}) (x^{2} + \frac{1}{x^{2}} ) … (x^{n} + \frac{1}{x^{n}} );

(iv) S(n) is the number of partitions of T_{n}/2 into distinct parts, less than or equal to n, if n ≡ 0 or 3 (mod 4), and S(n) = 0 otherwise;

(v) S(n) is the number of distinct subsets of {1, …, n} whose elements sum to T_{n}/2 if n ≡ 0 or 3 (mod 4), and S(n) = 0 if n ≡ 1 or 2 (mod 4);

(vi) S(n) is the coefficient of x^{T_{n}/2} in the polynomial G_{n}(x) = (1 + x)(1 + x^{2}) … (1 + x^{n}) when n ≡ 0 or 3 (mod 4), and S(n) = 0 otherwise; (vii)

S(n) = \frac{2^{n−1}}{π} ∫_{0}^{2π} cos t cos 2t ⋯ cos nt dt;

(viii) S(n)/2^{n} is the unique real number α having the property that the function f : ℝ → ℝ, defined by

f(x) = \{ \begin{matrix}cos(1/x) cos(2/x) ⋯ cos(n/x), & if x ≠ 0; \\ α, & if x = 0; \end{matrix}

is a derivative.

Proof: Some equivalences are obvious or were shown in the general case. For example, the equivalence between (ii) and (v) is given by the bijection φ defined for every bipartition M = C_{1} ∪ C_{2} such that ∑_{x∈C_{1}} x = ∑_{y∈C_{2}} y by φ(C_{1} ∪ C_{2}) = C_{1} ⊂ M.

Let us denote

G_{n}(x) = (1 + x)(1 + x^{2}) … (1 + x^{n}) = ∑_{i=0}^{T_{n}} G(n, i)x^{i}.  (4)

Note that the property that the coefficient of x^{i} in G_{n}(x) is the number of distinct subsets of {1, …, n} whose elements sum to i was used by Friedman and Keith [5] to deduce a necessary and sufficient condition for the existence of a basic (n,k) magic carpet. Stanley [9], using the “hard Lefschetz theorem” from algebraic geometry, proved that the posets M(n) of all partitions of integers into distinct parts less than or equal to n are rank unimodal, by showing the existence of a chain decomposition for M(n). This fact is equivalent to the unimodality of the polynomial G_{n}(x), which implies that S(n) is the maximum coefficient in the expansion of G_{n}(x) for n ≡ 0 or 3 (mod 4). Stanley’s proof was subsequently simplified by Proctor [6].

The property of symmetry of the coefficients in (4), namely G(n, i) = G(n, T_{n} − i) for every 0 ≤ i ≤ T_{n} was pointed out by Friedman and Keith[5]; they also found the recurrence G(n, i) = G(n − 1, i) + G(n − 1, i − n). This latter recurrence, which is a consequence of the identity G_{n}(x) = G_{n−1}(x)(1+x^{n}), allows us to compute any finite submatrix of the numbers G(n, i) and thus the numbers S(n) = G(n, T_{n}/2).

Some values of S(n), starting with n = 3, are given in the following table:

\begin{matrix}n & S(n) & n & S(n) & n & S(n) & n & S(n) \\ 3 & 2 & 13 & 0 & 23 & 99,820 & 33 & 0 \\ 4 & 2 & 14 & 0 & 24 & 187,692 & 34 & 0 \\ 5 & 0 & 15 & 722 & 25 & 0 & 35 & 221,653,776 \\ 6 & 0 & 16 & 1,314 & 26 & 0 & 36 & 425,363,952 \\ 7 & 8 & 17 & 0 & 27 & 1,265,204 & 37 & 0 \\ 8 & 14 & 18 & 0 & 28 & 2,399,784 & 38 & 0 \\ 9 & 0 & 19 & 8,220 & 29 & 0 & 39 & 3,025,553,180 \\ 10 & 0 & 20 & 15,272 & 30 & 0 & 40 & 5,830,034,720 \\ 11 & 70 & 21 & 0 & 31 & 16,547,220 & 41 & 0 \\ 12 & 124 & 22 & 0 & 32 & 31,592,878 & 42 & 0 \end{matrix}

and thus the terms different from zero form a subsequence of the sequence A025591 in Sloane [7].

Another recurrence satisfied by the numbers G(n, i) is the following:

Lemma 2.2 We have G(n, i) = ∑_{j≥0} G(n − 1 − j, i − n + j).

Proof: Let P(k, i) denote the set of partitions of i into distinct parts such that the maximum part is equal to k. It is clear that

G(n, i) = |⋃_{j≥0} P(n − j, i)| = ∑_{j≥0} |P(n − j, i)| = ∑_{j≥0} G(n − 1 − j, i − n + j).

Indeed, there is a bijection between the set of partitions of i into distinct parts such that the maximum part equals n − j and the set of partitions of i − n + j into distinct parts less than or equal to n − 1 − j, defined by deleting the maximum part, equal to n − j, in any partition in P(n − j, i). Hence |P(n − j, i)| = G(n − 1 − j, i − n + j).

Theorem 2.3 For any n ≥ 8 we have S(n) ≥ 6S(n − 4).

Proof: For n ≤ 11 this inequality is verified by inspection.

For n ≥ 12 we shall propose a constructive proof yielding for any ordered partition of {1, …, n−4} in two classes C_{1} and C_{2} with equal sums six ordered partitions of {1, …, n} in two classes C′_{1} and C′_{2} having equal sums and all partitions generated will be distinct. Indeed, for any ordered bipartition with equal sums {1, …, n − 4} = C_{1} ∪ C_{2} we can generate six ordered bipartitions with equal sums {1, …, n} = C′_{1} ∪ C′_{2} as follows:

(a) C′_{1} = C_{1} ∪ {n − 3, n} and C′_{2} = C_{2} ∪ {n − 2, n − 1};

(b) C′_{1} = C_{1} ∪ {n − 2, n − 1} and C′_{2} = C_{2} ∪ {n − 3, n};

(c) Without loss of generality suppose 1 ∈ C_{1}. We define C′′_{1} = C_{1}\{1}, C′′_{2} = C_{2} ∪ {1}, C′_{1} = C′′_{1} ∪ {n − 2, n} and C′_{2} = C′′_{2} ∪ {n − 3, n − 1};

(d) Without loss of generality suppose 2 ∈ C_{1}. Now C′′_{1} = C_{1}\{2}, C′′_{2} = C_{2} ∪ {2}, C′_{1} = C′′_{1} ∪ {n − 1, n}, C′_{2} = C′′_{2} ∪ {n − 3, n − 2}.

Case (e) is a little more complicated, but we will be able to do it by combining two simple transformations.

(e) Suppose 1 ∈ C_{1}. If n − 4 belongs to the same class, we define C′′_{1} = C_{1}\{1, n − 4}, C′′_{2} = C_{2} ∪ {1, n − 4}, C′_{1} = C′′_{1} ∪ {n − 3, n − 2, n − 1} and C′_{2} = C′′_{2} ∪ {n}. This transformation resolves the imbalance of 2n − 6 between C′′_{1} and C′′_{2} and will be called of type A.

Otherwise 1 ∈ C_{1} and n − 4 ∈ C_{2}. If 2 ∈ C_{2} one defines C′′_{2} = C_{2}\{2, n − 4}, C′′_{1} = C_{1} ∪ {2, n − 4}, C′_{1} = C′′_{1} ∪ {n − 1} and C′_{2} = C′′_{2} ∪ {n, n − 2, n − 3}. This transformation balances classes C′′_{1} and C′′_{2} by 2n − 4 and will be called of type B.

Otherwise 2 ∈ C_{1}, hence C_{1} = {1, 2, …} and C_{2} = {n − 4, …}. If n − 5 ∈ C_{1} then C′′_{1} = C_{1}\{2, n − 5}, C′′_{2} = C_{2} ∪ {2, n − 5}, C′_{1} = C′′_{1} ∪ {n − 3, n − 2, n − 1} and C′_{2} = C′′_{2} ∪ {n}.

Otherwise n − 5 ∈ C_{2}, hence C_{1} = {1, 2, …}, C_{2} = {n − 4, n − 5, …}. Now if 3 ∈ C_{2} we move 3 and n − 5 into C_{1} and apply a type B transformation.

Otherwise 3 ∈ C_{1} and if n − 6 ∈ C_{1}, we add n − 6 and 3 to C_{2} and apply a type A transformation; otherwise C_{1} = {1, 2, 3, …} and C_{2} = {n − 4, n − 5, n − 6, …} and so on.

Note that a transformation of type A or B can be applied to every partition π = C_{1} ∪ C_{2} of {1, …, n − 4} since otherwise π must have classes C_{1} = {1, 2, 3, …} and C_{2} = {n − 4, n − 5, n − 6, …} such that for every k ∈ C_{1} verifying 1 ≤ k ≤ (n − 4)/2, the number n − k − 3 belongs to C_{2}. But this contradicts the property that C_{1} and C_{2} have the same sum for every n ≥ 8.

If 1 ∈ C_{2} this algorithm runs similarly and all partitions generated in this way are pairwise distinct.

(f) Suppose 3 ∈ C_{1}. If n − 4 ∈ C_{1}, we move 3 and n − 4 into C_{2} and annihilate the imbalance equal to 2n − 2 by defining C′_{1} = C′′_{1} ∪ {n, n − 1, n − 3} and C′_{2} = C′′_{2} ∪ {n − 2} (a type C transformation).

Otherwise C_{1} = {3, …}, C_{2} = {n − 4, …}. If 4 ∈ C_{2} we move 4 and n − 4 into C_{1} which produces an imbalance equal to 2n; then define C′_{1} = C′′_{1}∪{n−3} and C′_{2} = C′′_{2}∪{n, n−1, n−2} (a type D transformation).

Otherwise C_{1} = {3, 4, …} and C_{2} = {n−4, …}. If n−5 ∈ C_{1} we move 4 and n−5 into C_{2} and apply a type C transformation; otherwise C_{1} = {3, 4, …} and C_{2} = {n−4, n−5, …}. In this way we can apply a transformation of type C or D to every partition π of {1, …, n − 4} since otherwise C_{1} = {3, 4, 5, …}, C_{2} = {n − 4, n − 5, n − 6, …} such that for every k ∈ C_{1}, 3 ≤ k ≤ (n − 2)/2, we have n − k − 1 ∈ C_{2}. This is a contradiction, since in this case C_{1} and C_{2} cannot have the same sum for every n ≥ 12. As in the previous cases all partitions produced in this way are distinct.

This theorem has the following consequence:

Corollary 2.4 We have

S(n) > 6^{n/4} ≈ 1.56508^{n}  (5)

for every n ≡ 0 or 3 (mod 4) and n ≥ 16.

Proof: If n = 4k one gets S(4k) ≥ 6^{n/4−4}S(16) > 6^{n/4} since S(16) = 1, 314. Similarly, S(4k + 3) ≥ 6^{k−3}S(15) = 6^{(n−15)/4}S(15) > 6^{n/4} because S(15) = 722.

Note that in [5] the maximum coefficient in the polynomial G_{n}(x), which coincides with S(n) for n ≡ 0 or 3 (mod 4), is bounded below by 2(n + 1) for every n ≥ 10.

Although the lower bound (5) is exponential, its order of magnitude is far from being exact, as can be seen below.

Lemma 2.5

lim_{n→∞} S(4n)^{1/(4n)} = lim_{n→∞} S(4n + 3)^{1/(4n+3)} = 2.  (6)

Proof: Since the sequence of coefficients (G(n, i))_{i=0,...,T_{n}} in G_{n}(x) is unimodal ([6, 7]) and symmetric, and the first and last coefficient are equal to 1, it follows that for every n ≥ 5, n ≡ 0 or 3 (mod 4),

S(n) > \frac{2^{n} − 2}{T_{n} − 1} > \frac{2^{n}}{T_{n}} = \frac{2^{n+1}}{n^{2} + n}.

Indeed, ∑_{i=0}^{T_{n}} G(n, i) = G_{n}(1) = 2^{n} and T_{n} < 2^{n−1} for every n ≥ 5. On the other hand, S(n) < 2^{n} − 2, the number of ordered partitions having two classes of {1, …, n}, and these two inequalities imply (6).

A better upper bound for S(n) is \binom{n}{⌊n/2⌋} ≤ C_{1} \frac{2^{n}}{\sqrt{n}} for some constant C_{1} > 0. This follows from the following particular case of a result of Erdős (see [1] or [4]): Fix an interval of length 2 and consider the set of combinations ∑_{i=1}^{n} ε_{i}i, that lie within the interval, where ε_{i} ∈ {1, −1} for every 1 ≤ i ≤ n. The sets {i : ε_{i} = 1} that correspond to these combinations form an antichain in the poset of subsets of {1, …, n} ordered by inclusion. By Sperner’s theorem [8] the maximum number of elements in such an antichain is \binom{n}{⌊n/2⌋}, which is an upper bound for the number of combinations ∑_{i=1}^{n} ε_{i}i that sum to 0.

Conjecture 2.6 For n ≡ 0 or 3 (mod 4) we have

S(n) ∼ \sqrt{6/π} · \frac{2^{n}}{n\sqrt{n}} ,

where f(n) ∼ g(n) means that lim_{n→∞} f(n)/g(n) = 1.

This behavior was verified by computer experiments up to n = 100.

3 Acknowledgements

The authors are grateful to J. Radcliffe from University of Nebraska (Lincoln) for useful discussions related to the upper bound for S(n). Also, the authors are indebted to the referee of the paper for his/her very useful remarks, including the present form of Conjecture 2.6.

References

[1] M. Aigner and G.-M. Ziegler, Proofs from THE BOOK, Springer Verlag, Berlin, Heidelberg, 1998.

[2] D. Andrica and Ş. Buzeţeanu, On the product of two or more derivatives, Revue Roumaine Math. Pures Appl., 30 (1985), 703–710.

[3] D. Andrica, A combinatorial result concerning the product of more derivatives, Bull. Calcutta Math. Soc., 92 (4) (2000), 299–304.

[4] P. Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc., 5 (1945), 898–902.

[5] E. Friedman and M. Keith, Magic carpets, Journal of Integer Sequences, 3 (2000), Article 00.2.5.

[6] R. Proctor, Solution of two difficult combinatorial problems with linear algebra, Amer. Math. Monthly, 89 (1982), 721–734.

[7] N. J. A. Sloane The On-Line Encyclopedia of Integer Sequences,

    http://www.research.att.com/~njas/sequences/.

[8] E. Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Zeitschrift, 27 (1928), 544–548.

[9] R. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Alg. Discr. Math., 1 (1980), 164–184.

[10] H. Wilf, Generatingfunctionology, Academic Press, New York, 1994.

2000 Mathematics Subject Classification: 05A15, 05A16, 05A17, 05A18, 06A07, 11B75 . Keywords: unimodal polynomial, triangular number, derivative, partition, Sperner’s theorem, generating function

(Concerned with sequence \underline{A025591}.)

Received September 25, 2002; revised version received November 3, 2002. Published in Journal of Integer Sequences November 14, 2002.

Return to Journal of Integer Sequences home page.