This is quite hand-wavy but I think that's acceptable considering you want intuition. There is $1$ key gap in the result, but maybe someone can come along and fill that in nicely.
First the notation:
$N(n)$ is the number of complete compositions of $n$
$N(n,a)$ is the number of complete compositions of $n$ with $a$ as the largest term
$N(n,a,i)$ is the number of complete compositions of $n$ with $a$ as the largest term and only a single term $i$ that has to be at the end of the sequence.
For each of those, let $\tilde{N}$ denote the set of sequences that fit the description.
For example: $N(5)=8$, $N(5,1)=1$, $N(5,2)=7$, $N(5,2,2)=1$, $N(5,2,1)=1$, $\tilde{N}(5,1)=\{1+1+1+1+1\}$, $\tilde{N}(5,2,2)=\{1+1+1+2\}$, $\tilde{N}(5,2,1)=\{2+2+1\}$
Now we introduce $2$ key relations. The first one:
$$N(n)=\sum_{a=1}^{n}N(n,a)$$
This one should make sense. The total number of complete compositions of $n$, is the number of complete compositions with a maximum term of $1$ + the number of complete compositions with a maximum term of $2$ + etc.
The second one:
$$N(n,a)=\sum_{i=1}^{a}N(n-i,a)+N(n,a,i)$$
To see this, take an arbitrary composition $c\in \tilde{N}(n,a)$. Write $c=c_1+c_2+...+c_m$, and consider the composition $c'=c_1+c_2+...+c_{m-1}$. Now there are $2$ possibilities:
- $c'$ is a complete composition of $n-c_m$ with largest term $a$
- $c'$ is an incomplete composition of $n-c_m$
If $c'$ is a complete composition of $n-c_m$ with largest term $a$, then $c'\in\tilde{N}(n-c_m,a)$.
Otherwise, since $c$ was a complete composition of $n$ with largest term $a$ and $c'$ is not complete, $c_m$ must have been the only term with this value in $c$, so that removing it results in an incomplete composition. Therefore $c'\in \tilde{N}(n,a,c_m)$
You can do this reasoning the other way around as well to establish the claim.
Now we first have to agree that
$$\lim_{n\to \infty}\frac{\sum_{i=1}^{a}N(n,a,i)}{N(n,a)}=0$$
To see this, think about what compositions $\cup_{i=1}^{a}\tilde{N}(n,a,i)$ contains. This set contains all compositions that contain some term exactly once, where that term has to be the last term in the composition. It is 'intuitively clear' that this is an awfully specific subset of $\tilde{N}(n,a)$.
So that we can rewrite*:
$$N(n,a)\approx\sum_{i=1}^{a}N(n-i,a)$$
And now
$$
\begin{aligned}
N(n+1)
& =\sum_{a=1}^{n+1}N(n+1,a) \\
& \approx \sum_{a=1}^{n+1}\sum_{i=1}^{a}N(n-(i-1),a)\\
& = \sum_{a=1}^{n+1}\sum_{i=0}^{a-1}N(n-i,a)\\
& = \sum_{a=1}^{n}\sum_{i=0}^{a-1}N(n-i,a) + \sum_{i=0}^{n}N(n-i,n) \\
& = \sum_{a=1}^{n}[\sum_{i=1}^{a}[N(n-i,a)] + N(n,a) - N(n-a,a)]\\
& = \sum_{a=1}^{n}\sum_{i=1}^{a}N(n-i,a) + \sum_{a=1}^{n}N(n,a) - \sum_{a=1}^{n}N(n-a,a)\\
& \approx N(n) + N(n) - \sum_{a=1}^{n}N(n-a,a)\\
& \approx 2N(n)
\end{aligned}
$$
So now we established that $N(n)$ asymptotically will behave as $c2^n$ for some constant $c$. Now from the fact that the total number of compositions of $n$ equals $2^{n-1}$ we know that $c<\frac{1}{2}$. And from observation we know of course that $c=\frac{1}{4}$. However, I have not really been able to come up with an argument for why it is $\frac{1}{4}$. Maybe it makes sense to say that $c$ must be of the form $\frac{1}{2^m}$ because we do want $N(n)$ to be a whole number. So then all we have to do is it find a reasoning for why $N(n)>2^{n-3}$. So maybe someone who reads this will be able to complete this reasoning from here.
So this might seem like a useless result because we are still left with the question of why this constant is exactly $\frac{1}{4}$. However, with this reasoning we at least see why the ratio converges in the first place.
*A remarkable result of this approximation is that it turns out that $N(n,2)\approx\frac{1+\sqrt 5}{2}F_n$ where $F_n$ is the $n$th fibonacci number. And this approximation is very good (always only either $1$ or $2$ too large).
To complete the conversation, here is a rather concise java program to generate the sequence up to $a(200)$
import java.lang.Math;
public class PartitionCounter
{
public static void main(String[] args)
{
int F[] = new int[201];
F[0]=1;
F[1]=1;
for(int n=2; n<201; n++){
for(int k=200; k>n-1; k--){
F[k] = F[k]+F[k-n];
}
}
System.out.print("[");
for(int k=0; k<200; k++){
System.out.print((F[k]-1) + ", ");
}
System.out.print("]");
}
}
What is going on mathematically is again, we are approaching via generating functions. In this case, the generating function is:
$$\frac{1}{x-1}+\prod\limits_{k=1}^\infty (1+x^k)$$
For our purposes however, we do not need infinitely many terms, we only need the first $201$ terms of the polynomial, so the following will suffice
$$(1+x)(1+x^2)(1+x^3)\cdots (1+x^{199})(1+x^{200}) - (1+x+x^2+\dots+x^{200})$$
The coefficient of $x^n$ in the expansion of the above corresponds to the number of partitions of $n$ matching your requirements (all parts distinct and at least two parts). To see why this is, recognize that if we were to avoid adding anything together, there will be a term associated with each sequence of choosing $x^i$ vs $1$ in the product such that the powers add up to $n$.
For example, one of the contributions to the coefficient of $x^5$ comes from the sequence of choices (in red) as $(\color{red}{1}+x)(1+\color{red}{x^2})(1+\color{red}{x^3})(\color{red}{1}+x^4)\cdots$ corresponding to the partition (2,3). This is just like the "foil" method for computing $(a+b)(c+d)$ except taken to the extreme having used "infinitely many" (though only finitely many matter) parenthetical expressions being multiplied.
The code above quite literally computes the coefficients of $x^k$ in the expansion of $(1+x)(1+x^2)(1+x^3)\cdots (1+x^{200})$ and stores them in an integer array for each partial product. It only bothers to remember the coefficients for those terms up to the power $x^{200}$ because anything of higher power is irrelevant. We finally recognize that if we have a polynomial, $f(x)$ and we multiply by $(1+x^k)$, the coefficient of $x^n$ in $(1+x^k)f(x)$ will be the coefficient of $x^n$ in $f(x)$ plus the coefficient of $x^{n-k}$ in $f(x)$. The above code will update the values of $F[n]$ from back to front so as to avoid having the newly modified values disrupting further calculations without the need to create a temporary array.
Finally, we subtract one from the above because you are interested only in those partitions which have at least two parts. (this is also where the $\frac{1}{x-1}$ comes into play in the generating function, as the expansion of $\frac{1}{x-1}$ is $-1-x-x^2-x^3-x^4-\dots$)
The output for the first two hundred and one terms in the sequence is then: (note: starts at $n=0$ instead of $n=3$)
[0, 0, 0, 1, 1, 2, 3, 4, 5, 7, 9, 11, 14, 17, 21, 26, 31, 37, 45, 53, 63, 75, 88, 103, 121, 141, 164, 191, 221, 255, 295, 339, 389, 447, 511, 584, 667, 759, 863, 981, 1112, 1259, 1425, 1609, 1815, 2047, 2303, 2589, 2909, 3263, 3657, 4096, 4581, 5119, 5717, 6377, 7107, 7916, 8807, 9791, 10879, 12075, 13393, 14847, 16443, 18199, 20131, 22249, 24575, 27129, 29926, 32991, 36351, 40025, 44045, 48445, 53249, 58498, 64233, 70487, 77311, 84755, 92863, 101697, 111321, 121791, 133183, 145577, 159045, 173681, 189585, 206847, 225584, 245919, 267967, 291873, 317787, 345855, 376255, 409173, 444792, 483329, 525015, 570077, 618783, 671417, 728259, 789639, 855905, 927405, 1004543, 1087743, 1177437, 1274117, 1378303, 1490527, 1611387, 1741520, 1881577, 2032289, 2194431, 2368799, 2556283, 2757825, 2974399, 3207085, 3457026, 3725409, 4013543, 4322815, 4654669, 5010687, 5392549, 5802007, 6240973, 6711479, 7215643, 7755775, 8334325, 8953855, 9617149, 10327155, 11086967, 11899933, 12769601, 13699698, 14694243, 15757501, 16893951, 18108417, 19406015, 20792119, 22272511, 23853317, 25540981, 27342420, 29264959, 31316313, 33504745, 35839007, 38328319, 40982539, 43812109, 46828031, 50042055, 53466623, 57114843, 61000703, 65139007, 69545357, 74236383, 79229675, 84543781, 90198445, 96214549, 102614113, 109420548, 116658615, 124354421, 132535701, 141231779, 150473567, 160293887, 170727423, 181810743, 193582641, 206084095, 219358314, 233451097, 248410815, 264288461, 281138047, 299016607, 317984255, 338104629, 359444903, 382075867, 406072421, 431513601, 458482687, ]
Best Answer
For large $n$, these are almost all the partitions there are. There can be at most one part $m$ larger than $n$, and the remaining parts form a partition of $2n-m$, so we have
$$q(2n,n)=p(2n)-\sum_{k=0}^{n-1}\;p(k)\;.$$
For large $n$, the terms in the sum are exponentially smaller than $p(2n)$, so asymptotically
$$q(2n,n)\sim p(2n) \sim \frac {1} {8n\sqrt{3}} e^{\pi \sqrt {\frac{4n}{3}}}\;.$$