Estimate the probability for a random 3-colouring of the edges of a complete graph not to contain a monochromatic spanning tree; see http://math.stackexchange.com/questions/1712204.

Question1712204.java

import java.util.Random;

public class Question1712204 {
	final static Random random = new Random ();
	final static int ntrials = 100000000;
	
	public static void main (String [] args) {
		for (int n = 3;;n++) {
			int successes = 0;
			for (int k = 0;k < ntrials;k++) {
				int [] componentCounts = new int [3];
				int [] [] componentss = new int [3] [n];
				for (int i = 0;i < 3;i++) {
					for (int j = 0;j < n;j++)
						componentss [i] [j] = j;
					componentCounts [i] = n;
				}
				
				for (int i = 1;i < n;i++)
					for (int j = 0;j < i;j++) {
						int c = random.nextInt (3);
						int [] components = componentss [c];
						int ci = getComponentIndex (components,i);
						int cj = getComponentIndex (components,j);
						if (components [cj] != components [ci]) {
							components [cj] = components [ci];
							componentCounts [c]--;
						}
					}
				if (componentCounts [0] != 1 && componentCounts [1] != 1 && componentCounts [2] != 1)
					successes++;
			}
			double estimate = 729 / 512. * n * (n-1) * (n-2) * Math.pow (8./27,n);
			double p = successes / (double) ntrials;
			double error = Math.sqrt (p * (1 - p) / ntrials) / estimate;
			System.out.println (n + " " + p / estimate + " " + error);
		}
	}
	
	static int getComponentIndex (int [] components,int i) {
		while (components [i] != i)
			i = components [i];
		return i;
	}
}