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

Jul 2010
3
1
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)
 
  • Like
Reactions: undefined

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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 \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.)
 
Last edited:
Jul 2010
3
1
Clarification

Hi s434,

Your choice of notation/wording is slightly confusing since C(n, k) is already commonly used to mean \(\displaystyle \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)
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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 \displaystyle S_n = \{1,\ \dots\ ,n\}\) and let \(\displaystyle \displaystyle f(n,k,x)\) be the number of k-subsets of \(\displaystyle \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 \displaystyle n = 10\)

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

\(\displaystyle \displaystyle k = 4\)

\(\displaystyle \displaystyle x = 2\)

\(\displaystyle \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..
 
Last edited:

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
So far I have a recursive solution.

Let \(\displaystyle \displaystyle g(n,k,x)\) be the number of k-subsets of \(\displaystyle \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 \displaystyle n>0\) and \(\displaystyle \displaystyle x>1\) .

Then

\(\displaystyle \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\quad\quad\ \ ,\ \ k<0\ \lor\ k>n \end{cases}\)

\(\displaystyle \displaystyle g(n,k,x) = \begin{cases} 1\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\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\quad\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.

(Made several edits.)
 
Last edited:

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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
 
Last edited:
Jul 2010
3
1
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)
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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 \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.)
 
Last edited: