view release on metacpan or  search on metacpan

xt/oeis/Catalans-oeis.t  view on Meta::CPAN

#
# This file is part of Graph-Maker-Other.
#
# This file is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the Free
# Software Foundation; either version 3, or (at your option) any later
# version.
#
# This file is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
# or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
# for more details.
#
# You should have received a copy of the GNU General Public License along
# with Graph-Maker-Other.  See the file COPYING.  If not, see
# <http://www.gnu.org/licenses/>.

use 5.004;
use strict;
use Test;

use lib 't','xt';
use MyOEIS;
use Math::BigInt;
use MyTestHelpers;
BEGIN { MyTestHelpers::nowarnings() }

use Graph::Maker::Catalans;

use File::Spec;
use lib File::Spec->catdir('devel','lib');
use MyGraphs;

plan tests => 30;

sub binomial {
  my ($n,$k) = @_;
  if ($n < 0 || $k < 0) { return 0; }
  my $ret = 1;
  foreach my $i (1 .. $k) {
    $ret *= $n-$k+$i;
    ### assert: $ret % $i == 0
    $ret /= $i;
  }
  return $ret;
}


#------------------------------------------------------------------------------
# flip = Stanley

sub flip_num_maximal_chains {
  my ($n) = @_;

  # Richard P. Stanley, "The Fibonacci Lattice", Fibonacci Quarterly, volume
  # 13, number 3, October 1975, pages 215-232.
  # https://fq.math.ca/13-3.html
  # https://fq.math.ca/Scanned/13-3/stanley.pdf
  # Page 222, left as an exercise for the reader.
  #
  # Hook length formula Frame, Robinson, Thrall as given by Luke Nelson.
  # h(n) = binomial(n,2)! / prod(i=1,n-1, (2*i-1)^(n-i));
  # vector(8,n,n--; h(n))
  # A005118
  # h(4)

  # This code began counting powers so as to stay in 32 or 64 bits, but now
  # gone to bignum.

  my @powers;
  foreach my $i (1 .. binomial($n,2)) {
    $powers[$i]++;
  }
  foreach my $i (1 .. $n-1) {
    my $b = 2*$i - 1;   # 1 to 2n-3
    my $p = $n - $i;    # n-1 to 1
    $powers[$b] -= $p;
  }
  for (my $i = 4; $i <= $#powers; $i+=2) {
    my $t = $i;
    until ($t % 2) {
      $t /= 2;
      $powers[2] += $powers[$i];
    }
    $powers[$t] += $powers[$i];
    $powers[$i] = 0;
  }
  ### @powers
  my $ret = Math::BigInt->new(1);
  foreach my $i (0 .. $#powers) {
    $powers[$i] ||= 0;
    if ($powers[$i] > 0) { $ret *= Math::BigInt->new($i)**$powers[$i]; }
  }
  foreach my $i (0 .. $#powers) {
    if ($powers[$i] < 0) { $ret /= Math::BigInt->new($i)**-$powers[$i]; }
  }
  return $ret;
}
MyOEIS::compare_values
  (anum => 'A005118',
   max_count => 8,
   func => sub {
     my ($count) = @_;
     my @got;
     for (my $N = 0; @got < $count; $N++) {
       my $graph = Graph::Maker->new('Catalans', N => $N, rel_type => 'flip');
       push @got, MyGraphs::Graph_num_maximal_paths($graph);
     }
     return \@got;
   });
MyOEIS::compare_values
  (anum => 'A005118',
   func => sub {
     my ($count) = @_;
     my @got;
     for (my $N = 0; @got < $count; $N++) {
       push @got, flip_num_maximal_chains($N);
     }
     return \@got;
   });