Discrete Mathematics 75 (1989) 155-166
North-Holland

155

ON THE NUMBER OF PARTITIONSGIVEN SUBSUM (I)P. ERD&,t

J.L. NICOLASSOF n WITHOUT

A

and A. SARKGZYt*fA Magyar Tudomiinyos Akadimia, Matematikai Kutato inttfsete, Realtanoda u. 13-15, Pf
127, H-1364 Budapest, Hungary.
# Dt!partement de Mathtfmatiques, bat. 101, Universite’ Claude Bernard, Lyon 1, F-69622
Villeurbanne Cedex, France

1. Introduction
Let us denote by p(n) the number of unrestricted partitions of IZ, by r(n, m)
the number of partitions of it whose parts are at least m, and by R(n, a) thenumber of partitions of it:

if & =
whose subsums ni, + * * - + ni, are all different from a. Furthermore,{ai, . . . , ak}, we denote by r(n, a) the number of partitions of 12with no parts
belonging to &.
Let us consider now partitions of n for which each part is allowed to occur atmost once. In that case the above notations will be changed for q(n), p(n, m),

Q<n, a), dn, 4.
Clearly we have:r(12, m) = r(n, {1,2, . . . , m - 1))R(n, a) 3 r(n, a + 1)
R(n, a)2r(n,{1,2,.

. . , LuL21, a>)

(1)
(2)

where 1x/2] denotes the integral part of x.
In [4], the following estimation is given for R(n, a): when a is fixed, and ntends to infinity,(3)
where q(a) = ]a/2 + l], and u(a) E N. The value of u(a) is computed for1s a s 20, and it does not seem easy to get a simple formula for U(U). The results
are u(1) = 1, u(2) =4, u(3) =3, u(4) = 16, and u is increasing from a =3 to* Research partially supported by Hungarian National Foundation for Scientific Research, grant no.
1811, and by C.N.R.S, Greco Calcul Formel and PRC Math.-Info.
0012-365X/89/$3.50@ 1989, Elsevier Science Publishers B.V. (North-Holland)

P. Erdo”s et al.

1.56

a = 20. Moreover,

J. Dixmier

gives the following

inequalities:

for a even(lu/3]- l)! ua’6+3 G u(a) G 2”“a!/(u/2for a odd([u/3]- l)! u~‘~+’ =Gu(u) s 2”“u!/(It follows from (3), the definition

- l)!

(4)

[u/2])!

of 1+9,and the behaviour(5)of u, that for IZ large

enough,R(n,andforu=2b,1) > R(n, 2) > R(n, 3) > R(n, 4)(6)

2sbc9,

R(n, 2b + 2) < R(n, 2b) < R(n, 2b + 1) < R(n, 2b - 1).
At the end of the paper, a table of R(n, a) is given. It has been calculated
J. Dixmier, H. Epstein and O.E. Lanford, using the induction
formula.

byf(n, p, a) = 2 f(n - i, i, & u ti - i).
i-pHere, f(n, p, ~4) denotes the number of partitionsof II in parts <p such that nosubsum belongs to &, and ti - i = {a - i; a E a, a - i > O}. It has been independently
calculated
by F. Morain and J.P. Massias. They have used computer
algebra systems MAPLE and MACSYMA
to compute polynomials
mentioned
byDiximier (cf. [4], 4.3 and 4.10). Unfortunately
these polynomials
are of degree((a + l)(u + 2)/2) - 2, and it is not easy to deal with them for large values of a.
As observed in [4], R(n, 2) < R(n, 3) f or 10 <n G 106, which contradicts(6).
But (6) is true only for IZ large enough.
The aim of this paper is to study R(n, a) for a depending
on a, and smaller
than &,fi,where A0 is a small positive constant.
The tools for that are anestimation
for r(n, &) (cf. Lemma 2 below), and inequalities
involving R(n, a),extending(1) and (2). We shall prove

the following

result.

Theorem

1. There exists Ai > 0, such that uniformlyfor 1 s a c A,fi,

we have,when n goes to infinity,(9log(F)s (V(u)(ii)

log(!$.$)

2 l/+2) log%-log%)+ 0(1/G)‘/aa + o(a”,fi)

where ya = 4 if a is odd, and, if a is even,y,=f+log3-~log2+c10gu-=+0.79*~~+cU

log aU

where c is a fixed constant.

Partitionsof n without a given subsum

157

Let us observe that, when a goes to infinity, (4) or (5) gives(- l +:Op3+0(l))a

G log u(a) - +a log a S (log 2 - 4 + o(l))a(7)while (3), (i) and (ii) yield that
-Y& + o(a) =Slog u(a) - &z log a =So(u)(8)

which is better than (7) except for the lower bound when a is even.
We intend to treat the case A,,fi G a in an other paper, by a different method,which will give also an estimation for Q(n, a). For this quantity, we here give
only a lower bound.
Theorem

2. There exists A, > 0, such that, uniformly for 1 G a 6 A,fi,log(Qgq
P-~log~-log3+0

we have:!C( fi’ >We thank very much J. Dixmier for several interesting remarks.
2. PreliminaryResults

Let us first recall the definition of the mth Bessel1 polynomial y,(x);Y&) = 1y,(x)= (1+ m)Y,-I(X)(cf. [9]):(9)+ X’YA(X).

From that definition, it is easy to see that, if we set
F(x) = (exp (fi))/Vk
then we have (cf. [5], Lemma 1)
exp tiF’“)(x) = 2nzx’“+““Y~Furthermore,Lemma

(-_lc
$>

.

it follows from (9) that ~~(0) = 1.

1. For m odd, the function x+ym(x)is increasing for x E 1-00, +m[, andits zero a;, suttifies-y<a,,<-mYm+l(11)where y is a constant satisfying 1.5 < y < 1.51.
For m even, y,(x) is decreasing on 1-00, cwL[and increasing on ]a&, +m[, andY-m+0.77<a:,<-Y
m + 1.61.

Proof. This is proved in [l] and [2].

Cl(12)

1.58

Lemma

P. Erd&et al.

2. Let us define P,,, byli (m +i))Xk.

j=-k+lThen we haveY,(x)Y,(-x)
Proof.

= P,(x’).

It is known that y,&)satisfies the differential equation (cf. [9], p. 7)x2y” + 2(x + 1)y’ - m(m + 1)y = 0.
If we set w(x) = y,(-x),(13)

it satisfiesx2w” + 2(x - 1)w’ - m(m + 1)w = 0.
Now we set Y = yw. It is known that Y satisfies a linear differential equation,with some calculation this equation writes:x4Y”’ + 6x3Y” - ((4m(m + 1) - 6)x2 + 4)Y’ - 4m(m + 1)xY = 0.

(14)
and(15)

We can easily check that Y satisfies (15), by calculating Y” and Y”’ in terms ofyw, y’w, yw’, y’w’ by (13) and (14).
Wow, we are looking for polynomial solutions of (15). It turns out that thesesolutions are of the form cP,(x’), and considering x = 0 yields Lemma 2. Cl
We are very pleased to thank A. Salinier for this proof of Lemma 2. This result
is somewhat curious. We would expect that, in the product y,(x)y,(-x)
thecoefficient of x2k is a polynomial of degree 4k in m. Indeed, it follows from (9),cf. [9], p. 13, thaty,(x) = 1 + $J aim”?lckk=lwithaim) = &j

(16)._Q+, (m +i).
‘ILemma

3. For x such that 0 =Zm s l/a,y,(-x)

3 (1 - m(m2+ l)*,)exp(=exp C - ,(y+\Proof.

we have- m(m2+ “x)l) (x + 0(x2))).
L

From the obvious inequality (m - i + l)(m + i) s (m + l)m, (16) implies

Partitionsof n without a given subsum

159

which givesm(m + 1)2r >.

(y,(x) sexp

(17)

Now, let us write the polynomial P,, defined in Lemma 2, in the formP,(x)= 2d/J!

k=O

Then we havedcm+k + l)(m - kW + 1)

I I
k+l

=((2k +2)

dk2m2.

.

Thus, the absolute value of the general term of y,(x)y,,,(-x),
that is (dkx2kl isdecreasing, and, as it alternates in sign, for mx G l/fi,
we havel_m(m+l)2

x2 G y,(x)yJ-x) = P,(x’)

S 1,which, with (17) completes the proof of Lemma 3.

Cl

More accurate estimations have been obtained by M. Chellali, using Agarwal’s
integral representationy,,,(x) =$ $t”(1 + 4)ne-f dt

and the saddle point method (cf. [3]).
Proposition. There exists A2 > 0 such that, if .& = {a,, . . . , ak} satisfies s = a, ++ ak s A,,n, then, when n tends to infinity, we havea,,+-**(9r(n, drs)s(ii)r(n, 4Proof.

operator

I?“JPci=,
nk&J1+o(+l))( )2 (l!J .i)p(n)($=)*exp(o(s/fi)).

It is very similar to the proof of Theorem 1 of [5]. First we introduce theDC”‘. Let f: R + R, m 3 1, ul, . . . , u, be positive. We set
D (1)(4;fix) =f(x)-f(xP)(U1,. . . ) u,;f,x) = P-‘)(L&- 4). . . , u,_,;f,_ #m-l)(u,, . . . 3 u,-1;f,x)
x - &J.

From the generating functions, we observe. . . ak;pJ n>.
r(n, (4, . . . , ak}) = D(k)(a19)

w-9

160

P. Erd6s et al.

Now, with F(x) = (exp(G))/J&,
can be written (cf. [5]) as follows:

the classicalp(n) = &with C = srm,F’(C’(n- l/24))

resultof HardyandRamanujan+fi(n)(19)

andIfi(exp(q).

Sy

Furthermore,using Lemma

3 of [5], (18) and (19) giveF@+‘)(C’(E- l/24))+ 0(cexp(T))(20)

withfl-.YGECn.

(21)

We now use (10) to estimate

F (k+1)(C2(E - l/24)).

The functionx+

increasing
for x 2 (k + 2)2. As s = a, + . . . + uk > k(k + 1)/2 2 k2/2,
plies k s a,for A2 small enough, from (21) we haveexp( CVFFi)(n _ s _ l)V+W~ exp( CVFTZ)(E _ 1/24)W+W

exp(G).

X(k+2)/21swhichim-~ exp( CVi)n(k+2)/2’(22)Now let us turn to the proof of (i). By (22), the main term of (20), is at mostexp(Clh)For A2 small enough,and thus Lemma

we have

1 gives(-1Ykfl (-&rqjj>sGl.

(23)

Using the estimation

the main term of (20) is at most(24)Partitions

To complete
included

the proof

in the above

by Stirling’sof (i), it remains
error

formula.

term.

First,

So it is enoughto check(CVZ

In order>VZA,nto prove

yk+lS

exp @.
(termof (20) is

is an increasing

functionon k, forTo conclude,

we observethat forto show that>(ii), first we apply Lemma-1(> aexp

cV=that the error(24) isBut the left hand side of the above inequality
4
k c - fi,and we know that k s fis m.
C& small enough, we have:
4e161

of n without a given subsum

3, to obtain(k+l)(k+2)(1++)))( - 2c.\/ns-l

which with (23) yields(-1

Then we observe

thatYk+l cj/mexp(CVn-s-l))= O(slfi).

= exp(Cfi(25)+ O(s/fi))and(n - s - l)(k+2)‘2 = exp q((log n + O(sln)))= n(k+2)‘2 exp(O(s/fi))since k = O(G).
Furthermore,by (lo),(22) and (259, the main term of (20) is at least

The end of the proof of (ii) goes in the same way as for (i).

Remark. A similar0

propositionis given in [7] in the case of restricted partitions.
A more general estimation
is given by J. Herzog (cf. [lo] and [ll]),using aTauberiantheorem.

162

P. Erd6s et al.

3. The upper bound in Theorem

1First let us say that a partition n = n, + . . . + n, of n represents a if there is a
subsum nit,. . . ,ni,, lsir<*.
. < ij 6 t which is equal to a. Thus R(n, a) counts
the number of partitions of n which do not represent a.
Clearly if b <a, b and a - b cannot be together parts of a partition which
does not represent a.
Let us suppose first that a is odd. From the above remark, we deduce that for
all integers, i, with 1 G i s La/2j, at most one of i and a - i can be a part, andthus

Wh 4 c .,,.%,,,,r(n,(F {i”(a - i)‘-‘1))
where in the summation ci E (0, l}.
NOW we apply our proposition,
obtain thatW, 4with k = q(a),U {a})(26)and s s &2<j_j,

and we“_pW($==)v’a‘(1 + O(&))
E, ..5,0,2,
a Fl’i”‘(a - i)lPq.

But this summation is exactlya l-J (i + (a -i))

=av@)

i=l

which proves (i) for a odd. When a is even, the part a/2 can occur but only once.
Thus we haveR(n, a) C .,,JI_r(n,+ . ....z.P L?
,2, +(y{i”(a - i)“9)- f >U {a}){P(a - i)‘-‘l})(yU {a})(27)

where the first summation counts partitions without any part equal to a/2, andthe second counts partitions with one part equal to a/2.
For the second sum we obtain the upper boundP(n -.i4&)Vb)(1+ o(&))
exp( Cm)G [ 4jh(nna ‘@)(l + 0(1/I/$).
- a/2)*(a)n+1 I( G >But, as already observed, the function x--, expfilxk
is increasing for x 2 k2,and for A, small enough, the expression between brackets is smaller thanexp( CG)4tinly(a)/Z+l=p(n)n-v’(a)n(l+ 0(1/G)).

Partitionsof n without a given subsum

163

So, the second sum in (27) is not bigger than the first one, which was alreadyestimated when a is odd. This completes the proof of (i). 04. The lower bound in Theorem

1

Let us suppose first that a is odd. ThenR(n, a) 3 r(n, { 1, 3, 5, . . . , a})and, observing that r/~(u) = (a + 1)/2, by the Proposition

we haveR(n, a) 3

By Stirling’s formula, (2u)!/2”u! 2 u”2ueC‘, and since ~(a) 3 u/2, we obtain (ii).
Let us suppose now that a is even. In fact, the following reasoning works also
for a odd, but it gives a worse estimation than the preceding one. For real
numbers x and y, let us denote the set of integers belonging to the real interval
1x9Y [ by lx - . . y[. We set&=[l*** u/3] u [u/2 * * * 2u/3] u {a}.

Then, it is not difficult to see that
R(n, a) 2 r(n, d)(which is slightly bettter than (2)), and considering the three possible cases
a = 0, 2,4 mod 6, that card .& = ~(a). By the proposition, we getR(n, u) ~ u la/31 ! l@ - I)/31 ! p(n)Jd v(a)exp(O(a2/G)).
]u/2-l]!
( -6 >
Using Stirling’s formula in the form
[u + O(l)]! = u”eeu exp(O(log u))
we obtain (ii) with an effectively computable

5. Proof of Theorem

constant c.

02We consider now only partitions without any repetition,subset of [l . * . (a - l)], say d with the following property:
noelementje
foreachje

l*..ia a1 I,

jEJBandu-j$.$[3**.2and we look at a1

belongs to &there are 3 possibilities:

j$&andu-jE&,.*a-1

1,j$&andu-j$&there are 2 possibilities, j E .& or j 4 A

164

P. Erd6s et al.

For any such &, we have:
Card L&s c1a2.
How many such d’s are there? AsCard(]i.**i[)si--1

andCard([$...(a--l)])a$

there are more than3(a/6)-lpsuch sets &. Further, to build a partition of n, we choose such a set .&, and wecomplete by a partition of n-Card J&?,without any part smaller than a + 1. Thus,since p(n, m) is non-decreasing in n (cf. [8]),Q(n, a) 2 3n’6-*2a’3~(n - cla2, a + 1).
Using Theorem
estimation

1 of [8], which gives p(n, m) 2 q(n)/2”-‘,

1exp(xG),
4(n) - 74(3n3)z

Table of R(n,.a)and the classicalPartitions of n without a given subsum

165

Table of R(n, a) (continued).

whichimplies

we obtain Theorem 2.

ClReferences[l] M. Chellali and A. Salinier, Sur les zeros des polyn6mes de Bessel, CRAS, t. 305, SCrie 1 (1987)
765-767.
[2] M. Chellali, Sur les zeros des polynomes de Bessel II, CRAS, t. 307, Strie 1 (1988) 547-550.
[3] M. Chellali, Sur les zeros des polyn6mes de Bessel III, CRAS, t. 307, SCrie 1 (1988) 651-654.
[4] J. Dixmier, Sur les sous sommes dune partition, preprint de I’IHES (1987) and to appear inMemoires Sot. Math. France.
[S] J. Dixmier and J.L. Nicolas, Partitions without small parts, to be published in the Proceedings ofColloquium in Number Theory, Budapest (July 1987).

166[6] P. ErdGs

P. Erd& et al.

and M. Szalay, On some problemsof J. D&es and P. Turan,Studies in pure
Mathematics
to the memory of P. Turan, Editor P. ErdBs, Budapest(1983) 187-212[7] P. ErdGs and M. Szalay, On some problems of the statistical theory of partitions,
to be publishedin the Proceedingsof Colloquium
in Number Theory, Budapest(July 1987).
[8] P. Erd&, J.L. Nicolas and M. Szalay, Partitions
into parts which are unequal and large, to be
publishedin the Proceedingsof Journees
Arithmetiques,
Ulm, Germany(SpringerVerlag
Lecture Notes).
(91 E. Grosswald,
Bessel polynomials,Lecture
Notes in Mathematics
No. 698 (SpringerVerlag,1978).
[lo] J. Herzog, Gleichmlssige
asymptotische
Formeln fiir parameterabhangige
Partition
funktionen,
Thesis of Univ. J.F. Goethe, Frankfurt
am Main (1987).
[ll] J. Herzog, On partitions
into distinct parts sy, preprint.