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.

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

share|improve this question
2  
..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
add comment

1 Answer

up vote 1 down vote accepted

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$

share|improve this answer
    
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
add comment

Your Answer

 
discard

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

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