#!/usr/bin/perl
 
use strict;
use warnings;
 
my $MAXn = 10;
 
# Brute force.
for my $n (0 .. $MAXn) {
    my $alphabet  = '{a,b,c}';
    my @words     = glob $alphabet x $n;
    my @goodwords = grep { /a/ and !/a.*c/ } @words;
 
    # print $_ . "\n" for (@goodwords);
    print "Brute force: b($n) = " . @goodwords . "\n";
}
 
print "\n\n" . "-" x 30 . "\n\n";
 
# Recurrence relation.
my @bn;
 
for my $n (0 .. $MAXn) {
    $bn[$n] = 0 if ($n == 0);
    $bn[$n] = 2 * $bn[ $n - 1 ] + 2**($n - 1) if $n > 0;
 
    print "Recurrence: b($n) = $bn[$n]\n";
}

IyEvdXNyL2Jpbi9wZXJsCgp1c2Ugc3RyaWN0Owp1c2Ugd2FybmluZ3M7CgpteSAkTUFYbiA9IDEwOwoKIyBCcnV0ZSBmb3JjZS4KZm9yIG15ICRuICgwIC4uICRNQVhuKSB7CiAgICBteSAkYWxwaGFiZXQgID0gJ3thLGIsY30nOwogICAgbXkgQHdvcmRzICAgICA9IGdsb2IgJGFscGhhYmV0IHggJG47CiAgICBteSBAZ29vZHdvcmRzID0gZ3JlcCB7IC9hLyBhbmQgIS9hLipjLyB9IEB3b3JkczsKCiAgICAjIHByaW50ICRfIC4gIlxuIiBmb3IgKEBnb29kd29yZHMpOwogICAgcHJpbnQgIkJydXRlIGZvcmNlOiBiKCRuKSA9ICIgLiBAZ29vZHdvcmRzIC4gIlxuIjsKfQoKcHJpbnQgIlxuXG4iIC4gIi0iIHggMzAgLiAiXG5cbiI7CgojIFJlY3VycmVuY2UgcmVsYXRpb24uCm15IEBibjsKCmZvciBteSAkbiAoMCAuLiAkTUFYbikgewogICAgJGJuWyRuXSA9IDAgaWYgKCRuID09IDApOwogICAgJGJuWyRuXSA9IDIgKiAkYm5bICRuIC0gMSBdICsgMioqKCRuIC0gMSkgaWYgJG4gPiAwOwoKICAgIHByaW50ICJSZWN1cnJlbmNlOiBiKCRuKSA9ICRiblskbl1cbiI7Cn0=