Results 1 to 6 of 6

Math Help - How to reduce number of tables?

  1. #1
    Newbie
    Joined
    Jun 2008
    Posts
    8

    Question How to reduce number of tables?

    Hi!

    If someone pick six numbers from {1,2,3,4,5,...,45,46,47,48,49} there are 13983816 combination.

    I want to make some tables (7-rows and 49-columns) in wich every combination of six numbers will fit in any column of these tables.

    Looks like this table (7x7):


    How many different tables shoud I build to have all of these combination on one of these tables?

    pls help me (if this is possible)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by aRTx View Post
    Hi!

    If someone pick six numbers from {1,2,3,4,5,...,45,46,47,48,49} there are 13983816 combination.

    I want to make some tables (7-rows and 49-columns) in wich every combination of six numbers will fit in any column of these tables.

    Looks like this table (7x7):


    How many different tables shoud I build to have all of these combination on one of these tables?
    If I'm understanding you correctly, this is a simple division problem. You have 13983816 possible combinations (correct), 49 of which are listed in each table. So you need 13983816\div49 = 285384 tables.

    I suspect that you actually mean something a bit different from that, but it's not clear exactly what. Can you state the problem more precisely?

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2008
    Posts
    8

    Question

    Hi Opalg!
    Thnx for your time...

    Look there are 13983816 combination and if every combination we will put in columns we will have 13983816 columns (a table with 6-rows and 13983816 columns).

    But I want a table with 7-rows and x-columns to include every combination of six from 49!

    Is this possible?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by aRTx View Post
    Look there are 13983816 combination and if every combination we will put in columns we will have 13983816 columns (a table with 6-rows and 13983816 columns).

    But I want a table with 7-rows and x-columns to include every combination of six from 49!

    Is this possible?
    Now I see what you're getting at (I think). I misread the question previously, overlooking the fact that there are 7 rows, not 6, in the table.

    With 7 numbers in a column, each column contains 7 of the possible 6-element subsets. If a table has 49 columns then it can include 749 = 343 of the 6-element subsets. Since 13983816\div343 = 40769\tfrac17, it will require at least 40770 tables to list every combination. But I have no idea whether there is an algorithm that will indicate how to do the job with just that number of tables.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jun 2008
    Posts
    8

    Question My sample...

    Thnx, but is there any way to find the number of tables because we have many replication of combinations...

    Look: I have generate combination of k=2 from n=9 and I have transform in all of possible tables

    The first table is the main table of our combination n=9 and k=2 but the in the other tables are all of these combination.

    My question is:
    If i have n=49 and k=6 and we made tables with 12-rows then how many tables we will have (excact) to include all of these combination?

    thnx very much!
    It is very important for me...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by aRTx View Post
    Thnx, but is there any way to find the number of tables because we have many replication of combinations...

    Look: I have generate combination of k=2 from n=9 and I have transform in all of possible tables

    The first table is the main table of our combination n=9 and k=2 but the in the other tables are all of these combination.

    My question is:
    If i have n=49 and k=6 and we made tables with 12-rows then how many tables we will have (exact) to include all of these combination?

    thnx very much!
    It is very important for me...
    I'm still no nearer to helping you with the general problem, but you can certainly improve on the algorithm that you are using. For example, when n=9 and k=2, the table with three rows includes three triples containing both 4 and 5. That is wasteful. You can reduce the number of columns from 16 to 12 (the minimum possible) like this:

    \begin{matrix}1&4&7&1&2&3\\ 2&5&8&4&5&6 \\ 3&6&9&7&8&9\end{matrix}\kern10pt\begin{matrix}1&2&  3&1&2&3\\ 5&6&4&6&4&5 \\ 9&7&8&8&9&7\end{matrix}

    For ideas on how to produce tables in the case where k=2, you could try googling for things like round robin tournament algorithm. When k=2 and the number of rows in the table divides n (the total number of elements in the pool), there is probably an efficient algorithm for achieving the minimum number of combinations. In your case, 7 (the number of rows) does divide 49 (the number of elements), which may mean that the problem has a good solution. But you are taking k=6, which makes the combinatorial problem massively more complicated and possibly takes you into unexplored territory. Sorry I can't help you further.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Reduce
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 25th 2010, 12:21 PM
  2. Is there a way to further reduce this?
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: September 24th 2009, 05:06 AM
  3. Reduce the expression
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 7th 2009, 04:43 PM
  4. Replies: 1
    Last Post: October 13th 2008, 06:14 PM
  5. Reduce Basis
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 22nd 2008, 01:27 PM

Search Tags


/mathhelpforum @mathhelpforum