Results 1 to 5 of 5

Math Help - Generating combinations

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    3

    Generating combinations

    we have integer N = 1*n1+2*n2+3*n3+4*n4+5*n5+6*n6+7*n7+8*n8+9*n9 .
    How to calculate total possible number of n1..n9 combinations?
    n can be any positive integer including 0.
    Also algo to generate all of that combinations?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    Clarification

    Just to clarify your notation here, are you saying:

    (1) N = n^1+2n^2+3n^3+4n^4+5n^5+6n^6+7n^7+8n^8+9n^9

    or

    (2) N = n_1+2n_2+3n_3+4n_4+5n_5+6n_6+7n_7+8n_8+9n_9

    I believe you are referring to (2) here. Are you seeking a computer program that will input N and count all possible solutions (n_1,n_2,...,n_9) - easy - or are you looking for a mathematical formula f(N) that will tell you how many solutions there are - hard?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    3
    Quote Originally Posted by Media_Man View Post
    Just to clarify your notation here, are you saying:

    (1) N = n^1+2n^2+3n^3+4n^4+5n^5+6n^6+7n^7+8n^8+9n^9

    or

    (2) N = n_1+2n_2+3n_3+4n_4+5n_5+6n_6+7n_7+8n_8+9n_9

    I believe you are referring to (2) here. Are you seeking a computer program that will input N and count all possible solutions (n_1,n_2,...,n_9) - easy - or are you looking for a mathematical formula f(N) that will tell you how many solutions there are - hard?

    Yes, I mean (2). I'm writing computer program where I need to esimate total number of possible solutions for given N and then rank all of them not trying the same combination twice. Actually the problem turns in to finding all possible combinations. Then is easy to count them. But how to eficiently find all possible combinations?
    Last edited by 82026; May 12th 2009 at 10:45 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    The Partition Problem

    This question is equivalent to finding all possible partitions of N, restricting the number of terms to 9.

    Start with N = n_1+2n_2+3n_3+4n_4+5n_5+6n_6+7n_7+8n_8+9n_9

    Define m_i=n_i+n_{i+1}+...+n_8+n_9 And you can see that N=m_1+m_2+m_3+m_4+m_5+m_6+m_7+m_8+m_9. In other words, all possible partitions of the number N with no more than 9 terms. By construction, n_i=m_{i} - m_{i+1} \geq 0 .

    Example. Let N=8.

    m_1+m_2+m_3+m_4+m_5+m_6+m_7+m_8+m_9
    8
    7 + 1
    6 + 2
    6 + 1 + 1
    5 + 3
    5 + 2 + 1
    5 + 1 + 1 + 1
    4 + 4
    4 + 3 + 1
    4 + 2 + 2
    4 + 2 + 1 + 1 \rightarrow n_1=4-2=2, n_2=2-1=1, n_3=1-1=0, n_4=1-0=1 \rightarrow 1(2)+2(1)+3(0)+4(1)=8
    4 + 1 + 1 + 1 + 1
    3 + 3 + 2
    3 + 3 + 1 + 1
    3 + 2 + 2 + 1
    3 + 2 + 1 + 1 + 1
    3 + 1 + 1 + 1 + 1 + 1
    2 + 2 + 2 + 2
    2 + 2 + 2 + 1 + 1
    2 + 2 + 1 + 1 + 1 + 1
    2 + 1 + 1 + 1 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

    So you see, by indexing each partition of 8, you can directly get a solution to your equation from each one by letting n_i=m_i - m_{i+1} for each i.

    I am not familiar with resources from which to get free code, but I'm sure someone somewhere on the net can provide you with the code for a getPartitions(int N) method. You simply want to restrict yourself to those with no more than 9 terms.

    *This code is relatively easy to implement, but in number theory, as you may know, the partition function P(n)="the number of partitions of n" is a famously complicated one. I don't think that limiting them to 9 terms makes it any simpler either.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2009
    Posts
    3
    Thanks! Will try to implement this in code an see how it works. But idea looks very right!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Generating a group
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 11th 2010, 11:18 AM
  2. Generating function
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 13th 2009, 05:15 PM
  3. Generating Functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 25th 2008, 04:43 PM
  4. Generating Function
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 25th 2008, 01:50 PM
  5. Generating functions...need some help here
    Posted in the Calculus Forum
    Replies: 4
    Last Post: January 31st 2008, 04:32 PM

Search Tags


/mathhelpforum @mathhelpforum