Abstract
If λ is a composition of the positive integer n, define B( λ) to be the product of the parts of λ. We present a modified version of Hitczenko's stopped sequence construction that leads to a proof of the asymptotic lognormality of B for random 1-free compositions (compositions containing no parts of size 1).
Introduction
A composition of n is a sequence of positive integers whose terms, referred to as parts, sum to n. In recent years, there has been considerable interest in compositions with restrictions on the sizes of the parts. One set of restricted compositions that has been studied extensively is that of Carlitz compositions, whose adjacent part sizes cannot be equal [8, 13, 15] . A generalization of Carlitz compositions is introduced by Bender and Canfield in [2, 3, 4] where the authors study locally restricted compositions, whose part sizes are restricted to a certain set depending on the position of the part. A variety of other restricted compositions have been studied, including complete and gap-free compositions, whose part sizes form an interval [10] ; compositions with distinct part sizes [14] ; compositions with the largest part in the first position [16] ; compositions with no parts of size 2 [6] ; and compositions whose parts sizes are restricted to a general set [1, 5] .
Introduction
Problems that are straightforward for unrestricted compositions can become quite complicated when such restrictions are imposed. In [18] it is proven that, for unrestricted compositions, the product of parts is asymptotically lognormal. The proof relies heavily on a construction, devised by Hitczenko and others, that models compositions with stopped sequences of geometric random variables. However, the proof does not extend immediately to any restricted part-size setting of which we are aware. In particular, one might expect the proof to extend to compositions with no parts of size 1, since those parts do not contribute to the product. However, non-trivial adaptations are needed to make Hitczenko's technique usable in this setting. The main result in this manuscript is Theorem 1. Theorem 1. Let P n be the uniform probability measure on the set of 1-free compositions of n, and let φ = 1+ √ 5 2 be the golden ratio. Define the constants µ =
Introduction
The rate of convergence is uniform for |x| ≤
Introduction
We present the new construction used for modeling 1-free compositions, as well as some preliminary results, before presenting the proof of the main theorem. Throughout this manuscript, we denote the set of 1-free compositions of n as Λ n and an individual composition having κ n parts as λ = (λ 1 , . . . , λ κn ). P n denotes the uniform probability measure on Λ n , and E n denotes the expected value with respect to P n . If F is a formal power series in x, then we write [x n ]F to denote the coefficient of x n in F .
Expected value of B and log B
Moments of B can be computed using the following lemma. Let Λ S n denote the set of all compositions of n with parts from some set of positive integers S, and let Λ S n,d denote the set of all such compositions having d parts.
Expected value of B and log B
a . The generating function for the sequence
Expected value of B and log B
d is the sum of the a-th power of the part-products over all compositions with d parts:
Expected value of B and log B
the electronic journal of combinatorics 18 (2011), #P235
Expected value of B and log B
Summing on d we get
Expected value of B and log B
.
Expected value of B and log B
Lemma 1 is a new generalization of the following widely known generating function for the number of compositions with parts from a general set [7] . Corollary 1. The generating function for the number of compositions of n with parts from the set S is
Expected value of B and log B
Corollary 2. If λ is chosen from a uniform distribution on the set of compositions of n into parts from the set S, then the expected value of the random variable B is
Expected value of B and log B
In [18] , a probabilistic proof is given to show that the average product over all unrestricted compositions of n is F 2n /2 n−1 , where F 2n is the 2n-th Fibonacci number. An alternative approach is to cite Corollary 2 with S = Z + . It is interesting that the Fibonacci numbers also appear in two special cases that are important for this manuscript. The most prominent occurrence is in the probabilistic construction that will be presented in the next section. In addition, Corollary 1 with S = {k : k ≥ 2} gives the following known result.
Expected value of B and log B
Corollary 3. The number of 1-free compositions of n is F n−1 .
Expected value of B and log B
Corollary 2 also yields an asymptotic formula for the expected value of B for 1-free compositions.
Expected value of B and log B
Theorem 2. Let ρ 1 , ρ 2 , and ρ 3 be the distinct real roots of the function x 3 − x 2 − 2x + 1. If λ is chosen from a uniform distribution on the set of 1-free compositions of n, the expected value of the product of parts is
Expected value of B and log B
Asymptotically, the expected value is
Expected value of B and log B
As a result of Theorem 1, we know that the expected value of the log product of parts is approximately nµ 1+φ 2 . This agrees with results from [18] where the following precise estimate is obtained. Theorem 3. If λ is chosen from a uniform distribution on the set of 1-free compositions of n, the expected value of the log product of parts is
Expected value of B and log B
The proof of Theorem 3 requires the probabilistic construction presented in Section 3 as well as a detailed consideration of the distribution of the last part λ κn . The proof is omitted because it involves lengthy calculations similar to those in the proof of the asymptotic lognormality of B.
Stopped sequence construction
We begin the new construction by defining an auxiliary space Λ * n that contains all 1-free compositions of n as well as all compositions of n that are 1-free except for the last part. Let Ω n be the set of all n-length sequences ω = (ω 1 , . . . , ω n ) with ω i ≥ 2, and let τ n = min{t ≥ 1 : ω 1 · · · + ω t ≥ n} be a stopping time associated with the sequence ω. We can then construct random compositions of n by defining the function
Stopped sequence construction
Notice that H n does not always return 1-free compositions of n, since it is possible for the last part to be a 1. Moreover, if we define a probability measure on the space Λ * n in the manner of [10, 11, 12] , then H n does not select compositions uniformly.
Stopped sequence construction
Formally, if we select the ω i 's independently with probability Q n (ω i = k) = 1 φ k for k ≥ 2 and define a probability measure on Ω n by
Stopped sequence construction
then we can define a probability measure Q n • H −1 n on Λ * n , where H −1 n is described as follows. For a composition λ with κ n = k parts and last part j,
Stopped sequence construction
n is not uniform, it is conditionally uniform given the size of the last part: For ease of use, we let P * n = Q n • H −1 n and denote the expected value with respect to P * n as E * n . We denote the expected value with respect to Q n as E Q n . The following observation will complete the new construction so that it is useful for our analysis of the product of parts. If X * is any random variable on Λ * n , then there is a corresponding random variable X on Ω n defined in the obvious way, X( ω) = X * (H n ( ω)), and having the same distribution as X * :
Stopped sequence construction
Lemma 2. If X * is any random variable on Λ * n and if X = X * • H n , then for all real numbers y, P * n (X * = y) = Q n (X = y).
Number of parts
For random unrestricted compositions, the number of parts is a binomial random variable that has an expected value of n+1 2
Number of parts
. A local limit theorem is proved in [1] for the number of parts of a composition with parts from a general set, but more specific results for 1-free compositions are needed for the proof of Theorem 1.
Theorem 4.
If λ is chosen from a uniform distribution on the set of 1-free compositions of n, the expected number of parts is
Theorem 4.
Proof. Observe that the total number of parts over all compositions in Λ S n is
Theorem 4.
Using the fact that the coefficient of
Theorem 4.
Letting S = {k : k ≥ 2}, so that G 0 (x) = ∞ k=2 x k , and combining (2) with Corollary 3, we obtain
Theorem 4.
the electronic journal of combinatorics 18 (2011), #P235
Theorem 4.
A pertinent part of the lognormality proof is to show that the number of parts of a composition is concentrated around its mean. For unrestricted compositions, Chernoff bounds can be applied directly to obtain an exponentially small upper bound. For 1-free compositions, we present the following result.
Lemma 3.
There exists a constant C 1 > 0 such that
Lemma 3.
By Markov's inequality and the independence of the ω i 's,
Lemma 3.
We compute the moment generating function of ω 1 to get, for 0 < t < log φ,
Lemma 3.
If we let u =
Lemma 3.
e α log(1−u) e tn = e −tn+2tα−α log(1−u) .
Lemma 3.
Now it remains to estimate the exponent in the right-hand side of (3). Define α = ⌊ n 1+φ 2 − √ n log n⌋ and let t = 1 √ n . Then, with an application of the Taylor expansion
Lemma 3.
Now (4), (5), and (6) can be used to make substitutions in the exponent of (3). When like terms are combined, the coefficient of √ n is
Lemma 3.
the electronic journal of combinatorics 18 (2011), #P235
Lemma 3.
and the coefficient of log n is
Lemma 3.
Since the remaining terms are O(1), we have for some C 1 > 0,
Lemma 3.
A similar calculation using β = ⌈ n 1+φ 2 + √ n log n⌉ gives the inequality in the other direction.
Lemma 3.
Corollary 4. There exists a constant C 2 > 0 such that
Lemma 3.
Thus the inequality in Lemma 3 remains unchanged for P * n . Let A be the event κ n − n 1+φ 2 ≥ √ n log n. Then
Lemma 3.
φ n−2 P n (A) and
Asymptotic normality of log B
The following lemma is proved in [18] with techniques from [9] and [17] and Lemma 3 from this manuscript. After the lemma, we will begin the proof of Theorem 1. In this section, we use Φ(x) to denote the standard normal distribution.
Asymptotic normality of log B
Proof of Theorem 1. For any integer t ≥ 1, P * n (B = t) = P * n (B = t and λ κn ≥ 2) + P * n (B = t and λ κn = 1) = 1 φ n−2 |B n = t and λ κn ≥ 2| + 1 φ n−1 |B n = t and λ κn = 1|
Asymptotic normality of log B
= 1 φ n−2 |B n = t and all λ i ≥ 2| + 1 φ n−1 |B n−1 = t and all λ i ≥ 2| (8)
Asymptotic normality of log B
the electronic journal of combinatorics 18 (2011), #P235
Asymptotic normality of log B
where the step from (7) to (8) is made by noting the bijection between the set of compositions of n − 1 and the set of compositions of n with last part 1. Summing over t on both sides and letting ξ n = nγ 2 1+φ 2 x + nµ 1+φ 2 , we have
Asymptotic normality of log B
We would like to rewrite P n−1 (log B ≤ ξ n ) in terms of P n−1 (log B ≤ ξ n−1 ), so we let
Asymptotic normality of log B
and make the following calculation:
Asymptotic normality of log B
As a lower bound, we can drop the second term to get
Asymptotic normality of log B
As an upper bound, we derive from (9) the inequality
Asymptotic normality of log B
so that
Asymptotic normality of log B
Then we can obtain an upper bound as follows, with the use of Lemma 4:
Asymptotic normality of log B
the electronic journal of combinatorics 18 (2011), #P235
Asymptotic normality of log B
With use of the Taylor expansion
Asymptotic normality of log B
, we can show that
Asymptotic normality of log B
Therefore,
Asymptotic normality of log B
Going back to equation (10), we have
Asymptotic normality of log B
Letting a n = F n−1 φ n P n (log B ≤ ξ n ) and b n = P * n (log B ≤ ξ n ), we rewrite this as
Asymptotic normality of log B
Solving for a n gives
Asymptotic normality of log B
Iterating ⌊n/2⌋ times, we obtain
Asymptotic normality of log B
We now look at each term separately: 
Asymptotic normality of log B
With use of Lemma 4, we have
Asymptotic normality of log B
We again look at each term separately: 
Asymptotic normality of log B
Putting the estimates from (11), (12) , (13) , and (14) together, we get a n = Φ(x) 1 + φ 2 + O log n √ n
Asymptotic normality of log B
Recalling that a n = F n−1 φ n P n (log B ≤ ξ n ), we therefore have
Asymptotic normality of log B
a n . .

{'paper_id': '12868606', 'title': 'Part-products of 1-free integer compositions', 's2_url': 'https://api.semanticscholar.org/CorpusID:12868606', 'source': 'S2ORC'}