1. Introduction
Let x be a nonnegative integer. If the binary expansion of x is
then the Hamming weight of x is
.
In [1] Tu and Deng proposed the following conjecture.
Conjecture 1: Let
where
. Then the cardinality
.
Based on this conjecture, Tu and Deng [1] constructed two classes of Boolean functions with many good cryptographic properties. In this paper we always use the following bijection, where 
is the set of binary strings of length 
except the string consisting of n copies of 1.
We use 
to denote the length of a binary string
. Let
. And we use the following notation 
where there are k consecutive 1 and m consecutive 0 in the string.
In [1] Tu and Deng construct an algorithm which they used it to show that the conjecture above is true when
. Cusick, Li and Stanica [2] show that Conjecture 1 is true when
. In this paper, we will consider the following conjecture, which is equivalent to Conjecture 1.
Conjecture 2: Suppose that 
Let
then
.
The following lemma is easy so we omit the proof.
Lemma 1.1 Let 
Then following statements are true:
1) 
2)
;
3) The map 
is bijective.
Hence 
So the authors in [3] actually showed that Conjecture 2 is true when
.
According to Lemma 1.1. Deng and Yuan [4] show that Conjecture 2 is true if 
The outline of this paper is as follows. In Section 2 we introduce some notations. In Section 3, we consider what happen if we change some digit 1 into 0 in the strings. We get a recursive formula about 
and prove a new case of the conjecture.
2. A Partition of 
The following lemma is about the relation between 
and
, which is proved in [4].
Lemma 2.1 Let
Suppose that
where 
Assume that
. Then
where we set 
Let
for any 
and 
Then
and 
which are disjoin unions. We define a partition on 
according to Lemma 2.1.
Definition 2.1 Let 
be a binary string of length n. Suppose that
and 
where 
Let 
be a binary string. Suppose that
where 
We set 
to be the subset of 
such that 
if and only if the following two conditions hold i)
, if 
ii)
, if 
And we will use that notation 
if
.
Definition 2.2 Let 
and 
be two given binary strings. For any
, we set
, if 
for each
.
We say that 
is free if there are two strings 
and 
in 
such that 
and
.
From Definition 2.1 and Lemma 2.1 we see that
and
where k is the number of indices such that 
is free.
Example 2.1 Let
, 
, 
and
Then
and
,
,
.
So
, 
and
.
Moreover, by Definition 2.2 
if and only if
, 
or
. That is, 
is free for
. We also have 
if and only if
, 
if and only if
, 
or
.
3. Main Results
If 
with each
, then we say that the block of 
is
. Jean-P. Flori and H. Randriam [5] give some asymptotic results when each
. In particular, they show that Conjecture 2 is true if the block of t is smaller than 3 or each 
is sufficient large for a fixed length of block. We give a recursive formula to show that we can restrict our attention to the case each 
is smaller than the block of 
in this situation. They also conjectured that
if
.
Lemma 3.1 Let
and
with
and
.
Let
for
,
and
Then
Proof. Note that for any
, if
, then 
for each
, moreover in this case we have
.
Let
then
. Similarly we write
where
We observe that if
, then 
if and only if each 
Now if 
by comparing the number of free indices we have
.
Hence,
. If each
, then
.
Suppose that
. Then
So
Therefore
This finishes the proof.
Remark 3.1 Let 
with
. It is clear that
for any 
So we use the following notation 
means that there are sufficient consecutive 0 in the string.
We set
for
.
Theorem 3.1 Let
, 
,
, 
,
, 
where each 
and 
Then
.
Proof. Suppose that those strings have the same length and
. By Lemma 3.1
Let
.
If
, by comparing the number of free indices we have
where
. We set
and
.
Then
Let
and
.
Now consider the following mapping 
and
. If
and
then
.
Then
.
So
.
If
then
.
It is easy to see that
and
.
By the discussion above we obtain
, and
.
This finishes the proof.
Corollary 3.1 With the same notations in Theorem 3.1. Suppose that
then
.
Proof. We proof the statement by induction on
.
The case 
implies that
.
This was proved in [4]. Without loss of generality we can assume that 
and
. By induction
by Theorem 3.1
.
The proof is completed by induction on
.
Corollary 3.2 Let
. Then
.
Proof. By Corollary 3.1 it suffice to show that case when each
. So we have
, which is proved in [4].