Number of combinations C(k,n) having max x interval between consecutive elements

• Jul 10th 2010, 03:40 AM
s4345
Number of combinations C(k,n) having max x interval between consecutive elements
Hi !
I am just stuck in a problem.

k = { 1,2,3,4,5,6,7,8,9,10 } set of positive integers
n = 4
x = 2

combination = { i1,i2,i3,i4 }

I want to find C(k,n) such that i2-i1 < x, i3-i2 < x , i4-i3 < x
I want a generalized method where the values of k,n,x can be changed.

Needed help

Senthil(Thinking)
• Jul 10th 2010, 09:34 AM
undefined
Quote:

Originally Posted by s4345
Hi !
I am just stuck in a problem.

k = { 1,2,3,4,5,6,7,8,9,10 } set of positive integers
n = 4
x = 2

combination = { i1,i2,i3,i4 }

I want to find C(k,n) such that i2-i1 < x, i3-i2 < x , i4-i3 < x
I want a generalized method where the values of k,n,x can be changed.

Needed help

Senthil(Thinking)

Hi s4345,

Your choice of notation/wording is slightly confusing since C(n, k) is already commonly used to mean $\displaystyle \binom{n}{k}$ for non-negative integers n and k. I would suggest using for example f(k,n) to mean the number of sets { i1,i2,i3,i4 } satisfying your conditions (for fixed x=2).

Also, will k always be of the form {1, 2, 3, ... , |k|} ? If so, then it would be wise to consider a function of |k| and n instead of k and n, as in g(|k|,n) = f(k,n). It's much easier to write g(5,3) than f({1,2,3,4,5},3). Knowing what restrictions are on k will affect the answer to your question, I think. (It is possible that for k of the form {1, 2, ..., |k|} there is a nice formula to be found, whereas for general set k of arbitrary integers an algorithm must be used, but I won't work on the problem until further clarity is provided.)
• Jul 10th 2010, 10:23 AM
s4345
Clarification
Quote:

Originally Posted by undefined
Hi s434,

Your choice of notation/wording is slightly confusing since C(n, k) is already commonly used to mean $\displaystyle \binom{n}{k}$. I would suggest using for example f(k,n) to mean the number of sets { i1,i2,i3,i4 } satisfying your conditions.

Also, will k always be of the form {1, 2, 3, ... , |k|} ? If so, then it would be wise to consider a function of |k| and n instead of k and n, as in g(|k|,n) = f(k,n). It's much easier to write g(5,3) than f({1,2,3,4,5},3). Knowing what restrictions are on k will affect the answer to your question, I think. (It is possible that for k of the form {1, 2, ..., |k|} there is a nice formula to be found, whereas for general set k of arbitrary integers an algorithm must be used, but I won't work on the problem until further clarity is provided.)

It is c(k,n)

k will always be of the form {1, 2, 3, ... , |k|}

Let me clarify a little bit more

according to my example

k = { 1,2,3,4,5,6,7,8,9,10 }
n = 4
x = 2

total combinations = k! / n!(k-n)! = 210

here are 2 combinations of 210

c1 = { 1,2,3,4 }
c2 = { 2,5,6,8 }

c1 satisfies my need

i2 - i1 < x
i3 - i2 < x
i4 - i3 < x

c2 does not satisfy

I wanted to eliminate all c2 type combinations

Senthil(Thinking)
• Jul 10th 2010, 12:09 PM
undefined
Quote:

Originally Posted by s4345
It is c(k,n)

k will always be of the form {1, 2, 3, ... , |k|}

Let me clarify a little bit more

according to my example

k = { 1,2,3,4,5,6,7,8,9,10 }
n = 4
x = 2

total combinations = k! / n!(k-n)! = 210

here are 2 combinations of 210

c1 = { 1,2,3,4 }
c2 = { 2,5,6,8 }

c1 satisfies my need

i2 - i1 < x
i3 - i2 < x
i4 - i3 < x

c2 does not satisfy

I wanted to eliminate all c2 type combinations

Senthil(Thinking)

Well you're interchanging sets and integers... if k = {1,2,3,4,5,6,7,8,9,10}, we wouldn't write k! but rather |k|! to mean 10! . Also you've been unclear about whether C(k,n) is an integer or a set.

I hope you don't mind, but I'll change your notation a little to make it more "standard".

Let $\displaystyle S_n = \{1,\ \dots\ ,n\}$ and let $\displaystyle f(n,k,x)$ be the number of k-subsets of $\displaystyle S_n$ such that when the elements are ordered from least to greatest, the difference of any two adjacent elements is less than x. The problem is to find a formula or algorithm to determine f(n,k,x) for arbitrary n,k,x.

Here is your example in my notation.

$\displaystyle n = 10$

$\displaystyle S_{10} = \{1,2,3,4,5,6,7,8,9,10\}$

$\displaystyle k = 4$

$\displaystyle x = 2$

$\displaystyle f(10,4,2) = 7$

This problem is tricky enough (to me) that I'll write a computer program first, and then try to come up with a simpler formula afterwards.

Java

Code:

public class CombsMaxDiffConsec {     static long c;         public static void main(String[] args) {         a(f(10,4,2)==7);         a(f(5,3,3)==8);         a(f(16,4,100)==1820);     }         static long f(int n,int k,int x) {         if(k>n||x<2) return 0;         if(k<1||k==n) return 1;         if(k==1) return n;         c=0;         f2(k,0,n,x);         return c;     }         static void f2(int r,int j,int n,int x) {         if(r==0) {             c++;             return;         }         int i,m=n-r+1;         if(j>0) m=Math.min(m,j+x-1);         for(i=j;i<m;i++)             f2(r-1,i+1,n,x);     }         static void a(boolean b) {         if(!b) throw new AssertionError();     } }
I'm thinking about finding a formula now..
• Jul 10th 2010, 12:56 PM
undefined
So far I have a recursive solution.

Let $\displaystyle g(n,k,x)$ be the number of k-subsets of $\displaystyle S_n$ with the same constraints as f(n,k,x) and the additional constraint that each k-subset must contain {1}.

Let $\displaystyle n>0$ and $\displaystyle x>1$ .

Then

$\displaystyle f(n,k,x) = \begin{cases}1\quad\quad\quad\quad\quad\quad\quad\ quad\quad\quad\quad\ \ ,\ \ k=0 \\ \displaystyle \sum_{i=k}^n g(i,k,x)\quad\quad\quad\quad\quad\quad\ \ \ ,\ \ 0 < k \le n \\ 0\quad\quad\quad\quad\quad\quad\quad\quad\quad\qua d\quad\ \ ,\ \ k<0\ \lor\ k>n \end{cases}$

$\displaystyle g(n,k,x) = \begin{cases} 1\quad\quad\quad\quad\quad\quad\quad\quad\quad\qua d\quad\ \ ,\ \ k=1 \\ \displaystyle \sum_{i=\max(1,n+1-x)}^{n-1} g(i,k-1,x) \quad,\ \ 1 < k \le n \\ 0\quad\quad\quad\quad\quad\quad\quad\quad\quad\qua d\quad\ \ ,\ \ k<1\ \lor\ k>n\end{cases}$

This could be used to write a program that quickly obtains f(n,k,x) for relatively large values of n,k,x.

I don't think I'll attempt to find a closed-form (non-recursive) solution.

• Jul 10th 2010, 03:58 PM
undefined
I updated my program. The algorithm from post #4 is renamed to naive(). There are many test cases, and I also chose an example that highlights the speed difference between the two algorithms.

Code:

public class CombsMaxDiffConsec {     static int u=100,v=100,w=100;     static long c,memoG[][][]=new long[u][v][w];         public static void main(String[] args) {         int i,j,k;         long t=time();         System.out.println("Initialising.");         for(i=0;i<u;i++)         for(j=0;j<u;j++)         for(k=0;k<w;k++)             memoG[i][j][k]=-1;         System.out.println("Time: "+(time()-t)/1000.0+" seconds");         t=time();         System.out.println("\nDoing test cases.");         // begin test cases         a(naive(10,4,2)==7);         a(naive(5,2,3)==7);         a(naive(5,3,3)==8);         a(naive(16,4,100)==1820);         for(i=0;i<10;i++)         for(j=0;j<=i;j++)         for(k=2;k<=i-j;k++)             a(f(i,j,k)==naive(i,j,k));         // end test cases         System.out.println("Time: "+(time()-t)/1000.0+" seconds");         t=time();         System.out.println("\nUsing fast algorithm:");         System.out.println("f(80,13,6) = "+f(80,13,6));         System.out.println("Time: "+(time()-t)/1000.0+" seconds");         t=time();         System.out.println("\nUsing naive algorithm:");         System.out.println("f(80,13,6) = "+naive(80,13,6));         System.out.println("Time: "+(time()-t)/1000.0+" seconds");     }         static long f(int n,int k,int x) {         if(k>n||x<2) return 0;         if(k<1||k==n) return 1;         if(k==1) return n;         int i;         long r=0;         for(i=k;i<=n;i++)             r+=g(i,k,x);         return r;     }         static long g(int n,int k,int x) {         if(k<1||k>n) return 0;         if(k==1) return 1;         if(n<u&&k<v&&x<w&&memoG[n][k][x]!=-1) return memoG[n][k][x];         int i;         long r=0;         for(i=Math.max(1,n+1-x);i<=n-1;i++)             r+=g(i,k-1,x);         if(n<u&&k<v&&x<w) memoG[n][k][x]=r;         return r;     }         static long naive(int n,int k,int x) {         if(k>n||x<2) return 0;         if(k<1||k==n) return 1;         if(k==1) return n;         c=0;         naive2(k,0,n,x);         return c;     }         static void naive2(int r,int j,int n,int x) {         if(r==0) {             c++;             return;         }         int i,m=n-r+1;         if(j>0) m=Math.min(m,j+x-1);         for(i=j;i<m;i++)             naive2(r-1,i+1,n,x);     }         static void a(boolean b) {         if(!b) throw new AssertionError();     }         static long time() {         return System.currentTimeMillis();     } }
Output

Code:

Initialising. Time: 0.014 seconds Doing test cases. Time: 0.0010 seconds Using fast algorithm: f(80,13,6) = 10742187500 Time: 0.0010 seconds Using naive algorithm: f(80,13,6) = 10742187500 Time: 43.09 seconds
• Jul 10th 2010, 09:33 PM
s4345
yes looping is not feasible for larger values of k
I have tried looping for slightly higher values for k like > 128
since the combinations are exponential it is not feasible.
(Worried)
• Jul 10th 2010, 09:42 PM
undefined
Quote:

Originally Posted by s4345
I have tried looping for slightly higher values for k like > 128
since the combinations are exponential it is not feasible.
(Worried)

The program uses memoization, and I set memory limits with u, v, and w at the beginning. If you want to get higher values in reasonable time, you will need to increase u, v, and/or w accordingly.

But if you have k that large, expect to have integer overflow. You could change to BigInteger, or if you only need the last several digits you could rewrite with a modulus.

By the way, why did you write "looping"?

Edit: Also I don't think exponential applies here, neither for the function values nor for the time or memory complexity of the algorithm. (Well the growth of $\displaystyle C\left(n,\left\lfloor \dfrac{n}{2}\right\rfloor\right)$ is I think exponential, but for fixed k it would be less than exponential.)