On the Multiplicity of Parts in a Random Composition of a Large Integer.
In this paper we study the following question posed by H. S. Wilf: what is, asymptotically as $n\rightarrow \infty$, the probability that a randomly chosen part size in a random composition  of an integer n has multiplicity m? More specifically, given positive integers n and m, suppose that a composition $\lambda$ of n is selected uniformly at random and then, out of the set of part sizes in $\lambda$, a part size j is chosen  uniformly at random. Let $\P(A_n^{(m)})$ be the probability that j has multiplicity m. We show that for fixed m, $\P(A_n^{(m)}$) goes to 0 at the rate $1/\ln n$. A more careful analysis uncovers an unexpected result: $(\ln n)\P(A_n^{(m)})$ does not have a limit but instead oscillates around the value $1/m$ as $n\to\infty$.This work is a counterpart of a recent paper of Corteel, Pittel, Savage, and Wilf, who studied the same problem in the case of partitions rather than compositions.
Introduction
In this paper we consider the multiplicity of a randomly chosen part size in a random
composition of an integer n. Let us recall that a multiset
is a partition of an integer n if the - j are positive integers, called parts, such
that
Compositions are merely partitions in which the order of parts
is significant. Thus, for example, the integer 3 admits three partitions, f1;
f2; 1g and f3g, and four compositions, namely (1; 1; 1), (1; 2), (2; 1) and (3).
Part of the research of the first author was carried out while he was visiting Department
of Mathematics of Lehigh University in the spring semester of 1999. He would like to thank
the Department for its hospitality
y Research supported in part by National Science Foundation Grant DMS9622772
Integer partitions (as deterministic objects) have been studied for quite some
time, but Erd-os and Lehner [5] were apparently the first to study integer partitions
from the probabilistic perspective, namely, they considered the set of all
partitions, P (n), of an integer n, as a probability space equipped with the uniform
probability measure. Quantities of interest are treated as random variables
and one can study their probabilistic properties, most typically, the limiting
properties as n ! 1. Erd-os and Lehner, for example, considered the limiting
distribution of the total number of parts in a partition. Their paper opened a
new line of investigation.
Goh and Schmutz [10] obtained the central limit theorem for the number of
different part sizes in a random partition, that is, they proved that the number of
different part sizes, appropriately normalized, has, approximately, the standard
Gaussian distribution. (Several years earlier Wilf [17] found an asymptotic formula
for the expected number of distinct part sizes.) This approach culminated
in an important paper by Fristedt [9], who proved that the joint distribution of
the multiplicities of part sizes is that of independent geometric random variables
conditioned on the event f
ng.
Fristedt's work, in turn, opened new possibilities and resulted in further
progress in our understanding of the structure of random partitions. A good
example is a paper of Pittel [16] substantiating two well-known conjectures
concerning integer partitions. Utilizing Fristedt's result, quite recently Cor-
teel, Pittel, Savage and Wilf [3] provided an answer to the following question.
Consider the following two-step sampling procedure: first choose uniformly at
random a partition - of n. Then, out of all different part sizes in - pick one
uniformly at random. What is the asymptotic unconditional probability that
this part size has a certain specified multiplicity, say, m? For example, partition
1g of the number 10 has three different part sizes 1, 2, and 3
and only one of them has multiplicity three, namely 1. Thus, for this particular
partition, the probability of choosing a part that has multiplicity three is 1=3.
In order to find the unconditional probability of randomly choosing a part of
multiplicity three in a randomly chosen partition of 10, one would have to average
similar probabilities over all partitions of 10. Corteel, Pittel, Savage and
showed that in general the probability in question approaches 1=(m(m+1))
(in particular, the probability that the randomly chosen part size in a random
partition is unrepeated approaches 1=2 as n !1.)
then asked the same question for random compositions: what is the
asymptotic value of the probability that a randomly chosen part size in a random
composition of an integer n has multiplicity m ? Our aim here is to provide
an answer as complete as we can. On the "first level" of precision the answer
is simple: for every fixed m this probability approaches zero. One would then
like to know the rate of this convergence. We will show that the rate is 1= ln n.
Specifically, if A (m)
n is the event that a randomly chosen part size in a random
composition of n has multiplicity m then there exist constants c 1 (m) - c 2 (m)
such that c 1 (m) - (ln
2.
The next natural step is to find possibly tight bounds on c 1 (m) and c 2 (m),
or to show that the limit (ln
exists as n ! 1. This is the place
where things become a bit tricky. In order to describe the difficulties let us
briefly discuss the argument. Letting U (m)
n and Dn denote the number of parts
of multiplicity m and the number of distinct part sizes, respectively, we have
In the case of partitions, Corteel, Pittel, Savage and
used Fristedt's result to argue that Dn is heavily concentrated around its
expectation, and therefore,
n ) is asymptotic to the ratio of expectations
EU
n =EDn and one needs to find asymptotic values of these two expectations.
In the case of compositions much of the story is the same, with one crucial
exception, the expected value of U (m)
n does not have a limit, but exhibits oscillations
around 1=(m ln 2). (This phenomenon is not new and was observed in
the context of head runs in coin tossings, see e.g. [2], [11] or [12].) Since, as we
will show, the behavior of (ln
goverened by the behavior of EU
it will follow that (ln n)P(A (m)
around the value 1=m as n !1.
The rest of the paper is organized as follows: in the next section we will
introduce notation and state our result precisely. In Section 3 we will describe
the probabilistic set-up. In Section 4 we estimate the number of distinct part
sizes and show that Dn is heavily concentrated about its expectation. In Section
5, we give an estimate for the expected number of parts of given multiplicity.
In Section 6, we compute bounds on the oscillation.
Notation and Statement of the Result
A composition - of an integer n is an ordered tuple (fl
are positive integers such that
n. The numbers are called
parts, k is the total number of parts, and the elements of the set ffl
are the part sizes of -. For example, (2; 1; 2; 3; 1; 1) is a composition of the
number 10 into six parts with part sizes 1, 2, and 3, where part size 1 has
multiplicity 3, 2 has multiplicity 2, and 3 has multiplicity 1. We denote the set
of all compositions of n by C(n) and note that . For a composition
denote the number of distinct part sizes and, for
fixed integer m, U (m)
n (-) will denote the number of part sizes of - that have
multiplicity m. More formally,
where I A , the indicator of event A, is 1 if A takes place and 0, otherwise.
Similarly,
U (m)
I
where
We equip C(n) with the uniform probability measure P, (i.e.
2 \Gamman+1 for every - 2 C(n)) and we will denote the expectation with respect to
that measure by E . Throughout the paper the letter c is reserved for an absolute
constant whose value is of no relevance and may change from line to line.
We consider the following experiment. First a composition is chosen at
random. Then, out of all distinct part sizes one is selected uniformly at random.
We would like to know what is the unconditional probability that this part
size has multiplicity m. We will denote this event by A (m)
n . Since for a given
composition - the probability that a randomly chosen part size has multiplicity
m is given by the ratio
U (m)
the unconditional probability that a randomly chosen part size in a random
composition has this multiplicity is just the expected value of that ratio. That
is,
U (m)
Dn
Thus, our goal is to approximate this expectation. Our result is as follows.
Theorem 1 Under the above notation we have the following: for a fixed integer
(ln
i.e. there exist two positive constants c 1 (m) and c 2 (m) such that for all n - 2,
More precisely, as n !1,
(ln
where H (m) is a mean - zero function of period 1 whose Fourier coefficients are
given by
Much of our proof relies on an appropriate interpretation of a composition,
found, e.g., in Andrews [1]. This interpretation allows us to connect the study
of random compositions to another much investigated topic, namely the study
of runs of successes in independent Bernoulli trials (see for example Erd-os and
R'enyi [6] or Erd-os and R'ev'esz [7].) In order to describe this connection we
interpret compositions as follows: consider a composition
into parts is a composition of the
0,1-sequence of length 10:
Composition of
index of sequence:

Figure

1: Correspondence between compositions of n and 0,1-sequences of length
which end with 1.
number Such a composition is associated with a
1g-valued sequence
and otherwise x (Note that this forces xn = 1.) For example, the
composition (2; 1; 2; 3; 1; 1) is associated with the sequence (0;
as illustrated in Figure 1. Clearly there is a one-to-one correspondence between
compositions of n and f0; 1g-sequences
To say that a composition is chosen at random is to say that the 0's and 1's
occur with probability 1=2 at each of the first n\Gamma1 positions, and the occurrences
at different positions are independent of each other. In other words, the number
of 1's in the first positions is a binomial random variable,
with parameters 1=2. With this interpretation the total number of
parts is just the number of 1's (including the one in the nth position) and thus
it is equidistributed with 1 contrasts with the case of
"unordered" partitions where the exact distribution of the number of parts is
unknown and it took a considerable effort to find a limiting distribution of the
total number of parts, see Erd-os and Lehner [5].) Furthermore, the numbers
can be viewed as "waiting times" for the first,
appearance of 1 in the associated f0; 1g-sequence our example, 1
appears in the second, third, fifth, eighth ninth and, of course, tenth positions.)
It is well-known and easy to check that in an infinite sequence of independent
Bernoulli trials with the probability of success p, waiting times for successes are
independent and identically distributed (i.i.d.) random variables whose common
distribution is that of a geometric random variable with parameter p. Since we
are considering only this is no longer true. But we have the following
fact.
Proposition random variables with parameter
(that is,
Then we have the following: If the set C(n) of all compositions of an integer
n is equipped with the uniform probability measure then the distribution of a
randomly chosen composition is given by
4 The Number of Distinct Parts
In this section we will study certain aspects of the behavior of Dn . For the
purpose of approximating
work with the ratio U (m)
will be clear from our argument, for example, that
EDn
log
We will proceed in the following fashion: we will establish the existence of two
sequences of natural numbers (' n which increase to infinity and are
asymptotically the same, i.e.
lim
kn
and such that both probabilities
tend to zero as n ! 1 at a rate faster than 1= log 2 n. This will allow us to
replace the Dn in the denominator by either of the sequences (' n
then in the next section, we will approximate the expected value of U (m)
n . We
begin with establishing the existence of (' n ). For a composition
let Sn (-) denote the number of consecutive part sizes (starting with size 1) in
-. That is,
Consider for a moment an arbitrary integer ' n . Since Sn (- Dn (-) we have
where we purposely ignored the last part
In
order to bound the last probability we first notice that, since - is equidistributed
with the random varialble 1 we have
Moreover, - is well concentrated around its mean. Namely, for every t ? 0 we
have
In particular, letting t
(The value of ff plays a minimal role in the argument, so we will set it to be
1 for the rest of this section; we just want to mention that by increasing this
value as necessary we can get arbitrary polynomial rate of convergence to zero
of this probability. This will be useful in the next section.) Let q \Gamma
Then we can bound (1) by
From (2), the first probability in the right-hand side (rhs) of (3) goes to 0 at a
polynomial rate, so we concentrate on the second. Since
that
we bound the second term in the rhs of (3) by
'n
'n
'n
P(
'n
'n
'n
'n
as long as
1. Furthermore, the upper bound will go to 0 as
1. For that it is enough to let ' n - log 2 (q \Gamma
1. For our purpose, the choice OE(q \Gamma
be convenient. With this choice, we conclude that
Using the fact that 0 - U (m)
we infer that
U (m)
Dn
U (m)
Dn
I
U (m)
Dn
I Dn?'n - P(Dn - '
As we will see in the next section, EU
so that the second term in
the last sum is dominating.
As for the lower bound consider a sequence (k n ) which will be specified later.
We then have
U (m)
Dn
U (m)
Dn I Dn-kn - 1
kn EU (m)
kn
I Dn?kn
We will choose (k n ) so that the term EU
I Dn?kn will be of lower order than
EU
n . Since the latter term will be shown to be bounded away from zero, this
means that it suffices to choose (k n ) so that
Since the number of distinct part sizes is no larger than the largest part size,
letting
respectively,
we have
U (m)
(The second inequality is valid since the size of the last part is no more than
It follows that
and thus
To find a choice of (k n ) that would make this latter expectation go to 0 we write
t=kn
t=kn
t=kn
Choosing kn - log 2 (n/(n)) we get
which goes to 0 for
Thus one can set kn -
log 2 (n log 2
n). With these choices of (' n ) and (k n ) we obtain that
U (m)
Dn
U (m)
Dn
I
U (m)
Dn
I f'n-Dn-kng c
U (m)
log 2 n \Sigma o(log n)
U (m)
Dn
I
U (m)
Dn
I
By the choice of (' n ) and (k n ) the last two expectations are bounded above by

and we see that
(ln
log
provided that EU (m)
Thus, the asymptotic behavior of (ln
is determined completely by the behavior of EU (m)
, and to complete the proof
we need to estimate EU
n .
5 Parts of Multiplicity m
In this section we will approximate EU
. Let U denote the set
of part sizes in - that have multiplicity m, and let us write j 2 U (m) to indicate
that size "j" has multiplicity m. We have
I j2U
Therefore, we need to estimate the sum of P(j 2 U (m) ). The degree of difficulty
of this approximation increases with the accuracy that one desires to
achieve. Furthermore, since, as we will see, EU
n is an oscillatory function,
explicit bounds on EU
n , no matter how tight, cannot be used to show that
(ln
converges. Thus, one may consider devoting too much attention
to an accurate approximation to be a questionable investment. We will present
the detailed argument for the fairly precise bound on EU
n but the reader
interested in just the fact that this expectation is \Theta(1) (which is all that is
needed to establish (4)) will notice that the argument may be simplified. To
make this point more transparent let ~
denote the parts of
a composition -, i.e.
~
It is much more convenient to work with \Gamma's rather than with ~
\Gamma's, because the
last part, complicates the dependence structure. As a result a nonnegligible
part of an argument is to show that "tildas" can be neglected. This is, of course,
not an issue if one is interested merely in a \Theta(1) result; tildas may be dropped,
since the single part ~ \Gamma - can be ignored without affecting U (m)
n by more than 1.
To estimate P(j 2 U (m) ) write:
I ~
We begin by estimating the first probability in (5), and then we will show that
the sums over j of last two probabilities are negligible. Let q \Sigma
As in the previous section, let t
now choose
so that from (2) we get To get an upper bound on
the first term in (5) write
P(
The second probability in the rhs of (6) is O(1=n 4 ) and for the first one we have:
P(
m"
Similarly, to get a lower bound for the first term of (5) we have
P(
It remains to bound the sum over j of the terms
P(f ~
and
in (5) and to show that they are negligible compared to the sum over j of the
first term in (5). Since
for the probability in (7) we have
P(f ~
by the definition of q
. Thus, summing up over j we get:
c
r
For the second probability (8) the argument is essentially the same:
P(f ~
and in the same fashion as before we see that the sum over j of these terms does
not exceed \Theta(
(ln n)=n).
We now observe that for the sum
is easily seen to be \Theta(1) (it suffices to compare it to the integral
Therefore, since q
are asymptotically the same, and m
is fixed, and
j?n
j?n
we conclude that
A more detailed analysis reveals a quite interesting and unexpected phenomenon.
The right-hand side in (9) does not have a limit, but exhibits oscillations about
1=(m ln 2). To see this, one approach is as follows (for convenience we will replace
by q in (9)- this does not affect asymptotics): expanding
using the binomial formula, and summing over j, givesX
Alternating sums of this type appear surprisingly often in the analysis of certain
algorithms, and can be approximated using methods of complex analysis. Since
the standard method, attributed to Rice, has been described recently in several
papers, we will not reproduce the details here. Rather, we refer to [15, Section
5.2.2], [8], [13] or [14] for some examples of applications and illustration of the
method. In particular, these last two papers explicitly treat the asymptotics of
the sum q
We would like to indicate an alternative approach to approximating shown
to the first author by Bennett Eisenberg and Gilbert Stengle [4]. Although it
seems less general than the Rice method, in the case of our sum it gives a more
elementary and direct proof of the asymptotics. Consider a sequence (q s ) such
that for some 1 -
replacing q s by 2 x+s and j by s
where the "legality" of passing to the limits is easily checked (see [4]). The
latter expression defines a 1-periodic function and its Fourier coefficients are
easily found:
Z 11
e \Gamma2-i'x dx
e \Gamma2-i'x dx;
which, upon substitution
Note that OE so if we let
then H (m) satisfies the conditions of Theorem 1. Combining this with equation
(4) completes the proof of the theorem.
6 Bounding the Oscillation
The sum below, is used in Section 5 of the paper to approximate EU (m)

Figure

2: Comparison of EU
(1)
n (dotted), the approximating sum (10) and
1=(ln
b(n=2)c. The data displayed in Figures 2, 3 and 4 indicate that
1=(m ln 2) is a reasonble approximation to the actual value EU
and that the sum (10) is a good approximation to EU
n , as n gets large.
As noted in the previous section, the sum (10) oscillates about 1=(m ln 2).
We would like to note that the oscillation is not an artifact of our approxima-
tion. The data shows that the actual value of EU
does itself oscillate about
1=(m ln 2). This is illustrated in Figures 5, 6, and 7 for
These plots use successively coarser scales and show how the amplitude of the
oscillation of EU
about 1=(m ln n) increases as m increases.
In order to bound the amplitude of the oscillation, note that the coefficients
of Fourier expansion of the function H (which is asymptotic to EU (m)
1=(m
and therefore,
lim sup
Using the properties of gamma function,
t sinh(-t) and \Gamma(z

Figure

3: Comparison of EU (5)
n (dotted), the approximating sum (10) and
1=(5

Figure

4: Comparison of EU (10)
n (dotted), the approximating sum (10) and

Figure

5: The oscillation of EU (1)
about 1=(ln 2).0.260.280.3

Figure

The oscillation of EU (5)
about 1=(5 ln 2).

Figure

7: The oscillation of EU
about 1=(10 ln 2).
and letting we get a bound on the oscillation:m!
ae' sinh(-ae')
pm!
For small m this bound is very good, but as illustrated in Table 1, as m
increases it becomes increasingly weaker. In fact, for m exceeding the value 52
it becomes useless as the thus obtained bound on the amplitude exceeds the
mean value, 1=(m ln 2). (Thus, from this bound on the oscillation, one could
not even conclude that the quantity (10) is positive.) A more detailed analysis
of the nature of these fluctuations is perhaps an interesting question but we do
not pursue it much further in this paper. One thing worth pointing out is that
oscillations of EU
are highly nonsymmetric around 1=(m ln 2). On one hand,
considering q of the form m2 p and replacing the sum over j by its largest term
(corresponding to we find that
lim sup
m the bound (11) on oscillation 1=(m ln 2)
9 .004904708738 .1602994490
53 .02757781675 .02722066115
54 .02757203860 .02671657484
200 .02098570878 .007213475205

Table

1: Comparison of the bound (11) with the mean value as m increases.
by Stirling's formula. On the other hand we have
lim inf
To see this, let
so that
Since
f is increasing for x ! x 0 and decreasing for x ? x 0 , where x
Therefore, letting k be the integer part of x 0 , we see thatX
f(x)dx
Z k0+1
f(x)dx:
The first integral upon substitution easily seen to be equal to
1=(m while for the second one, letting t, we
get
Z k0+1
\Gammaffi2 mx02 mt
dt
\Gammaffi2 mt
dt;
which upon substitution
du:
Using
letting q ! 1 we see that the latter expression is
bounded above by
Z m2 ffiu
and by a successive partial integration, and because we see that the
last integral is no more thanm!
Thus, Z k0+1
that is,
and the argument is completed.

Acknowledgment

We would like to express our gratitude to Herbert Wilf for
bringing to our attention the paper of Kirschenhofer and the work of Knuth on
the alternating sums that are used in our analysis.



--R

The Theory of Partitions
Losing runs in Bernoulli trials
On the multiplicity of parts in a random partition
The asymptotic probability of a tie for first place
The distribution of the number of summands in the partitions of positive integer
On a new law of large numbers
On the length of the longest head-run
Mellin transform and asymptotics: finite differences and Rice's integrals
The structure of random partitions of large integers
The number of different part sizes in a random integer partition
An extreme value theory for long head runs
Long repetitive patterns in random sequences
A note on the alternating sums
The number of winners in a discrete geometrically distributed sample
The Art of Computer Programming.
Confirming two conjectures about the integer partitions
Three problems in combinatorial asymptotics
--TR

--CTR
Pawe Hitczenko , Jeremy R. Johnson , Hung-Jen Huang, Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform, Theoretical Computer Science, v.352 n.1, p.8-30, 7 March 2006
compositions of an integer;geometric random variables;random compositions