Question

What is the probability that a randomly selected composition of N that has a second part equal to 1?

Answer 1

It is well known [1] that the number of compositions of n into parts equal to 1 or 2
is the Fibonacci number Fn+1, with F0 = 0, F1 = 1, and Fn = Fn−1 +Fn−2 for n ≥ 2.
Indeed, using induction, such a composition either has 1 for its first part, and then
can be continued in Fn−1 ways, or has 2 for its first part, and then can be continued in
Fn−2 ways. It is worth pointing out that the number of these compositions also equals
∑-
n/2
k=0
-
n−k
k

, since if such a composition has k parts equal to 2, then it has n−2k parts
equal to 1. When arranging these n−k parts in a line, there are -
n−k
k

ways to choose
the positions of the parts equal to 2.
Interestingly, the number of compositions of n into parts that are at least two is
also a Fibonacci number, namely, Fn−1. Indeed, for n = 1, there are no such composi-
tions, and for n = 2, there is one such composition. For larger values of n, we can use
induction again. Such a composition either has a 2 for its first part, and then it can be
continued in Fn−3 ways, or has a first part larger than 2, in which case subtracting 1
of that first part, we get one of Fn−2 compositions of n into parts at least two.
Even more interestingly, there is a one-to-one correspondence between these
classes of compositions even if we specify the number of parts. Indeed, the number of
compositions of n into n−k parts that are at most 2 is -
n−k
k

since such compositions
must consist of k parts equal to 2 and n − 2k parts equal to 1. The number of com-
positions of n + 2 into k + 1 parts that are at least two is also -
n+2−(k+1)−1
ksince these compositions are in bijection with the compositions of n−k+1 into k+1
parts (just add 1 to each part). Therefore, if we can compute the probability that two
randomly selected compositions have the same number of parts for one of these two
classes of compositions, the result will also apply for the other class

= -
n−k
k