Date: Wed, 01 Sep 2010 13:08:07 -0400
From: "John P. Linderman" <jpl(AT)research.att.com>

Attached is a perl script with a tighter lower bound for A094837
than A171001, based on the observation that Russ's
lcs length is coming out as 2 * ceiling(N/4) +/- 1.
So I see what combination yields the biggest number,
and report that.  It agrees with all of Russ's numbers
from index 7 on (as far as the numbers have been generated).

If you run the script without arguments, it tells you what
arguments to use.  A range reports A094837-style lower
bounds for the indexes in that range:


  a094837.lb.pl 13 16
len 13: 17640 lcs of length 7 for aaaaaaaaaabbb aaaabbbbbbbbb
len 14: 44100 lcs of length 8 for aaaaaaaaaabbbb aaaabbbbbbbbbb
len 15: 108900 lcs of length 8 for aaaaaaaaaaabbbb aaaabbbbbbbbbbb
len 16: 261360 lcs of length 9 for aaaaaaaaaaaabbbb aaaaabbbbbbbbbbb

A single value tells you about the options inspected,
as well as the A094837-style lower bound.  (I abbreviate
the X and Y strings after index 19).

  a094837.lb.pl 20
20:
        5 twice: 3003 squared = 9018009
        5 and 6: 5005 x 2002 = 10020010
        4 and 5: 4368 x 1365 = 5962320

len 20: 10020010 lcs of length 11 for (a x 15)(b x 5) (a x 6)(b x 14)


---------------------------
Postscript:

I thought it would be interesting to see which of the
combinations won out for each index.  So I made the following
tiny changes to a094837.lb.pl:

  diff a094837.which.pl bin/a094837.lb.pl   
59,60c59
<       # report($n, $c1, $q, $q);
<       print("$n:\t2\n");
---
>       report($n, $c1, $q, $q);
62,63c61
<       # report($n, $c2, $qp, $q);
<       # print("$n:\t1\n");
---
>       report($n, $c2, $qp, $q);
65,66c63
<       print("$n:\t3\n");
<       # report($n, $c3, $q, $qm);
---
>       report($n, $c3, $q, $qm);

So, instead of reporting the A094837-style information,
I just print 2 if ceil(N/4) is used twice, 3 if it is used
together with ceil(N/4) + 1.  Originally I printed 1 if it
was used with ceil(N/4) - 1, but I stopped doing that
because after index 37, that's always printed, at least up to
1000.  It can probably be shown that it will always come
out best for sufficiently large N.

(later)
Typo.  It's ceil(N/4) and ceil(N/4) + 1 that
wins out, not ceil(N/4) and ceil(N/4) - 1.

---------------------------

#!/usr/bin/perl -w

use strict;
use bignum;

sub binomial {
    my $n = shift;
    my $k = shift;
    my $choices = 1;

    for (my $i = $n - $k + 1; $i <= $n; ++$i) {
	$choices *= $i;
    }
    for (my $i = 2; $i <= $k; ++$i) {
	$choices /= $i;
    }
    return int($choices);
}

sub report {
    my ($n, $t, $l1, $l2) = @_;
    my ($X, $Y);

    if ($n <= 19) {
	$X = "a" x ($n - $l2) . "b" x $l2;
	$Y = "a" x $l1 . "b" x ($n - $l1);
    } else {
	$X = "(a x " . ($n - $l2) . ")(b x " . $l2 . ")";
	$Y = "(a x " . $l1 . ")(b x " . ($n - $l1) . ")";
    }
    print("len ", $n, ": ", $t, " lcs of length ", $l1+$l2, " for ",
	    $X, " ", $Y, "\n");
}

sub lb {
    my $n = shift;
    my $q = int(($n + 3) / 4);
    my $qp = $q + 1;
    my $qm = $q - 1;
    my $a  = binomial($n - $q, $q);
    my $a1 = binomial($n - $q, $qp);
    my $a2 = binomial($n - $qp, $q);
    my $a3 = binomial($n - $qm, $q);
    my $a4 = binomial($n - $q, $qm);
    my $c1 = $a * $a;
    my $c2 = $a1 * $a2;
    my $c3 = $a3 * $a4;

    if (@ARGV == 1) {
	print($n, ":\n");
	print("\t", $q, " twice: ", $a, " squared = ",
			$c1, "\n");
	print("\t", $q, " and ", $qp, ": ", $a1, " x ", $a2, " = ",
			$c2, "\n");
	print("\t", $qm, " and ", $q, ": ", $a3, " x ", $a4, " = ",
			$c3, "\n\n");
    }
    if (($c1 >= $c2) && ($c1 >= $c3)) {
	report($n, $c1, $q, $q);
    } elsif ($c2 >= $c3) {
	report($n, $c2, $qp, $q);
    } else {
	report($n, $c3, $q, $qm);
    }
}

sub usage {
    my $msg =<<"EOM" ;
Usage: $0 from [ to ]

If to is omitted, print details of the breakdown of from,
and the A094837-style output for from.

If to is present and no less than to, print just the
A094837-style output for each value in that range.

Example:
    $0 10           # Detailed report for 10
    $0 10 12        # Brief summary for 10 through 12
    $0 10 10        # Brief summary for 10
EOM
    print($msg);
    exit(1);
}

sub main {
    my $from = $ARGV[0];
    my $to = (@ARGV > 1) ? $ARGV[1] : $from;

    for (; $from <= $to; ++$from) {
	lb($from);
    }
}
usage() unless ((@ARGV > 0) && (@ARGV < 3));
main();