Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complete integer compositions, intuitive aspects

  1. Nov 5, 2011 #1
    About two years ago, a friend of mine published his licentiate thesis in mathematics. As an non-mathematician I understood practically nothing at a first glance, but patience and determination made me grasp one of the articles at a rate of about two lines per hour.

    I used a lot of programming in Scilab to understand many of the concepts in the article, which came quite natural to me considering my background as a computer scientist (kind of, at least). The article in question was about the packing densities in compositions and one task in my search for understanding was the generation of all complete compositions of n.

    Remember that a composition of n is a way of writing n as the sum of a sequence of positive integers, where order is important (as opposed to partitions). For example, the compositions of 5 are


    The number of compositions of n can be easily shown to be [itex]2^{n-1}[/itex]. Refer to the http://en.wikipedia.org/wiki/Composition_%28number_theory%29" [Broken] for more information.

    Now, a complete composition of n is a composition containing at least one occurrence of all numbers up to the maximum number in the composition. For example, 3+1+1 is not a complete composition, since 2 is not in it. Similarly, 1+1+2+1 is complete, since it contains all numbers up to its maximum, which is 2. Thus, the eight complete compositions of 5 are:


    Here is a list of the number of complete compositions g(n) of n up to 10:

    n g(n)
    1 1
    2 1
    3 3
    4 4
    5 8
    6 18
    7 33
    8 65
    9 127
    10 264

    It doesn't take a rocket scientist to see that the g(n) is close to [itex]2^{n-2}[/itex] for all these values. Can something be said about the asymptotic behaviour of g(n)? Well, I continued to improve my algorithms and in the end I could generate g(n) for n up to about 80. I plotted the ratio between g(n) and [itex]2^{n-2}[/itex] and result was in my opinion quite remarkable.

    [PLAIN]http://forumbilder.se/images/a05201160511P55e0.jpg [Broken]

    Not only is it a strong indication that the conjecture g(n) ~ [itex]2^{n-2}[/itex] might be true. It also shows an interesting oscillating behaviour.

    I soon realized that a proof of the conjecture required much more skill than I had, and after plugging in the series at oeis.org, I found what I was looking for. The series is called http://oeis.org/A107429" [Broken] and the reference paper includes a proof of g(n) ~ [itex]2^{n-2}[/itex].

    However, since the number of complete compositions is in some sense half of the total number of compositions, I was thinking there should be an intuitive way of thinking about this, which the article doesn't go into at all. Since then, I've tried to think of ways to understand how this could be, but to no avail. So, after these tl;dr-ish ramblings, I'm asking if anyone has any insights that could bring some light on the intuitive aspects of all this.
    Last edited by a moderator: May 5, 2017
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?