My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
February 24th, 2009, 06:20 AM   #1
Joined: Feb 2009

Posts: 2
Thanks: 0

Complexity of Problem


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.
UnOriginal is offline  
February 24th, 2009, 07:25 AM   #2
Global Moderator
CRGreathouse's Avatar
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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.
CRGreathouse is offline  
August 26th, 2009, 08:05 AM   #3
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.
UnOriginal is offline  

  My Math Forum > College Math Forum > Applied Math

complexity, problem

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
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
Computability/Complexity problem related to Lotto/Keno. ChessTal Computer Science 3 January 27th, 2010 08:23 AM
complexity problem baxy7 Applied Math 14 April 20th, 2009 03:29 PM

Copyright © 2017 My Math Forum. All rights reserved.