#!/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 !/ac/ } @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] = 1                                               if ($n == 1);
    $bn[$n] = 3 * $bn[ $n - 1 ] - $bn[ $n - 2 ] + 2**($n - 2) if $n > 1;
 
    print "Recurrence: b($n) = $bn[$n]\n";
}

IyEvdXNyL2Jpbi9wZXJsCgp1c2Ugc3RyaWN0Owp1c2Ugd2FybmluZ3M7CgpteSAkTUFYbiA9IDEwOwoKIyBCcnV0ZSBmb3JjZS4KZm9yIG15ICRuICgwIC4uICRNQVhuKSB7CiAgICBteSAkYWxwaGFiZXQgID0gJ3thLGIsY30nOwogICAgbXkgQHdvcmRzICAgICA9IGdsb2IgJGFscGhhYmV0IHggJG47CiAgICBteSBAZ29vZHdvcmRzID0gZ3JlcCB7IC9hLyBhbmQgIS9hYy8gfSBAd29yZHM7CgogICAgIyBwcmludCAkXyAuICJcbiIgZm9yIChAZ29vZHdvcmRzKTsKICAgIHByaW50ICJCcnV0ZSBmb3JjZTogYigkbikgPSAiIC4gQGdvb2R3b3JkcyAuICJcbiI7Cn0KCnByaW50ICJcblxuIiAuICItIiB4IDMwIC4gIlxuXG4iOwoKIyBSZWN1cnJlbmNlIHJlbGF0aW9uLgpteSBAYm47Cgpmb3IgbXkgJG4gKDAgLi4gJE1BWG4pIHsKICAgICRiblskbl0gPSAwICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiAoJG4gPT0gMCk7CiAgICAkYm5bJG5dID0gMSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKCRuID09IDEpOwogICAgJGJuWyRuXSA9IDMgKiAkYm5bICRuIC0gMSBdIC0gJGJuWyAkbiAtIDIgXSArIDIqKigkbiAtIDIpIGlmICRuID4gMTsKCiAgICBwcmludCAiUmVjdXJyZW5jZTogYigkbikgPSAkYm5bJG5dXG4iOwp9