Project Euler/158

We consider strings of n <= 26 diff chars from the alphabet.

For every n, p(n) is the number of strings of length n for which exactly one character comes lexicographically AFTER its neighbour to the left.

What is the maximum value of p(n)?

Overview of approach

For a string of length n, we can compute p(n) using the number of positions in which we can substitute characters, which we denote C, for a given string of length n:

$C_{n}=C_{n-1}+2^{n-1}-1$

plus the base case,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{2} = 1 }

(This means that when we have a string of length 2, there is only 1 position in which the one character in question, that's lexicographically out of order, can possibly occupy.)

Now the number of choices for these letters depends on the length of the string via the binomial term Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \binom{26}{n}} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P(n) = \binom{26}{n} C_{n} }

The recurrence for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_n} suggests a recursive or dynamic approach might work.

Code

Code: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round5_150-160/158

$ cat Problem158.java
public class Problem158 {
	public static void main(String[] args) {
		System.out.println(solve());
	}

	public static int pow(int b, int p) {
		int result = b;
		for(int i=2; i<=p; i++) {
			result *= b;
		}
		return result;
	}

	public static String solve() {
		int m = 26;
		BinomialDP b = new BinomialDP(m);

		long p = 0;
		long priorconfigs = 1;
		for(int n=3; n<=26; n++) {

			long binom = (long)( b.binomial(26,n) );
			long configs = (long)(priorconfigs + (pow(2,n-1)-1));
			long pnew = binom*configs;

			//System.out.printf("%12d\t%12d\t%12d\t%12d\n",n,binom,configs,pnew);

			p = Math.max(p,pnew);
			priorconfigs = configs;
		}
		return Long.toString(p);
	}
}