$n$ professors go to a conference and have to sit together at a table. See illustration below for $n=8$  Each professor has people they like to sit next to and people they do not want to sit next to. Given a $n\times n$ (non-symmetrical) matrix $M$ where $M_{ij}$ gives the score assigned by professor $i$ if s/he is made to sit next to professor $j$ and $M_{ii}=0$, the goal is to output a symmetrical indicator matrix $I$ where $I_{ij} = 1$ if professor $i$ is sitting next to professor $j$ such that $\sum M.*I$ is maximized (I used Matlab notation here to denote elementwise multiplication of two matrices). How can we find this optimal arrangement? Lets assume we are dealing with even $n$. From my side I spent some time calculating the total # of possible arrangements for given $n$ and arrived at this formula:$\frac{C^n_{n/2}}{2}(\frac{(n/2)!}{k})^2$where $k = 1$ if $n = 2$ and $k = 2$ otherwise.I wrote the following program to calculate the # of different arrangements for given value of $n$ (assume even $n$) according to above formula.public static void main(String[] args) {        for(int i = 2; i <= 10; i += 2)        {            System.out.printf(%d\t%s\n, i, foo(i).toString());        }    }    static BigInteger foo(int n)    {        BigInteger t1 = binomial(n, n/2).divide(BigInteger.valueOf(2));        BigInteger t2 = factorial(n / 2);        BigInteger t3 = n >= 4 ? BigInteger.valueOf(4) : BigInteger.ONE;        return t1.multiply(t2).multiply(t2).divide(t3);    }    // http://stackoverflow.com/a/2929897/147530    static BigInteger binomial(final int N, final int K) {        BigInteger ret = BigInteger.ONE;        for (int k = 0; k < K; k++) {            ret = ret.multiply(BigInteger.valueOf(N-k))                    .divide(BigInteger.valueOf(k + 1));        }        return ret;    }    static BigInteger factorial(int n) {        BigInteger ret = BigInteger.ONE;        for (int k = 2; k <= n; k++) {            ret = ret.multiply(BigInteger.valueOf(k));        }        return ret;    }Output:2   14   36   908   504010  453600
Seating arrangement problem
algorithms;counting;assignment problem