how to count the number of orderings that satisfy certain restrictions?

[joaren_56]

Hi all!
I have a question about how to count orders according to certain restrictions, I hope you can guide me.
Consider the set of n object {a(1), a(2), a(3), ..., a(n)} and n agents {1,2,3,...,n}. Each agents orders this n objects, generating a matrix nxn such that de column "j" is the order of agent j of the n objects.

For example, if n=3, a possible arrangement would be:

agent 1: agent 2: agent 3:
a(1) a(2) a(1)
a(3) a(1) a(3)
a(2) a(3) a(2)

I know that there are (n!)ˆn possible ways to have matrices of this style.

However, I am interested in how many of those arrays satisfy certain constraints.
For example, going back to n=3, if the constraints are a(1)>a(2) for agent 2, and a(3)>a(1) for agent 3, how many matrix satisfy these restrictions?

If I have "k" different "binary" conditions, How can I transform these "binary" constraints into possible cases for the previous matrices?
and thus be able to count how many of the (n!)ˆn possible matrices satisfy these k different constraints?

I hope you can guide me.
Thanks!
Best,

 

[JeffM]

If I understand your question, you want a formula that relates the number of possible distinct matrices to n and k. I greatly doubt there is such a formula because such a formula ignores the nature of the unspecified constraints and how those constraints may operate when combined.

 

[blamocur]

Hi all!
I have a question about how to count orders according to certain restrictions, I hope you can guide me.
Consider the set of n object {a(1), a(2), a(3), ..., a(n)} and n agents {1,2,3,...,n}. Each agents orders this n objects, generating a matrix nxn such that de column "j" is the order of agent j of the n objects.

For example, if n=3, a possible arrangement would be:

agent 1: agent 2: agent 3:
a(1) a(2) a(1)
a(3) a(1) a(3)
a(2) a(3) a(2)

I know that there are (n!)ˆn possible ways to have matrices of this style.

However, I am interested in how many of those arrays satisfy certain constraints.
For example, going back to n=3, if the constraints are a(1)>a(2) for agent 2, and a(3)>a(1) for agent 3, how many matrix satisfy these restrictions?

If I have "k" different "binary" conditions, How can I transform these "binary" constraints into possible cases for the previous matrices?
and thus be able to count how many of the (n!)ˆn possible matrices satisfy these k different constraints?

I hope you can guide me.
Thanks!
Best,

Questions:

1. Can we assume that no two objects are equal? I.e., for any [imath]k\neq n[/imath] we either have a(k) < a(n) or a(n) < a(k) ?
2. Are the orderings in each column completely independent of each other?
3. If the answers to 1. and 2. are Yes, then do you agree that you can compute the number of permutations for each column (which should be the same), and the simply raise it to the n-th power?

 

[joaren_56]

Thank you for your answers!

1. Yes, ">" can be considered to be a complete, transitive, and strict binary relation.
2. No, because the restrictions that I mention come from some previous ordering (column).

For example, for the case n=3, given the first column of the style: a(1) > a(2) > a(3), the restrictions for the second column would be: a(1) > a(3). Therefore, for the second column it could only be one of the following three orders: a(1) > a(2) > a(3), or a(1) > a(3) > a(2), or a( 2) > a(1) > a(3).

Then, if I choose, for the second column, the order: a(2) > a(1) > a(3), a new constraint follows for the third column: a(2) > a(3) (also including the first constraint). Therefore, the third column could only be one of two orders: a(1) > a(2) > a(3), or a(2) > a(1) > a(3).
On the other hand, if I choose, for the second column, the order: a(1) > a(3) > a(2), a new constraint follows for the third column: a(1) > a(2) (also including the first constraint). Therefore, the third column could only be one of two orders: a(1) > a(2) > a(3), or a(1) > a(3) > a(2).
But, if I choose, for the second column, the order: a(1) > a(2) > a(3), there are no additional restrictions to the first. So, the third column could only be one of three orders: a(1) > a(2) > a(3), or a(1) > a(3) > a(2), or a( 2) > a(1) > a(3)

So for the first column there are 3! ways to choose it, for the second there are 3 ways, but for the third there are scenarios with 2 ways, or with 3 ways, then there are (6*3 + 6*2 + 6*2) = 42 possible order that satisfy these restrictions.

I intend to do something like this for any number n.

Thanks!

 

[blamocur]

Can you give a more formal definition of how the order of one column effects the restrictions in the next column? From your examples it looks like the rule is: for any order in column [imath]k[/imath] all the following columns the first element of column [imath]k[/imath] must precede its last element.

Is my understanding correct? And if it is, is it the only restriction? Is the ordering of the first column arbitrary, i.e., no restrictions?

 

[joaren_56]

Can you give a more formal definition of how the order of one column effects the restrictions in the next column? From your examples it looks like the rule is: for any order in column [imath]k[/imath] all the following columns the first element of column [imath]k[/imath] must precede its last element.

Is my understanding correct? And if it is, is it the only restriction? Is the ordering of the first column arbitrary, i.e., no restrictions?

The rule is the follow:
- Given the first column, for example a(1) > a(2) > ... >a(n), the restrictions for the second column are: a(1) > a(3), a(1) > a(4), ... , a(1) > a(n), a(2) > a(4), a(2) > a(5), ..., a(2) > a(n), ..., a(n-2) > a(n). That is, there are (n-2)*(n-1)/2 restrictions for the second column. These restrictions follow the idea that "cycles" are not formed in the orderings
- So, given the first and second columns, the following columns must also not contain these "loops", considering the orders of the first, second and following columns.

And yes, the first column is free of constraints.