×

A minimum problem for finite sets of real numbers with nonnegative sum. (English) Zbl 1273.11045

Summary: Let \(n\) and \(r\) be two integers such that \(0 < r \leq n\); we denote by \(\gamma(n, r)\) \([\eta(n, r)]\) the minimum [maximum] number of the nonnegative partial sums of a sum \(\sum^n_{1=1} a_i \geq 0\), where \(a_1, \dots, a_n\) are \(n\) real numbers arbitrarily chosen in such a way that \(r\) of them are nonnegative and the remaining \(n - r\) are negative. We study the following two problems:
(P1) which are the values of \(\gamma(n, r)\) and \(\eta(n, r)\) for each \(n\) and \(r\), \(0 < r \leq n\)?
(P2) if \(q\) is an integer such that \(\gamma(n, r) \leq q \leq \eta(n, r)\), can we find \(n\) real numbers \(a_1, \dots, a_n\), such that \(r\) of them are nonnegative and the remaining \(n - r\) are negative with \(\sum^n_{1=1} a_i \geq 0\), such that the number of the nonnegative sums formed from these numbers is exactly \(q\)?

MSC:

11B75 Other combinatorial number theory
05A15 Exact enumeration problems, generating functions
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. Manickam and D. Miklós, “On the number of nonnegative partial sums of a nonnegative sum,” Colloquia Mathematica Societatis Janos Bolyai, vol. 52, pp. 385-392, 1987. · Zbl 0726.11014
[2] C. Bisi and G. Chiaselotti, “A class of lattices and boolean functions related to a,” Manickam-Miklös-Singhi Conjecture. In press. · Zbl 1259.05178
[3] C. Bisi and G. Chiaselotti, “Extension results for boolean maps and a class of systems of linear inequalities,” http://arxiv.org/abs/1012.5486. · Zbl 1259.05178
[4] G. Chiaselotti, “On a problem concerning the weight functions,” European Journal of Combinatorics, vol. 23, no. 1, pp. 15-22, 2002. · Zbl 0998.05064
[5] A. Bhattacharya, “On a conjecture of Manickam and Singhi,” Discrete Mathematics, vol. 272, no. 2-3, pp. 259-261, 2003. · Zbl 1030.05116
[6] A. Bhattacharya, Some problems in combinatorics, Ph.D. thesis, Indian Institute of Technology, Bombay, India, 2004.
[7] T. Bier and N. Manickam, “The first distribution invariant of the Johnson-scheme,” Southeast Asian Bulletin of Mathematics, vol. 11, no. 1, pp. 61-68, 1987. · Zbl 0723.05120
[8] G. Chiaselotti, G. Infante, and G. Marino, “New results related to a conjecture of Manickam and Singhi,” European Journal of Combinatorics, vol. 29, no. 2, pp. 361-368, 2008. · Zbl 1131.05093
[9] G. Marino and G. Chiaselotti, “A method to count the positive 3-subsets in a set of real numbers with non-negative sum,” European Journal of Combinatorics, vol. 23, no. 5, pp. 619-629, 2002. · Zbl 1021.05003
[10] N. Manickam, “Distribution invariants of association schemes,” Congressus Numerantium, vol. 61, pp. 121-131, 1988. · Zbl 0676.05026
[11] N. Manickam, “First distributed sets in the association scheme of bilinear forms,” Colloquia Mathematica Societatis Janos Bolyai, vol. 60, pp. 465-468, 1992. · Zbl 0785.05088
[12] B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, New York, NY, USA, 2nd edition, 2002. · Zbl 1002.06001
[13] P. Erdos, C. Ko, and R. Rado, “Intersection theorems for systems of finite sets,” Quarterly Journal of Mathematics, vol. 2, no. 12, pp. 313-320, 1961. · Zbl 0100.01902
[14] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, Cambridge, UK, 1997. · Zbl 0889.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.