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

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

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

3. ## Clarification

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

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

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

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

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

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