# On Some Numbers Related to Extremal Combinatorial Sum Problems

Authors: D. Petrassi
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

Letn, d, and r be three integers such that 1
≤
r
,
d
≤
n. Chiaselotti (2002) defined γ
n
,
d
,
r as the minimum number of the nonnegative partial sums with d summands of a sum ∑
1
=
1
n
a
i
≥
0, where a
1
,
…
,
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. Chiaselotti (2002) and Chiaselotti et al. (2008) determine the values of γ
n
,
d
,
r for particular infinite ranges of the integer parameters n, d, and r. In this paper we continue their approach on this problem and we prove the following results: (i) γ
(
n
,
d
,
r
)
≤
(
r
d
)
+
(
r
d
-
1
) for all values of n, d, and r such that (d
-
1)
/
d
n
-
1
≤
r
≤
(d
-
1)
/
d
n; (ii) γ
d
+
2
,
d
,
d
=
d
+
1
.


---

## Body

## 1. Introduction

Letn, d, and r be three fixed integers such that 1
≤
r,d
≤
n. We set [
n
]
:
=
{
1
,
…
,
n
} and
(1)
W
n
:
=
{
f
:
[
n
]
⟶
ℝ
:
∑
x
∈
[
n
]
‍
f
(
x
)
≥
0
}
.
The elements of W
n are called n-weight functions and, if f
∈
W
n, we set f
+
=
|
{
a
∈
[
n
]
:
f
(
a
)
≥
0
}
|. For example, if f
(
1
)
=
f
(
2
)
=
f
(
3
)
=
1
,
f
(
4
)
=
f
(
5
)
=
-
1
/
2, and f
(
6
)
=
f
(
7
)
=
-
1, then f
+
=
3. If f
∈
W
n, we also set Φ
(
f
,
d
)
:
=
{
A
⊆
[
n
]
:
|
A
|
=
d
,
∑
a
∈
A
‍
f
(
a
)
≥
0
} (we call (
d
+
,
n
)-subset of f a generic element of Φ
(
f
,
d
)), ϕ
(
f
,
d
)
:
=
|
Φ
(
f
,
d
)
|, and
(2)
γ
(
n
,
d
,
r
)
:
=
min
⁡
{
ϕ
(
f
,
d
)
:
f
∈
W
n
,
f
+
=
r
}
.
These numbers γ
(
n
,
d
,
r
) were introduced in [1] in order to refine the study of a conjecture of Manickam-Miklós-Singhi (for further information on this conjecture and on its links with the numbers γ
(
n
,
d
,
r
) see [1–4]). The complete determination of the numbers γ
(
n
,
d
,
r
) is a very difficult task and actually they are known only for a relatively small range of the integer parameters n,d, and r. In [1–3] some of the numbers γ
(
n
,
d
,
r
) have been determined, and we report these values:(
n
-
1
d
-
1
) if r
≤
d
≤
n
/
2,
(
n
-
r
d
-
r
) if r
≤
d
<
n and r
<
(
n
/
(
n
-
d
)
),
(
r
d
) if d
<
r
<
n and r
>
(
(
d
-
1
)
/
d
)
n,
(
n
-
1
d
-
1
) if r
=
1,
(
r
d
)
+
(
r
-
1
d
-
1
) if r
≥
d and r
=
(
(
d
-
1
)
/
d
)
n,
(
r
d
)
+
(
r
-
1
d
-
1
) if n
=
2
d
+
2
,
r
=
2
d
-
1 and d
≥
2.In particular, in [3] the authors prove the last of these results using Hall’s matching theorem.Also, in [2, 5] the numbers γ
(
n
,
d
,
r
) were linked within the context of the combinatorial order theory. More in detail, in [2] the authors introduce two new classes of lattices of signed integer partitions, S
(
n
,
r
) and S
(
n
,
d
,
r
), and they show that the numbers γ
(
n
,
d
,
r
) can be interpreted as the cardinality of particular types of up-sets in the previous lattices.On the other hand, the latticesS
(
n
,
r
) and S
(
n
,
d
,
r
) can also be considered as particular types of discrete dynamical systems. In this context many properties of the numbers γ
(
n
,
d
,
r
) can be related to the evolution rules that characterize S
(
n
,
r
) and S
(
n
,
d
,
r
) as discrete dynamical systems (see [6, 7]). For very recent studies concerning the discrete dynamical systems see [8–12].In this paper we determine some new identities and new bounds for the numbersγ
(
n
,
d
,
r
). In particular, we show that(i)
γ
(
n
,
d
,
r
)
≤
(
r
d
)
+
(
r
d
-
1
) for all values of n
,
d, and r satisfying (
(
d
-
1
)
/
d
)
(
n
-
1
)
≤
r
≤
(
(
d
-
1
)
/
d
)
n (Corollary 5),
(ii)
γ
(
n
,
d
,
r
)
=
(
r
d
)
+
(
r
d
-
1
)
=
d
+
1 in the case n
=
d
+
2 and r
=
d (Proposition 8).Finally we provide a combinatorial interpretation of the inequality(
(
d
-
1
)
/
d
)
(
n
-
1
)
<
r
≤
(
(
d
-
1
)
/
d
)
n.The remaining part of this paper is structured as follows. In Section2 we provide the necessary notations for the sequel. In Section 3 we establish our results and, finally, in Section 4 we briefly describe conclusions and possible future research approaches.


## 2. Notations

In the sequel, we will assume that a generic weight functionf
∈
W
n, with f
+
=
r, has the form
(3)
1
⋯
r
r
+
1
⋯
n
↓
⋯
↓
↓
⋯
↓
x
1
⋯
x
r
y
1
⋯
y
n
-
r
,
with
(4)
x
1
≥
x
2
≥
⋯
≥
x
r
≥
0
>
y
1
≥
y
2
≥
⋯
≥
y
n
-
r
.
Let us call the indexes 1
,
…
,
r the nonnegative elements of f and the indexes r
+
1
,
…
,
n the negative elements of f. The real numbers x
1
,
…
,
x
r are said to be the nonnegative values of f and the numbers y
1
,
…
,
y
n
-
r are said to be the negative values of f.Ifi
1
,
…
,
i
α are nonnegative elements of f and j
1
,
…
,
j
β are negative elements of f, with i
1
<
⋯
<
i
α and j
1
<
⋯
<
j
β, a subset A of {
1
,
…
,
n
} is said to be of type
(5)
[
i
1
,
…
,
i
α
]
a
+
[
j
1
,
…
,
j
β
]
b
-
if A is made of a elements chosen in {
i
1
,
…
,
i
α
} and b elements chosen in {
j
1
,
…
,
j
β
}.LetX be a finite set of integers. If q is an integer less than or equal to |
X
|, we call q-string on X a sequence a
1
,
…
,
a
q, where a
1
,
…
,
a
q are distinct elements of X such that a
1
<
⋯
<
a
q. In this paper, each subset Y of X with q elements will be identified with the q-string of its elements ordered in increasing way. When i
1
,
…
,
i
k are nonnegative elements of f and j
1
,
…
,
j
l are negative elements of f, with i
1
<
⋯
<
i
k
<
j
1
<
⋯
<
j
l, the (
k
+
l
)-stringi
1
⋯
i
k
j
1
⋯
j
lwill be written in the form
(6)
i
1
⋯
i
k
∣
(
j
1
-
r
)
⋯
(
j
l
-
r
)
(thus j
1
-
r
,
…
,
j
l
-
r
∈
{
1
,
…
,
n
-
r
}).For example, ifn
=
10 and r
=
7, the 4-string 1269 will be written in the form 126
∣
2.Using the string-terminology instead of the set-terminology, in the sequel, we will call a(
d
+
,
n
)-subset of f a (
d
+
,
n
)-string of f.


## 3. The Results

The range of values of the integer parametersn,d, and r that we are going to study is the following: d
≤
r
≤
n. As reported in the first section, we already know that the next result holds for γ
(
n
,
d
,
r
) in the case r
>
(
(
d
-
1
)
/
d
)
n. We state it referring to its proof.Proposition 1.
Ifr
≥
d and r
>
(
(
d
-
1
)
/
d
)
n, then γ
(
n
,
d
,
r
)
=
(
r
d
).Proof.
See [1].Therefore we concentrate our attention on the caser
≤
(
(
d
-
1
)
/
d
)
n. In order to examine it, we start by considering the partition 𝒫 of the real interval (
0
,
(
(
d
-
1
)
/
d
)
n
]:
(7)
𝒫
=
{
0
,
d
-
1
d
,
2
d
-
1
d
,
…
,
(
n
-
1
)
d
-
1
d
,
n
d
-
1
d
}
.
The following proposition establishes when an interval determined by 𝒫 contains an integer.Proposition 2.
Ifk
=
1
,
…
,
n and if n
-
k
≢
d
0, there exists a unique integer r such that
(8)
d
-
1
d
(
n
-
k
)
<
r
≤
d
-
1
d
(
n
-
k
+
1
)
,
and r coincides with ⌊
(
(
d
-
1
)
/
d
)
(
n
-
k
+
1
)
⌋. Furthermore if n
-
k
≡
d
0, no integer r satisfies (8).Proof.
Letk
∈
{
1
,
…
,
n
} and set m
=
n
-
k
+
1. Since the interval (
(
(
d
-
1
)
/
d
)
(
m
-
1
)
,
(
(
d
-
1
)
/
d
)
m
] has length (
(
d
-
1
)
/
d
)
<
1, there is at most one integer r that satisfies (8). Let us now write m in the form
(9)
m
=
q
~
d
+
s
,
where q
~,s are integers such that q
~
≥
0
,
1
≤
s
≤
d. Let us suppose now that n
-
k
≢
d
0; that is, m
≢
d
1; then we have 2
≤
s
≤
d.
Letr
=
⌊
(
(
d
-
1
)
/
d
)
m
⌋. We show that r satisfies (8).
Firstly, the second inequality is straightforward; secondly, for the first inequality we observe(10)
d
-
1
d
(
m
-
1
)
=
d
-
1
d
(
q
~
d
+
s
-
1
)
=
q
~
(
d
-
1
)
+
(
s
-
1
)
d
-
1
d
.
Furthermore
(11)
r
=
⌊
d
-
1
d
(
q
~
d
+
s
)
⌋
=
⌊
q
~
(
d
-
1
)
+
s
-
s
d
⌋
=
q
~
(
d
-
1
)
+
(
s
-
1
)
.
Therefore r
>
(
(
d
-
1
)
/
d
)
(
m
-
1
), since s
≥
2.
Ifn
-
k
≡
d
0, that is, m
≡
d
1, in (9), we have s
=
1 and (8) becomes
(12)
q
~
(
d
-
1
)
<
r
≤
q
~
(
d
-
1
)
+
d
-
1
d
.
Note that (12) has no integer solutions.Lemma 3.
Letr be a positive integer such that
(13)
d
≤
r
≤
d
-
1
d
n
.
Then there exists a unique positive integer b
(
r
)
∈
{
1
,
…
,
n
-
r
-
1
} that satisfies
(14)
d
-
1
d
(
n
-
b
(
r
)
)
<
r
≤
d
-
1
d
(
n
-
b
(
r
)
+
1
)
.Proof.
By construction of partition𝒫, as in (7), there exists a unique b
(
r
)
∈
{
1
,
…
,
n
} such that (14) holds.
We now show thatb
(
r
) cannot exceed n
-
r
-
1.
Firstly, we suppose thatb
(
r
)
>
n
-
r. Then, we write b
(
r
) in the form b
(
r
)
=
n
-
r
+
ζ, with ζ integer such that 1
≤
ζ
≤
r. Since r satisfies (14), we have
(15)
d
-
1
d
(
r
-
ζ
)
<
r
≤
d
-
1
d
(
r
-
ζ
+
1
)
;
that is,
(16)
ζ
(
1
-
d
)
<
r
≤
(
d
-
1
)
(
1
-
ζ
)
.
Since ζ
(
1
-
d
)
<
0 and (
d
-
1
)
(
1
-
ζ
)
≤
0, there is no positive integer r that satisfies (16).
Secondly, ifb
(
r
)
=
n
-
r, (14) becomes
(17)
d
-
1
d
r
<
r
≤
d
-
1
d
(
r
+
1
)
;
that is,
(18)
0
<
r
≤
d
-
1
,
contradicting the hypothesis (13).Using the previous lemma, we find a useful and appreciable upper bound forγ
(
n
,
d
,
r
). This is one of our important steps to establish, under suitable hypotheses for n,d, and r, an exact value for γ
(
n
,
d
,
r
).Proposition 4.
Letr be a positive integer that satisfies
(19)
d
≤
r
≤
d
-
1
d
n
;
then
(20)
γ
(
n
,
d
,
r
)
≤
∑
j
=
0
min
⁡
⁡
{
b
(
r
)
,
d
-
1
}
‍
(
b
(
r
)
j
)
(
r
d
-
j
)
.Proof.
Since1
≤
b
(
r
)
≤
n
-
r
-
1, we construct a weight function f
∈
W
n, with f
+
=
r, such that
(21)
ϕ
(
f
,
d
)
=
∑
j
=
0
min
⁡
{
b
(
r
)
,
d
-
1
}
‍
(
b
(
r
)
j
)
(
r
d
-
j
)
.
This is sufficient to prove the (20).
Leth
=
min
⁡
{
b
(
r
)
,
d
-
1
}. Let α be a positive real number. In order to simplify the notation, we call β the number (
(
r
+
b
(
r
)
(
-
α
)
)
/
(
n
-
r
-
b
(
r
)
)
), in such a way that
(22)
r
+
b
(
r
)
(
-
α
)
+
(
n
-
r
-
b
(
r
)
)
(
-
β
)
=
0
holds.
At this point we define the function(23)
f
α
:
1
⋯
r
r
+
1
⋯
r
+
b
(
r
)
r
+
(
b
(
r
)
+
1
)
⋯
r
+
(
n
-
r
)
↓
⋯
↓
↓
⋯
↓
↓
⋯
↓
1
⋯
1
-
α
⋯
-
α
-
β
⋯
-
β
.
We now show that, forα sufficiently small, that is,(24)
0
<
α
<
min
⁡
{
r
b
(
r
)
,
d
h
-
1
,
d
b
(
r
)
(
r
-
d
-
1
d
(
n
-
b
(
r
)
)
)
}
,
f
α is a weight function that satisfies (21).
In fact,
(a)  the denominator ofβ, due to Lemma 3, is a positive number. Furthermore the numerator of β is a positive number if and only if α
<
(
r
/
b
(
r
)
). Therefore (24) and the definition of β assure that f
α is a weight function.
(b)  Havingα
<
d
/
h
-
1 is equivalent to require
(25)
1
+
⋯
+
1
︸
d
-
h
times
+
(
-
α
)
+
⋯
+
(
-
α
)
︸
h
times
>
0
.
This condition assures that the subsets of the type(26)
[
1
,
…
,
r
]
d
+
[
r
+
1
,
…
,
r
+
b
(
r
)
]
0
-
,
in
total
(
b
(
r
)
0
)
(
r
d
)
[
1
,
…
,
r
]
d
-
1
+
[
r
+
1
,
…
,
r
+
b
(
r
)
]
1
-
,
in
total
(
b
(
r
)
1
)
(
r
d
-
1
)
⋮
⋮
⋮
⋮
[
1
,
…
,
r
]
d
-
h
+
[
r
+
1
,
…
,
r
+
b
(
r
)
]
h
-
,
in
total
(
b
(
r
)
h
)
(
r
d
-
h
)are (
d
+
,
n
)-subsets of f
α.
(c)  Firstly we note that the requirement(27)
α
<
d
b
(
r
)
(
r
-
d
-
1
d
(
n
-
b
(
r
)
)
)
is equivalent to require
(28)
d
-
1
d
(
n
-
b
(
r
)
)
+
α
b
(
r
)
d
<
r
.
Lemma 3 assures the existence of a such α. Note that (28) is equivalent to
(29)
1
+
⋯
+
1
︸
d
-
1
times
+
(
-
β
)
<
0
,
which assures that the (
d
+
,
n
)-strings of f
α are only of the type (26). Therefore we have constructed a weight function f
=
f
α with r being nonnegative elements which satisfies (21).We now concentrate our attention on the subinterval(
(
(
d
-
1
)
/
d
)
(
n
-
1
)
,
(
(
d
-
1
)
/
d
)
n
]. By Proposition 2 there is a unique value of r contained in this subinterval. For this value formula (20) becomes simpler as expressed in the following result.Corollary 5.
Letr be a positive integer such that r
≥
d and (
(
d
-
1
)
/
d
)
(
n
-
1
)
<
r
≤
(
(
d
-
1
)
/
d
)
n. Then
(30)
γ
(
n
,
d
,
r
)
≤
(
r
d
)
+
(
r
d
-
1
)
.Proof.
The result follows directly from Proposition4 since b
(
r
)
=
1.The aim of the next proposition is to try to individuate a lower bound forγ
(
n
,
d
,
r
) starting from ϕ
(
f
,
d
). Recalling that γ
(
n
,
d
,
r
)
=
min
⁡
{
ϕ
(
f
,
d
)
:
f
∈
W
n
,
f
+
=
r
}, we have the following result.Proposition 6.
Let r be a positive integer such thatd
≤
r
≤
(
(
d
-
1
)
/
d
)
n. Let f
∈
W
n, with f
+
=
r, as in (3). If
(31)
x
1
+
y
n
-
r
≥
0
,
then
(32)
ϕ
(
f
,
d
)
≥
(
r
-
1
d
-
2
)
(
n
-
r
)
+
(
r
d
)
≥
(
r
d
)
+
(
r
d
-
1
)
.Proof.
We can consider thed-strings of {
1
,
…
,
n
} of type
(33)
1
i
1
⋯
i
d
-
2
∣
(
n
-
r
)
,
where i
1
⋯
i
d
-
2 are chosen in {
2
,
…
,
r
}.
By virtue of (31), each string of the type (33) is a (
d
+
,
n
)-string of f.
On the other hand, sincey
1
≥
y
2
≥
⋯
≥
y
n
-
r, each string of type
(34)
1
i
1
⋯
i
d
-
2
∣
k
,
where i
1
⋯
i
d
-
2 are chosen in {
2
,
…
,
r
} and k in {
1
,
…
,
n
-
r
}, will be a (
d
+
,
n
)-string of f.
The distinct strings of the type (34) are exactly (
r
-
1
d
-
2
)
(
n
-
r
). There are moreover all the (
d
+
,
n
)-strings of f that are the d-strings on {
1
,
…
,
r
}. This proves the first inequality in (32). Moreover, since r
≤
(
(
d
-
1
)
/
d
)
n, we also have n
-
r
≥
(
r
/
(
d
-
1
)
). Therefore
(35)
(
r
-
1
d
-
2
)
(
n
-
r
)
≥
(
r
-
1
d
-
2
)
r
d
-
1
=
(
r
d
-
1
)
.
Thus the second inequality also holds.Proposition6 leads us to state the following conjecture.Remark 7.
We conjecture that(36)
γ
(
n
,
d
,
r
)
=
(
r
d
)
+
(
r
d
-
1
)
,
where r
≥
d and (
(
d
-
1
)
/
d
)
(
n
-
1
)
<
r
≤
(
(
d
-
1
)
/
d
)
n.
Note that, in order to prove (36), by Corollary 5, it is sufficient to show
(37)
γ
(
n
,
d
,
r
)
≥
(
r
d
)
+
(
r
d
-
1
)
.
In the particular casen
=
2
d
+
2 and r
=
2
d
-
1 the previous conjecture has been proved in [3].In the next result we show that our conjecture (36) is true when n
=
d
+
2 and r
=
d.Proposition 8.
Ifn
=
d
+
2 and r
=
d, then
(38)
γ
(
n
,
d
,
r
)
=
(
r
d
)
+
(
r
d
-
1
)
.Proof.
We observe that ifn
=
d
+
2 and r
=
d, then (
(
d
-
1
)
/
d
)
(
n
-
1
)
<
r
≤
(
(
d
-
1
)
/
d
)
n. Hence, by Corollary 5,
(39)
γ
(
n
,
d
,
r
)
≤
(
r
d
)
+
(
r
d
-
1
)
.
Therefore, in order to have the thesis, we must prove that(40)
γ
(
n
,
d
,
r
)
≥
(
r
d
)
+
(
r
d
-
1
)
.
Let us note that as a direct consequence of Corollary 5 and Proposition 6 it follows that if r is a positive integer with r
≥
d such that (
(
d
-
1
)
/
d
)
(
n
-
1
)
<
r
≤
(
(
d
-
1
)
/
d
)
n, then
(41)
min
⁡
⁡
{
ϕ
(
f
,
d
)
:
f
∈
W
n
,
f
+
=
r
,
x
1
+
y
n
-
r
≥
0
}
=
(
r
d
)
+
(
r
d
-
1
)
.
Therefore by (41) inequality (40) is equivalent to the following:
(42)
min
⁡
{
ϕ
(
f
,
d
)
:
f
∈
W
n
,
f
+
=
r
,
x
k
+
y
n
-
r
<
0
,
h
h
h
h
h
h
h
h
h
h
h
for
every
k
=
1
,
…
,
r
}
≥
(
r
d
)
+
(
r
d
-
1
)
.
So, to prove inequality (40), it is sufficient to prove that, for each f
∈
W
n such that f
+
=
r and x
1
+
y
n
-
r
=
x
1
+
y
2
<
0, we have ϕ
(
f
,
d
)
≥
(
r
d
)
+
(
r
d
-
1
). We setp
=
(
r
d
-
1
)and let A
1
,
…
,
A
p be all the (
d
-
1
)-strings in [
r
]. At this point we consider the following configurations:
(43)
A
1
∣
1
i
1
∣
2
⋮
⋮
A
p
∣
1
i
p
∣
2
,
where {
i
j
}
=
[
r
]
∖
A
j
(
j
=
1
,
…
,
p
). Since f is a weight function and x
i
j
+
y
2
<
0 for j
=
1
,
…
,
p, it follows that all the d-strings A
1
∣
1
,
…
,
A
p
∣
1 are nonnegative d-tuple of the form (
d
-
1,1
) associated with f. Therefore ϕ
(
f
,
d
)
≥
(
r
d
)
+
p
=
(
r
d
)
+
(
r
d
-
1
). This proves (42), and hence also (40) is proved.In Table1 we list all the known values of γ
(
n
,
d
,
r
) in the range (
(
d
-
1
)
/
d
)
(
n
-
1
)
<
r
≤
(
(
d
-
1
)
/
d
)
n. Let us note that when the integer d is fixed and n runs in {
d
+
1
,
d
+
2
,
…
}, by Proposition 2, we find at most an integer value r such that (
(
d
-
1
)
/
d
)
(
n
-
1
)
<
r
≤
(
(
d
-
1
)
/
d
)
n.Table 1
n
r
n
-
r
d
+
1
∄
∄
d
+
2
d
2
Proposition8
⋮
⋮
⋮
d
+
(
d
-
1
)
2
d
-
3
2
2
d
2
d
-
2
2
Proposition 2.5 in [3]
2
d
+
1
∄
∄
2
d
+
2
2
d
-
1
3
Proposition 2.4 in [3]
⋮
⋮
⋮
k
d
+
1
∄
∄
⋮
⋮
⋮
k
d
+
t
k
(
d
-
1
)
+
(
t
-
1
)
k
+
1
⋮
⋮
⋮
(
k
+
1
)
d
(
k
+
1
)
(
d
-
1
)
(
k
+
1
)
Proposition 2.5 in [3]
⋮
⋮
⋮In Table1, k
=
1,2
,
… and t
∈
{
1
,
…
,
d
}. Moreover, if t
=
1, then there does not exist an integer r such that (
(
d
-
1
)
/
d
)
(
n
-
1
)
<
r
≤
(
(
d
-
1
)
/
d
)
n. In the last column we have marked the cases in which the conjecture (36) is proved. In particular, we note that, for every k, the case t
=
d corresponds to n
=
(
k
+
1
)
d, which implies r
=
(
k
+
1
)
(
d
-
1
)
=
(
(
d
-
1
)
/
d
)
n. For these values of r we know that (36) holds (see [3]) and the conjecture (36) is true.We give now a simple combinatorial interpretation of the inequalities(44)
d
-
1
d
(
n
-
1
)
<
r
≤
d
-
1
d
n
.For this purpose let us note that the last inequalities are equivalent to the following:(45)
(
n
-
r
-
1
)
(
d
-
1
)
<
r
≤
(
n
-
r
)
(
d
-
1
)
.Let nowr be a positive integer that satisfies (45) and f
∈
W
n, with f
+
=
r, as in (3). Let us consider the following representation:
(46)
⌞
⌟
+
⌞
⌟
+
⋯
+
⌞
⌟
+
k
1
⌞
⌟
+
⌞
⌟
+
⋯
+
⌞
⌟
+
k
2
⋮
⌞
⌟
+
⌞
⌟
+
⋯
+
⌞
⌟
+
k
n
-
r
-
1
⌞
⌟
+
⌞
⌟
+
⋯
+
⌞
⌟
+
k
n
-
r
,
where every ⌞
⌟ can be seen as a “box” initially empty and every row contains d
-
1 boxes. Each of such boxes can be occupied by at most one nonnegative element of f. Thus (45) is equivalent to state that n
-
r
-
1 rows in (46) must be completely occupied, whereas the last row must contain at least a nonempty box and, furthermore, the number of nonnegative elements of f cannot exceed the number of empty boxes in (46). This combinatorial interpretation of (45) suggests to examine firstly the (
d
+
,
n
)-strings of f of the form +
⋯
+
-, that is, a subset with d
-
1 nonnegative elements and only one negative.


## 4. Conclusions and Further Developments

In this paper we continue the research approach started in [1, 3] to the problem of determining new identities and new bounds concerning the numbers γ
(
n
,
d
,
r
). After a brief introduction to these numbers and their combinatorial context, we establish some preliminary results necessary to delimit the range of the integers parameters n, d, and r that we study. Next we give a relevant upper bound for numbers γ
(
n
,
d
,
r
) (Proposition 4). Afterwards we focus our attention on the range (
(
d
-
1
)
/
d
)
(
n
-
1
)
<
r
≤
(
(
d
-
1
)
/
d
)
n (Corollary 5). In this context, Proposition 6 and the study of ϕ
(
f
,
d
) bring us to conjecture a strong lower bound for γ
(
n
,
d
,
r
) on the subinterval (
(
d
-
1
)
/
d
)
(
n
-
1
)
<
r
≤
(
(
d
-
1
)
/
d
)
n. Finally, we prove our conjecture in the case n
=
d
+
2 and r
=
d, and this provides an exact value for γ
(
r
+
2
,
r
,
r
). We think that our approach of dividing the intervals of variation of the integers parameters n, d, and r in particular types of subintervals can be useful in order to determine further upper and lower bound for γ
(
n
,
d
,
r
). In future papers our purpose will be:(i)
to study other subintervals, trying to extend and generalize the validity of the results of this paper;
(ii)
to prove conjecture (36) in all the range (
(
d
-
1
)
/
d
)
(
n
-
1
)
<
r
≤
(
(
d
-
1
)
/
d
)
n.



---

*Source: 979171-2014-03-03.xml*