My Math Forum Complexity of Problem
 User Name Remember Me? Password

 Applied Math Applied Math Forum

 February 24th, 2009, 05: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, 06: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, 07: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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post ChessTal Computer Science 7 December 25th, 2018 10:17 AM courteous Computer Science 0 August 31st, 2010 01:55 AM ulita Computer Science 2 August 18th, 2010 06:56 AM mcaos Computer Science 4 June 1st, 2010 11:57 AM baxy7 Applied Math 14 April 20th, 2009 02:29 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top