Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  799.11044
Autor:  Erdös, Paul; Nicolas, J.-L.; Sárközy, A.
Title:  On the number of pairs of partitions of n without common subsums. (In English)
Source:  Colloq. Math. 63, No.1, 61-83 (1992).
Review:  Let \Pi = {n1+n2+...+nt = n; n1 \geq n2 \geq ... \geq nt > 0} be a generic partition of n where t = t(\Pi) and the ni's are integers. Each sum ni1+...+nij (i1 < ... < ij) is said to be a subsum of \Pi. Let p(n) denote the number of partitions of n.
Let R(n,a) be the number of partitions of n such that no subsum is equal to a. The asymptotic behaviour of R(n,a) has been investigated by several authors, cf. J. Dixmier [Mém. Soc. Math. Fr., Nouv. Sér. 35, 1-70 (1988; Zbl 684.10047); Port. Math. 46, 137-154 (1989; Zbl 684.10048); Bull. Sci. Math., II. Sér. 113, 125-149, 505 (1989; Zbl 684.10049); Bull. Soc. Math. Belg., Ser. A 42, 477-500 (1990; Zbl 734.11051)]; P. Erd\H os, J.-L. Nicolas and A. Sárközy [Discrete Math. 75, 155-166 (1989; Zbl 673.05007); in ``Analytic number theory'', Prog. Math. 85, 205-234 (1990; Zbl 727.11038)].
In the paper under review the authors solve a problem of J. Dénes from 1967 by obtaining an asymptotic expansion for the number G(n) of pairs of partitions of n which do not have nontrivial equal subsums:

G(n) = 2p(n) (1+\alpha1 n- ½+\alpha2 n-1+...+\alphak n-k/2+O(n-(k+1)/2)).

As to the q(n) unequal partitions of n, the authors prove the following asymptotic estimate for the number H(n) of pairs of unequal partitions of n without nontrivial equal subsums:

H(n) = cq(n) (1+O(n- ½ log2 n)),    where   13.83 \leq c \leq 14.29.

Reviewer:  M.Szalay (Budapest)
Classif.:  * 11P82 Analytic theory of partitions
                   05A17 Partitions of integres (combinatorics)
Keywords:  pairs of partitions without equal subsums; number of partitions; asymptotic expansion
Citations:  Zbl 684.10047; Zbl 684.10048; Zbl 684.10049; Zbl 734.11051; Zbl 673.05007; Zbl 727.11038

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page