Number of ways to divide a stick of integer length $N$
Suppose we have a stick of integer length $N$. I'm looking for (preferably closed-form) formula that gives the numbers of ways in which we can divide the stick into 3 parts with distinct integral lengths.
EDIT: Also, every part in any division has unique length which does not appear in any other division of $N$.
EDIT2: Based on coffeemath's answer, just to clarify, I'm interested in maximal number of sums $F(n)$. Given some $N$, count the number of all possible ways to divide stick $N$ into 3 parts such that the length of any part in any valid division is unique number between $1$ an $N$.
Solution 1:
The array $$\matrix{1&30&16&4&24&31&7&18&13&15&28\cr17&2&32&20&5&14&23&8&29&22&11\cr33&19&3&27&22&6&21&25&9&10&12\cr}$$ uses each integer $1,2,\dots,33$ exactly once; each column sums to $51$ (so we have $11$ ways to divide a stick of length $51$ into three parts); and, as a bonus, each row sums to $187$. There's a calculator that finds such things.
It has been proved that an $m\times n$ magic rectangle exists provided $m$ and $n$ have the same parity and exceed $1$, with the sole exception of $m=n=2$. Taking $m=3$, this gives a way of dividing a stick of length $(9n+3)/2$ into three parts in $n$ ways, where $n$ is an arbitrary odd number exceeding $1$. It's pretty clear that stick can't be divided into three parts in more than $n$ ways; if you can do it in $k$ ways, then the numbers used must add up to $k(9n+3)/2$, but they must also add up to at least $3k(3k+1)/2$, and this is easily seen to imply $k\le n$.
In short, if $N$ is of the form $(9n+3)/2$, $n$ odd, then the number of ways is $(2N-3)/9$.
The magic rectangles theorem has been proven, and constructions given, in many papers. One, which gives references to others, is Thomas R Hagedorn, Magic rectangles revisited, Discrete Mathematics 207 (1999) 65-72. Of course, the construction is a bit of overkill for this problem, as we don't really need a magic rectangle, we just need the columns sums to be equal and don't care about the row sums. Here's a simple construction which just solves the original construction, without giving a magic rectangle: $$\matrix{1&2&3&4&5&6&7&8&9&10&11\cr17&18&19&20&21&22&12&13&14&15&16\cr33&31&29&27&25&23&32&30&28&26&24\cr}$$ The pattern should be clear.
EDIT: Now, suppose $N$ is not of the form $(9n+3)/2$ with $n$ odd. Let's write $n'=n+1$ and $n''=n+2$, and $${9n+3\over2}\lt N\lt{9n''+3\over2}$$ for some odd $n$. First, we note that $F(N)\ge n$; if $N-(1/2)(9n+3)=k$, then just add $k$ to each entry in the bottom row in the construction above. and you have $n$ ways to divide $N$ into three parts. Second, note that $F(N)\le(2N-3)/9$, by the argument a few paragraphs up about the sum of the numbers involved. So we get
If $(1/2)(9n+3)\lt N\lt (1/2)(9n'+3)$, then $f(N)=n$;
If $(1/2)(9n'+3)\le N\lt(1/2)(9n''+3)$, then $f(N)$ is either $n$ or $n+1$.
In summary, for every $N$, we have a formula for $f(N)$ which is exact in some ranges, and off by at most $1$ in other ranges. I suspect that the $n+1$ is generally correct in the situation where we haven't pinned things down. For example, for $N=20$, we have $$((9)(4)+3)/2\lt N\lt((9)(5)+3)/2$$ with the left inequality barely holding, and we get $f(20)=4$ from $$\matrix{1&2&3&4\cr5&7&8&6\cr14&11&9&10\cr}$$
Solution 2:
This is an example of achieving $a$ distinct sums for a stick of length $6a$. No specific integer occurs twice in any particular sum, or twice in two different sums, or more succinctly all the numbers involved in the sums are distinct. I think that is what the OP means in the statement of the "EDIT".
The triples are $T_k=[k,3a-2k+1,3a+k-1]$ for $1 \le k \le a.$ Each triple then has sum $6a$ as desired, and the numbers used are all distinct. The middle numbers are going down by 2 as $k$ runs through $\{1,2,...,a\}$ with the last one being $3a-2a-1=a+1$, just after the highest number $a$ of the first term in any triple, and the first middle number is the largest of the middle numbers namely $3a-2\cdot 1+1=3a-1,$ which is just before the lowest of the third elements of the triples, i.e. $3a+1-1=3a$. After that the third elements of the triples increase by 1 each step until reaching the highest third element of a triple, namely $3a+a-1=4a-1$ (So the last triple $T_a$ is $[a,a+1,4a-1]$).
I don't know if better can be done for a stick of length $6a$, but I haven't been able to prove that; it may be that some other sheme of getting different triples could give more than $a$ sums for the $6a$ long stick. What I tried to do was to have the middle numbers going down two each time, and make the block of them start right after the end of the first block going up one each time, and end just before the final block which again goes up one each time. I can't think of a denser way to pack the triples.
By the way in my opinion, given the restriction of no number used twice in any one triple or even anywhere on the list of triples obtained, the OP should specify whether his question is to find the maximal number of sums say $F(n)$ for a given stick length $n$, or on the other hand maybe the OP is interested in a formula of type $F(n,t)$ for the number of ways a stick of length $n$ can be cut into three parts in $t$ ways, no repeated numbers. The latter would be a lot harder, and even a provable formula for $F(n)$ would seem difficult, at least to me.
EDIT In this construction the "middle numbers" are spaced 2 apart. And in most cases more triples can be found in the unused numbers of the middle range. For example in the case $a=4$ with stick length $6a=24$, the $a=4$ triples formed using the construction are
$[1,11,12],\ [2,9,13],\ [3,7,14],\ [4,5,15]$
The unused numbers of the middle range make up another triple $[6,8,10],$ so that for stick length 24 one can find 5 triples.
For the case $a=10$ (stick length 60) besides the ten automatically constructed triples, the unused middle numbers are the nine even numbers from 12 through 28, and these can be put into the three triples $[12,20,28],\ [14,22,24],\ [16,18,26].$ So for stick length 60 the max number of triples is at least 13.
Solution 3:
I assume that your lengths have to be integers. Let $a, b,c$ be the lengths.
You want $a+b+c=N$ and $a,b,c$ pairwise distinct.
Since the equation is homogeneous in $a,b,c$ we can find the solutions for which $a<b<c$ and then by permuting we get all solutions (thus the no of solutions will be multiplied by 6).
Now this is a simple counting problem.
$N=a+b+c < 3c$, thus $c > \frac{N}{3}$. Also $c=N-a-b <N-2$.
For each fixed $\frac{N}{3} < c < N-2$ you need to count all the solutions to the equation $a+b =N-c$ with $a < b <c$. This is very easy, since any $b$ yields an unique $a$, the only thing you have to make sure is that $a < b <c$.
After finding this number, add this by $c$ and you get your formula...
Solution 4:
I think you're asking about partitions of an integer into distinct parts. That is, you're interested in $$ q_k(N) := \# \{ (a_1, \dots, a_s) \; : \; a_1 > \dots > a_s > 0, \; \sum a_i = N \} $$ (and $s$ is allowed to be anything). You can show that $q_k(N + \binom{k}{2}) = p_k(N)$ where $p_k(N)$ is equal the number of partitions of $N$ into exactly $k$ parts. Then, if $N$ isn't too big you can compute $p_k(N)$ via the recurrence $p_k(N) = p_{k-1}(N-1) + p_k(N-k)$. (Base conditions are $p_k(k) = 1$ for all $k$, $p_{n-1}(n) = 1$, $p_1(n) = 1$, and $p_2(n) = \lfloor n/2 \rfloor$.)