# Counting of the elements in a set

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...

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.
• 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 ! – Gim Jul 1 '14 at 7:00
• Thanks, I have edited from $\binom{n-1}{nG-2}$ to $\binom{n-1}{nG-1}$. – talegari Jul 2 '14 at 2:54