# Formula to compute number of groups from given points (with overlap)

The problem is kind of easy to understand.

Given is some points, say 10 points. (I am using numbering for understanding)

0 1 2 3 4 5 6 7 8 9

Now group these such that the group size is 5 and there is no overlap so, there can be 2 groups. the groups are (0 1 2 3 4) & (5 6 7 8 9)

Now group the above given points such that the group size is 5 and overlap is 1 so, there can be 3 groups. the groups are (0 1 2 3 4) & (4 5 6 7 8) & (8 9) //Note: don't worry that (8 9) group has only 2 points

Now group the above given points such that the group size is 5 and overlap is 3 so, there can be 3 groups. the groups are (0 1 2 3 4) & (3 4 5 6 7 ) & (6 7 8 9)

I am looking for some generalized formula to compute the number of groups

So, given the group size and overlap size, find the number of groups. Can anyone help me with finding a generalized formula

-
..such that the group size is 5 + don't worry that (8 9) group has only 2 points $$\quad$$ = $*$head asplode$*$ –  anon Feb 2 '12 at 3:52

## 1 Answer

EDIT: removed answer to my complete misunderstanding. Added new response based on comment.

We t wish to compute the number of ways to find the number of "groups" over $n$ elements with $q$ overlap. Define $g$ to be the best-try group size. That should simply be $\lceil n / (g - q) \rceil$

So for your example we would have $n = 10$, $g = 5$ and $q = 1$. $\lceil 10 / (5 - 1) \rceil = \lceil 10/4 \rceil = \lceil 2.5 \rceil = 3$

-
I kinda understand what's going on but actually I need to find the value of k. All I know is n objects, number of objects in each partition and number of overlaps. –  veda Feb 2 '12 at 5:09
Ah I completely misunderstood. I appended the correct answer. –  Nicholas Mancuso Feb 2 '12 at 5:23
In fact I needed to use this exact process for some calculation regarding some sequencing algorithms. –  Nicholas Mancuso Feb 2 '12 at 5:33