Results 1 to 8 of 8

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

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    3

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by s4345 View Post
    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.)
    Last edited by undefined; July 10th 2010 at 05:34 PM. Reason: Clarity, typo
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    3

    Clarification

    Quote Originally Posted by undefined View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by s4345 View Post
    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..
    Last edited by undefined; July 10th 2010 at 01:37 PM. Reason: clarity
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.

    (Made several edits.)
    Last edited by undefined; July 10th 2010 at 02:56 PM. Reason: typos/errors/formatting
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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 by undefined; July 10th 2010 at 10:05 PM. Reason: program initially ran in more than twice the amount of time for some reason.. maybe I was watching a movie.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jul 2010
    Posts
    3

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by s4345 View Post
    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.)
    Last edited by undefined; July 11th 2010 at 12:48 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. probability that binary number has no consecutive ones
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 9th 2011, 09:40 PM
  2. Calculating number of non consecutive numbers
    Posted in the Statistics Forum
    Replies: 1
    Last Post: November 10th 2010, 05:17 AM
  3. division number with consecutive digits
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: June 6th 2010, 05:37 PM
  4. Replies: 2
    Last Post: November 8th 2008, 09:05 PM
  5. a consecutive number question
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 4th 2008, 04:21 AM

Search Tags


/mathhelpforum @mathhelpforum