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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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

Copyright © 2019 My Math Forum. All rights reserved.      