Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a follow up and motivated by this question, 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 different ways in which we can divide the stick into $m$ parts with integral lengths.

In other words, Given some $N$, count the number of all possible different ways to divide stick $N$ into $m$ parts such that the length of any part in any valid division is an integer between $1$ an $N$. Note a crude upper bound is $C_m^N$. I want an exact count or a very tight estimate. Naturally, $m \lt N$. Two divisions of a stick are different if they differ in the length of at least one part. Order of parts inside a division does not matter.

EDIT: The comment of Hagen von Eitzen partially answers my question. I'm more interested in a closed form formula. For instance, find closed-form formula for $F(N, N/2)$.

share|improve this question
    
If I understand the question correctly, you are looking for the number of strict partitions of $N$ into $m$ nonzero parts. Unlike the question linked to where you are looking for maximal collections of such partitions where additionally the sets of parts among the partitions must be disjoint; here the phrase "divisions of a stick are different if they differ in the length of at least one part" implicitly admits that two counted partitions may share some (but of course not all) of their parts. –  Marc van Leeuwen Jun 7 '13 at 8:31
    
$f(N,1)=1$. $f(N,2)=\lfloor\frac N2\rfloor$. $f(N,k)=f(N-1,k-1)+f(N-k,k)$. –  Hagen von Eitzen Jun 7 '13 at 9:10
    
@Marc You are correct. –  Mohammad Al-Turkistany Jun 7 '13 at 16:39
    
@HagenvonEitzen Could you explain how you derived the recurrence equation? –  Mohammad Al-Turkistany Jun 8 '13 at 9:57
    
@turkistany Decrease the length of each piece by 1. The first term counts the ones with a piece of length 1 (you get one piece less) the second counts the ones with no piece of length 1. –  N. S. Jun 12 '13 at 14:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.