Calculate the average number of edges in a graph uniformly randomly selected from all acyclic digraphs on n nodes with at most one incoming edge and at most one outgoing edge at each node; see http://math.stackexchange.com/questions/264698.

Question264698.java

import java.math.BigInteger;

public class Question264698 {
    final static int max = 10000;

    final static BigInteger quotientFactor = BigInteger.valueOf ((1L << 63) - 1);
    public static double quotient (BigInteger num,BigInteger den) {
        return num.multiply (quotientFactor).divide (den).doubleValue () / quotientFactor.doubleValue ();
    }

    public static void main (String [] args) {
        BigInteger [] [] binomialCoefficients = new BigInteger [2] [max];
        int j = 0;
        for (int n = 1;n < max;n++) {
            BigInteger factorial = BigInteger.ONE;
            BigInteger sum = BigInteger.ONE;
            BigInteger sumk = BigInteger.ZERO;
            binomialCoefficients [j] [0] = binomialCoefficients [j] [n] = BigInteger.ONE;
            for (int k = 1;k < n;k++) {
                BigInteger K = BigInteger.valueOf (k);
                factorial = factorial.multiply (K);
                binomialCoefficients [j] [k] = binomialCoefficients [1 - j] [k].add (binomialCoefficients [1 - j] [k - 1]);
                BigInteger count = binomialCoefficients [1 - j] [k].multiply (binomialCoefficients [j] [k]).multiply (factorial);
                sum = sum.add (count);
                sumk = sumk.add (count.multiply (K));
            }
            j = 1 - j;

            if ((n & (n - 1)) == 0) {
                double expect = quotient (sumk,sum);
                System.out.println (n + " : " + sumk + " / " + sum + " = " + expect + " : " + (expect - n + Math.sqrt (n)));
            }
        }
    }
}