Combinatorics Problem (Mathematics Heavy)

[Script Coder]

I have been trying to work this out for the past few days, and have not gotten very far.

Assume there are N objects and N places to put them in (N₁ to N_N) and each place has M objects to choose from, however, each object may only appear once in the final "string" and a object may be in multiple places' sets.

To make it clearer I will provide an example.

Suppose we have 4 objects (1 through 4) and we will then have 4 places to put them into (A through D) and the following is true:
A={1}
B={2,3}
C={2,4}
D={2,3,4}

The number of combinations is 3:
1243
1324
1342

1242 cannot be as is uses object 2 twice
1234 cannot be because C cannot use object 3

I have tried so many solutions, but all of them don't work. Any help will be greatly appreciated.

[abhishekm71]

What are the bounds for N and M?

[Script Coder]

N<=1000 and M<1000

[abhishekm71]

Are you talking about factorial(1000) permutations?

[ne555]

http://en.wikipedia.org/wiki/Matching_(graph_theory)#Counting_problems

[Script Coder]

@abhishekm71
No, I do not think you understand the question. Or I do not understand your answer.

@ne555
I have no idea how that relates, but I will do some more research and get back to you if I do not find anything.

Thank you both for your help thus far.

[ne555]

You've got elements and positions as nodes
There is an edge between an element and a position if it can be put there

You want to count the number of perfect (using all the nodes) matching in the graph

[Script Coder]

Ah, now I understand, however the understanding has raised a question or two:

1) Is the graph definitely planar, because if it is not, then the algorithm won't work?
2) Does anyone know a good tutorial on computational complexity, I know the basics, but have no idea what #P is, and wikipedia's definition did little to help that.

[helios]

Graphs are not inherently geometrical.

[Script Coder]

Graphs are not inherently geometrical.

Would you mind explaining, what you mean by that, and in reference to what did you say that, please?

[helios]

Is the graph definitely planar

It seems to me that you're confusing the graph itself -- an object that describes the relationships between other objects -- with a drawing with circles and lines on a piece of paper that's meant to represent the graph in a way that is easy to visualize. In reality, the distribution of the circles on the paper and the length of the lines that connect them doesn't (necessarily) mean anything. What matters is which nodes are connected to which other nodes, and possibly how, in the case of a directed graph.

[abhishekm71]

Script Coder wrote:

@abhishekm71
No, I do not think you understand the question. Or I do not understand your answer.

Yes I think I am failing to understand your question.

What I meant was, with N <= 1000 and M < 1000, there can be a case where N = 999 and for each prospective "place" (a₁,a₂,...,a₉₉₉) M = 999.
a₁ = {all 999 elements}
a₂ = {all 999 elements}
.
.
.
a₉₉₉ = {all 999 elements}

The number of combinations in this case shall be factorial (999).

Missing something?

[Duthomhas]

What you are missing is that each pigeon hole can only hold a subset of the list of items.

[abhishekm71]

What you are missing is that each pigeon hole can only hold a subset of the list of items.

Actually I assumed that a list can be a subset of itself. However, even if you discard that assumption, then say in the example the OP gave, we can have:
A={1}
B={2,3,4}
C={2,3,4}
D={2,3,4}
The combinations are:
1234
1243
1324
1342
1423
1432
The number of combinations is factorial(3).

Similarly, if N = 1000 (not 999), then we can have a case where:
a₁ = {1}
a₂ = {all elements except 1}
a₃ = {all elements except 1}
.
.
a₁₀₀₀ = {all elements except 1}

The number of combinations shall be factorial(999).

I'm sorry for my repeat question but I genuinely do not get where I am going wrong.

[Script Coder]

@abhishekm71 Yes it is possible to have those situations, it is not always the case, and therefore cannot be a general solution.

@helios I think you should read this: http://en.wikipedia.org/wiki/Planar_graph

Would the FKT algorithm work?

[Duthomhas]

That is not the example the OP gave.

For his example, only three combinations are possible:

    1 2 4 3
    1 3 2 4
    1 3 4 2

You are generalizing on a subproblem.

[abhishekm71]

@Script Coder
My objective was not to give you the solution, but to give you an idea of the size of data involved with the bounds you are considering.

[Script Coder]

@abhishekm71 Yes I know, that is why the original problem asked for a modulo 10 007 (In case you are worried about integer overflow) I did not think it would be necessary to add as all I want to know it the general algorithm for solving this type fro problem.

But anyway back on topic, would the FKT algorithm work?