I have an algorithm returning a set of groups from a time series. Be $X$ this time series, made of $n$ points $x_1$ to $x_n$.

My algorithm returns from the time series a set of groups G, containig the $nG$ groups $g_1$ to $g_{nG}$.

Every point in $X$ belongs to one and only one group.

Moreover, the groups are made of consecutive points, i.e. the first group contains points whose indices in the time series range from $a_1$ to $b_1$ with $a_1=1$, the second group is made of the points $a_2=b_1+1$ to $b_2$ and so on until the last group $g_{nG}$ whose points have the indices $a_{nG}=b_{nG-1}+1$ to $n$.

My question is : given $n$ and $nG$, how many different set of groups can I have ?

Simple remarks can be made. First, the smallest group size is 1. This yields directly the second remark, i.e. the largest group size is $n-nG+1$.

Let us denote $S$ the set of possible groups and for instance $G=\{(1,10), (11,20), (21,30)\}$ one of its element. In this example, $n=30$, $nG=3$, the group 1 ranges from 1 to 10, the group 2 from 11 to 20 and the group 3 from 21 to 30.

If $nG=2$, then for any $n$ the result is obviously $|S|=n-1$, since the set of possible groups is $S=\{\{(1,1),(2,n)\},\{(1,2),(3,n)\},\{(1,3),(4,n)\}$...$\{(1,n-1),(n,n)\}\}$.

For $n=5$ and $nG=3$, the possible groups are $\{(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)\}$. More generally, for any $n$ and $nG=3$, it seems that $S=\sum_{i=1}^{n-nG+1}i=(n-nG+1)(n-nG+2)/2$

I think this problem is equivalent to evaluating the sum $$\sum_{a_1=1<a_2<a_3<...<a_{nG-1}<a_{nG}=n}1$$ but I am not able to evaluate it...

Thanks in advance for your help !


stars and bars argument: There are $n$ balls and $nG-1$ bars so that each part (the size of a group) is non-empty. Hence, $\binom{n-1}{nG-1}$ different sets of groups.

  • $\begingroup$ Actually, I may not have formulated my problem correctly, but there is nG groups and n stars (as indicated in the great Wikipedia article you sent me), so this is exactly $\left(\begin{array}{c} n-1\\ n_{G}-1 \end{array}\right)$ different set of groups. Thanks for your help ! $\endgroup$ – Gim Jul 1 '14 at 7:00
  • $\begingroup$ Thanks, I have edited from $\binom{n-1}{nG-2}$ to $\binom{n-1}{nG-1}$. $\endgroup$ – talegari Jul 2 '14 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.