February 24th, 2009, 06:20 AM  #1 
Newbie Joined: Feb 2009 Posts: 2 Thanks: 0  Complexity of Problem
Hi, I have the following combinatorial problem. Let P and Q be two sets and let M: P /> Q be a partial and injective mapping from P to Q. What is the function that describes the number of allowed mappings from P to Q? For example, if I have the set {a,b} and the set {A,B,C} then the following mappings are allowed: a > A, b > B a > A, b > C a > A, b > a > B, b > A a > B, b > C a > B, b > ... In this case the number of allowed mappings is 13, but what is the general function? I need this function to give an indication of the complexity of a problem. I would say that the problem has a lower bound of O(N!). Any help would be appreciated. 
February 24th, 2009, 07:25 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Complexity of Problem
This is Sloane's A088699. Let P = p and Q = q. Then mappings(p, q) = sum(k=0, min(p, q), binomial(p, k) * binomial(q, k) * k!). The function is symmetric in p and q. If P = p = Q, then log(mappings(p)) ~ p log (p/e) + 2*sqrt(p) + log(p)/4. 
August 26th, 2009, 08:05 AM  #3 
Newbie Joined: Feb 2009 Posts: 2 Thanks: 0  Re: Complexity of Problem
I finally got a chance to look take a look at your answer. It seems to be exactly what I need. Thanks a lot.


Tags 
complexity, problem 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Computability/Complexity problem related to Lotto/Keno.  ChessTal  Computer Science  7  December 25th, 2018 11:17 AM 
Big O complexity  courteous  Computer Science  0  August 31st, 2010 02:55 AM 
O(sin n), ?(sin n), ?(sin n) complexity  ulita  Computer Science  2  August 18th, 2010 07:56 AM 
Complexity Theory  Multiple ways to describe a problem  mcaos  Computer Science  4  June 1st, 2010 12:57 PM 
complexity problem  baxy7  Applied Math  14  April 20th, 2009 03:29 PM 