Graph-Maker-Other
view release on metacpan or search on metacpan
devel/Hanoi-config-sequence.gp view on Meta::CPAN
\\ 2nd digit: 0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0
\\ 6 periodic, 12 periodic, etc 6*2^k, opposite ways
\\ 0, 1, 1, 2, 2, 0,0, 1, 1, 2, 2, 0,0, 1, 1, 2, 2, 0,0, 1, 1, 2, 2, 0
\\ A131555
\\ not in OEIS: 0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0,0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0,0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0
\\ vector(20,n,n--; A055662(n)%10)
\\ vector(20,n,n--; A055662(n)\10%10)
\\ vector(20,n,n--; A055662(n)\100%10)
\\ formula in A055662
A055662(n) =
{
n>=0 || error();
sum(j=0,if(n,logint(n,2)),
10^j * (floor((n/2^j + 1)/2)*(-1)^j % 3));
}
{
OEIS_check_func("A055662");
}
\\
devel/Hanoi-config-sequence.gp view on Meta::CPAN
"A060572 destination recurrence");
\\ c = A003602 Kimberling's paraphrases: if n = (2k-1)*2^m then a(n) = k.
check_equal(vector(124,n, a(n)),
vector(124,n, my(ret=0,c=0);
while(1, my(p=2^A001511(n)); c++;
ret += -(-1)^A001511(n); if(n>p,n-=p,break));
ret%3),
"A060572 destination quotient, counting one by one");
\\ first formula in A060572
check_equal(vector(1024,n, a(n)),
vector(1024,n, (A060571(n) - (-1)^A001511(n)) % 3),
"A060572 destination related to source");
\\ Donald Sampson in A060572
check_equal(vector(1024,n, a(5*n)),
vector(1024,n, (-A060571(n))%3),
"A060572(5n) by source reversed");
}
\\-----------------------------------------------------------------------------
devel/Hanoi-equal-shortest.pl view on Meta::CPAN
}
#-------------
# Other Setups
# GP-DEFINE read("OEIS-data.gp");
# GP-DEFINE read("OEIS-data-wip.gp");
# GP-DEFINE OEIS_check_verbose = 1;
# GP-DEFINE A107839_formula(n) = \
# GP-DEFINE polcoeff(lift(Mod('x,'x^2-5*'x+2)^(n+1)),1);
# GP-DEFINE A107839(n) = {
# GP-DEFINE n>=0 || error("A107839() is for n>=0");
# GP-DEFINE A107839_formula(n);
# GP-DEFINE }
# GP-Test OEIS_check_func("A107839")
# OEIS_check_func("A107839",'bfile)
# GP-DEFINE A052984_formula(n) = vecsum(Vec(lift(Mod('x,'x^2-5*'x+2)^(n+1))));
# GP-DEFINE A052984(n) = {
# GP-DEFINE n>=0 || error("A052984() is for n>=0");
# GP-DEFINE A052984_formula(n);
# GP-DEFINE }
# GP-Test OEIS_check_func("A052984")
# OEIS_check_func("A052984",,'bfile)
# my(v=OEIS_data("A052984")); \
# lindep([v, vector(#v,n,n--; polcoeff(lift(Mod('x,'x^2-5*'x+2)^(n+1)), 0)), \
# vector(#v,n,n--; polcoeff(lift(Mod('x,'x^2-5*'x+2)^(n+1)), 1)) ])
# GP-DEFINE sqrt17 = quadgen(17*4);
# GP-Test sqrt17^2 == 17
devel/Hanoi-equal-shortest.pl view on Meta::CPAN
# GP-Test my(x=fromdigits(v)/10^(#v-1)); \
# GP-Test PM_poly(x) > 0
# GP-DEFINE M = (5 - sqrt17)/2;
# (5 - sqrt(17))/2
# not in OEIS: 0.438447187191
# GP-Test PM_poly(M) == 0
# GP-Test P*M == 2
#---
# GP-DEFINE \\ powers formula by Hinz et al, x_n for n+1 discs
# GP-DEFINE xx(n) = {
# GP-DEFINE simplify(
# GP-DEFINE 3/(4*sqrt17)
# GP-DEFINE * ((sqrt17+1)*P^(n+1) - 2*3^(n+1)*sqrt17 + (sqrt17-1)*M^(n+1))
# GP-DEFINE );
# GP-DEFINE }
# GP-Test /* in x_n, A107839 across one pair n within n+1 */ \
# GP-Test vector(10,n,n--; (xx(n+1) - 3*xx(n))/6) == \
# GP-Test vector(10,n,n--; A107839(n))
#
# GP-DEFINE a_formula(n) = xx(n-1);
# GP-DEFINE a(n) = {
# GP-DEFINE n>=1 || error("a() is for n>=1");
# GP-DEFINE xx(n-1);
# GP-DEFINE }
# GP-Test vector(4,n, a(n)) == [0, 6, 48, 282]
# GP-Test a(1) == 0 /* unit triangle only */
# GP-Test a(2) == 6
# vector(12,n,n--; a(n))
# GP-Test my(want=[0,6,48,282,1476,7302,35016,164850,767340,3546366,16315248,74837802,342621396, \
devel/Hanoi-equal-shortest.pl view on Meta::CPAN
# GP-Test /* sum by Hinz et al, adjusted so a(n) */ \
# GP-Test vector(100,n, a(n)) == \
# GP-Test vector(100,n, \
# GP-Test (6/sqrt17) * sum(k=0,n-1, 3^k * (P^(n-1-k) - M^(n-1-k))))
#
# GP-Test /* subgraphs using A107839 = num between subgraphs */ \
# GP-Test vector(100,n,n++; a(n)) == \
# GP-Test vector(100,n,n++; 3*a(n-1) + 6*A107839(n-2))
#
# GP-Test my(n=1); a(n) == 0
# GP-Test my(n=1); 6*A107839_formula(n-2) == 0
# GP-Test my(n=0); a_formula(n) == 0
# GP-Test my(n=0); 6*A107839_formula(n-2) == -3
# GP-Test my(n=-1); a_formula(n) == 1
# GP-Test /* including reversing back earlier */ \
# GP-Test vector(100,n,n-=20; a_formula(n)) == \
# GP-Test vector(100,n,n-=20; 3*a_formula(n-1) + 6*A107839_formula(n-2))
# GP-Test my(n=3); A107839_formula(n-2) == 5 /* my n=3 example */
#
# GP-Test /* recurrence 8, -17, 6
# GP-Test vector(100,n,n+=2; a(n)) == \
# GP-Test vector(100,n,n+=2; 8*a(n-1) - 17*a(n-2) + 6*a(n-3))
# GP-Test vector(100,n,n-=20; a_formula(n)) == \
# GP-Test vector(100,n,n-=20; \
# GP-Test 8*a_formula(n-1) - 17*a_formula(n-2) + 6*a_formula(n-3))
#
# GP-Test /* using A052984 for the Lucas sequence part */ \
# GP-Test vector(100,n, a(n)) == \
# GP-Test vector(100,n, (A052984(n) - 3^n)*3/2 )
# GP-DEFINE g(x) = 6*x^2/((1 - 5*x + 2*x^2)*(1 - 3*x));
# GP-Test my(limit=100); g(x) + O(x^limit) == sum(n=1,limit-1, a(n)*x^n)
# GP-Test (1 - 5*x + 2*x^2) == polrecip(PM_poly(x))
#
# GP-Test /* partial fractions */ \
# GP-Test g(x) == (3/2 - 3*x)/(1 - 5*x + 2*x^2) - (3/2)/(1 - 3*x)
# GP-DEFINE \\ compact polmod
# GP-DEFINE my(p=Mod('x, 'x^2-5*'x+2)); a_compact(n) = (vecsum(Vec(lift(p^(n+1)))) - 3^n)*3/2;
# GP-Test vector(100,n, a(n)) == \
# GP-Test vector(100,n, a_compact(n))
# GP-Test vector(100,n,n-=20; a_formula(n)) == \
# GP-Test vector(100,n,n-=20; a_compact(n))
# GP-Test 6*5 + 6*3*1 == 48
# GP-Test /* A107839 across one pair n when making n+1 */ \
# GP-Test vector(10,n, (a(n+1) - 3*a(n))/6) == \
# GP-Test vector(10,n, A107839(n-1))
# GP-Test vector(10,n, a(n+1)) == \
# GP-Test vector(10,n, 6*A107839(n-1) + 3*a(n))
devel/lib/Graph/Maker/Permutations.pm view on Meta::CPAN
= 0,0,1,8,58,444,3708,... (A002538)
This sum is per David Callan in OEIS A002538. Elements i and j are to be
swapped. Those and the i+1,i+2,...,j-1 values between them are ordered
(j-i+1)! ways (within the whole permutation). But cannot have intermediate
values between i,j. Perms of i..j with i,j adjacent are only (j-i)!, so
fraction (j-i)!/(j-i+1)! = 1/(j-i+1) of all N! perms.
=cut
# GP-DEFINE \\ formula per A002538 but starting N=2 at value=1
# GP-DEFINE transpose_cover_num_edges(N) = /* per A002538 */ \
# GP-DEFINE if(N<=1,0, (N+1)*transpose_cover_num_edges(N-1) + (N-1)*(N-1)!);
# GP-Test vector(7,N,N--; transpose_cover_num_edges(N)) == [0,0,1,8,58,444,3708]
#
# new element N at any of N positions
# covers in N-1 still good so N*covers(N-1)
# covers i to N has new N bigger
# so x ... N with N at any position
#
# sum N* for i<j<N
devel/lib/Graph/Maker/SierpinskiTriangles.pm view on Meta::CPAN
There are various enclosed regions other than such upwards unit triangles.
Total number of interior regions follows from the top-down replications by 3
copies and a new middle,
NumRegions(N) = 3*NumRegions(N) + 1
= (3^(N+1) - 1)/2
= 1, 4, 13, 40, 121, 364, ... (A003462)
The graph is planar by its construction, so the combination of vertices,
edges and interior regions satisfy Euler's formula
NumVertices(N) + NumRegions(N) = NumEdges(N) + 1
=cut
# GP-DEFINE NumRegions(N) = {
# GP-DEFINE N>=0 || error();
# GP-DEFINE (3^(N+1) - 1)/2;
# GP-DEFINE }
# GP-Test NumRegions(0) == 1
devel/misc.pl view on Meta::CPAN
MyGraphs::hog_searches_html($graph);
exit 0;
}
{
# n=11 no duplicated leaf
# https://hog.grinvin.org/ViewGraphInfo.action?id=28553
# https://hog.grinvin.org/ViewGraphInfo.action?id=28555
my $n = 11;
my $formula = int((2*$n-1)/3);
print "n=$n\n";
print "formula $formula\n";
my $iterator_func = MyGraphs::make_tree_iterator_edge_aref
(num_vertices_min => $n,
num_vertices_max => $n,
connected => 1);
my $count = 0;
my @graphs;
while (my $edge_aref = $iterator_func->()) {
my $graph = MyGraphs::Graph_from_edge_aref($edge_aref, num_vertices => $n);
next if Graph_has_duplicated_leaf($graph);
my $indnum = MyGraphs::Graph_tree_indnum($graph);
if ($indnum == $formula) {
my $g6_str = MyGraphs::graph6_str_to_canonical
(MyGraphs::Graph_to_graph6_str($graph));
print "n=$n ",MyGraphs::hog_grep($g6_str)?"HOG":"not", "\n";
# MyGraphs::Graph_view($graph);
# sleep 5;
$count++;
push @graphs, $graph;
}
}
print "count $count\n";
devel/misc.pl view on Meta::CPAN
# GP-Test my(k=4,n=3*k+2); 2*k+1 == 9 && n==14
# n=15 indnum 9
foreach my $n (# 12 .. 14,
11,
) {
my $graph = make_extremal_nodupicated_leaf_indnum($n);
MyGraphs::Graph_view($graph);
my $indnum = MyGraphs::Graph_tree_indnum($graph);
my $formula = int((2*$n-1)/3);
print "n=$n indnum $indnum formula $formula\n";
$graph->vertices == $n or die;
}
exit 0;
sub make_extremal_nodupicated_leaf_indnum {
my ($n) = @_;
my $graph = Graph->new (undirected=>1);
$graph->set_graph_attribute (name => "n=$n");
my $upto = 1; # next prospective vertex number
$graph->add_vertex($upto++);
devel/wiener.pl view on Meta::CPAN
# (N-1)*(N)*(N+1)/3 / (N-1) / N^2 -> 1/3
#
# GP-DEFINE linear_diameter(k) = k-1;
# GP-DEFINE linear_W_by_sum(k) = sum(i=1,k, sum(j=i+1,k, j-i));
# vector(20,k,k--; linear_W_by_sum(k))
# GP-DEFINE linear_W(k) = 1/6*k*(k^2-1);
# \\ A000292 tetrahedral n*(n+1)*(n+2)/6 = (n+1)*((n+1)^2-1)/6
# GP-Test vector(100,k,k--; linear_W(k)) == vector(100,k,k--; linear_W_by_sum(k))
# GP-DEFINE linear_binomial(k) = k*(k-1)/2;
# vector(100,k,k--; linear_binomial(k)) == vector(100,k,k--; binomial(k,2))
# GP-DEFINE linear_mean_by_formula(k) = linear_W(k) / (linear_diameter(k) * binomial(k,2));
# linear_mean(k) = 1/6*k*(k^2-1) / (k*(k-1)/2) / (k-1);
# linear_mean(k) = 1/3*(k+1)/(k-1);
# linear_mean(k) = my(n=k-1); (n+2)/(3*n);
# linear_mean(k) = my(n=k+1); n/(3*(n-2));
# GP-DEFINE linear_mean(k) = 1/3 + 2/3/(k-1);
# GP-Test vector(100,k,k++; linear_mean(k)) == vector(100,k,k++; linear_mean_by_formula(k))
# GP-Test my(k=1000000); nearly_equal(linear_mean(k), 1/3, 1e-3) \\ -> 1/3
# GP-DEFINE A060789(n) = n/gcd(n,2)/gcd(n,3); \\ numerator
# GP-Test vector(100,k,k++; numerator(linear_mean(k))) == vector(100,k,k++; A060789(k+1))
# vector(30,k,k++; denominator(linear_mean(k))) \\ *1.0
# can divide out possible 2 if n even, possible 3 too,
# otherwise n,n-1 no common factor
# denominator not
#
#--------------------
# star of k vertices
# *
# |
# *--*--*
# GP-DEFINE star_W_by_terms(k) = if(k==0,0, 2*binomial(k-1,2) + k-1);
# star_W(0) == 0
# star_W(4) == 1+2+2 + 1+1 + 2
# GP-DEFINE star_W(k) = if(k==0,0, (k-1)^2);
# GP-Test vector(100,k,k--; star_W(k)) == vector(100,k,k--; star_W_by_terms(k))
# GP-DEFINE star_diameter(k) = if(k<=1,0, k==2,1, 2);
# GP-DEFINE star_mean_by_formula(k) = star_W(k) / star_diameter(k) / binomial(k,2);
# GP-DEFINE star_mean(k) = if(k==2,1, 1 - 1/k); \\ -> 1
# GP-Test vector(100,k,k++; star_mean(k)) == vector(100,k,k++; star_mean_by_formula(k))
# vector(20,k,k++; star_mean(k))
#
#----------
# Graph::Maker::BalancedTree, rows 0 to n inclusive
# A158681 Wiener of complete binary tree = 4*(n-2)*4^n + 2*(n+4)*2^n
# = 4, 48, 368, 2304 starting n=1
# * (1+2 + 2 + 1+2)/2 = 4
# / \ has 2^(n+1)-1 vertices
# * *
# diameter 2*n
# GP-DEFINE complete_binary_W(n) = 4*(n-2)*4^n + 2*(n+4)*2^n;
# GP-Test complete_binary_W(1) == 4
# GP-Test complete_binary_W(2) == 48
# GP-DEFINE complete_binary_N(n) = 2^(n+1)-1;
# GP-Test complete_binary_N(1) == 3
# GP-DEFINE complete_binary_diameter(n) = 2*n;
# GP-Test complete_binary_diameter(1) == 2
# GP-DEFINE complete_binary_mean(n) = 2*complete_binary_W(n) \
# GP-DEFINE / complete_binary_N(n)^2 \
# GP-DEFINE / complete_binary_diameter(n);
# GP-DEFINE complete_binary_mean_formula(n) = \
# GP-DEFINE 1 - 2/n + 3*1/(2*2^n - 1) + 2*(1 + 1/n)*1/(2*2^n - 1)^2;
# GP-Test vector(100,n, complete_binary_mean_formula(n)) == vector(100,n, complete_binary_mean(n))
# complete_binary_mean -> 1 slightly slowly
#
#----------
# BinomialTree
# A192021 Wiener of binomial tree = 2*n*4^n + 2^n
# W Binomial tree = (k-1)*2^(2k-1) + 2^(k-1)
# (in POD)
#
#----------
# Cycle
devel/wiener.pl view on Meta::CPAN
# cycle_W_by_sum(0) == 0
# cycle_W_by_sum(1) == 0
# cycle_W_by_sum(2) == 1
# cycle_W_by_sum(3) == 3
# cycle_W_by_sum(4) == 1+1+2 + 1+2 + 1
# vector(20,k,k--; cycle_W_by_sum(k))
# GP-DEFINE cycle_W(k) = 1/2 * k * floor((k/2)^2);
# GP-DEFINE cycle_W(k) = 1/2*k*((k/2)^2 - if(k%2==1,1/4));
# GP-Test vector(100,k,k--; cycle_W(k)) == vector(100,k,k--; cycle_W_by_sum(k))
# GP-DEFINE cycle_diameter(k) = floor(k/2);
# GP-DEFINE cycle_mean_by_formula(k) = cycle_W(k) / cycle_diameter(k) / binomial(k,2);
# GP-DEFINE cycle_mean(k) = 1/2 + (k^2/4 - 1/2*(k-1)*(k/2-if(k%2==1,1/2)) - if(k%2==1,1/4)) / (k-1) / floor(k/2);
# GP-DEFINE cycle_mean(k) = 1/2 + (k^2/4 - (k-1)*(k/4-if(k%2==1,1/4)) - if(k%2==1,1/4)) / (k-1) / floor(k/2);
# GP-DEFINE cycle_mean(k) = 1/2 + 1/4*(k*if(k%2==0,1,2) - if(k%2==0,0,1) - if(k%2==0,0,1)) / (k-1) / floor(k/2);
# GP-DEFINE cycle_mean(k) = 1/2 + 1/4*(if(k%2==0,k,2*k-2)) / (k-1) / if(k%2==0,k/2,(k-1)/2);
# GP-DEFINE cycle_mean(k) = 1/2 + 1/2*if(k%2==0,k / (k-1) / if(k%2==0,k,k-1),(2*k-2) / (k-1) / if(k%2==0,k,k-1));
# GP-DEFINE cycle_mean(k) = 1/2 + 1/2*if(k%2==0, 1/k + 1/(k*(k-1)), 2/(k-1));
# GP-Test vector(100,k,k++; cycle_mean(k)) == vector(100,k,k++; cycle_mean_by_formula(k))
# GP-Test my(k=1000000); nearly_equal(cycle_mean(k), 1/2, 1e-3) \\ -> 1/2
# vector(30,k,k++; numerator(cycle_mean(k)))
# vector(30,k,k++; denominator(cycle_mean(k)))
#
#----------
# Hypercube
# GP-DEFINE hypercube_W_by_sum(k) = sum(i=0,2^k-1, sum(j=i+1,2^k-1, hammingweight(bitxor(i,j))));
# hypercube_W_by_sum(0) == 0
# hypercube_W_by_sum(1) == 1
# hypercube_W_by_sum(2) == 8
# vector(8,k,k--; hypercube_W_by_sum(k))
#
# GP-DEFINE hypercube_W(k) = k*4^(k-1);
# GP-Test vector(10,k,k--; hypercube_W(k)) == \
# GP-Test vector(10,k,k--; hypercube_W_by_sum(k))
#
# GP-DEFINE hypercube_diameter(k) = k;
# GP-DEFINE hypercube_mean_by_formula(k) = \
# GP-DEFINE hypercube_W(k) / hypercube_diameter(k) / binomial(2^k-1,2);
# GP-DEFINE hypercube_mean(k) = 1/2 * 4^k / (2^k-1)/(2^k-2);
# GP-Test vector(20,k,k++; hypercube_mean_by_formula(k)) == \
# GP-Test vector(20,k,k++; hypercube_mean(k))
# GP-Test vector(20,k,k++; hypercube_mean_by_formula(k)) == \
# GP-Test vector(20,k,k++; 1/2 + 1/2*(3*2^k - 2) / (2^k-1)/(2^k-2))
# GP-Test vector(20,k,k++; hypercube_mean_by_formula(k)) == \
# GP-Test vector(20,k,k++; 1/2 + 1/2*(3*2^k-3 +3 - 2) / (2^k-1)/(2^k-2))
# GP-Test vector(20,k,k++; hypercube_mean_by_formula(k)) == \
# GP-Test vector(20,k,k++; 1/2 + 3/2/(2^k-2) + 1/2/(2^k-1)/(2^k-2))
# GP-Test my(k=100); nearly_equal(hypercube_mean(k), 1/2, 1e-3) \\ -> 1/2
#
# vector(30,k,k++; numerator(hypercube_mean(k))) \\ 4^k
# vector(30,k,k++; denominator(hypercube_mean(k))) \\ binomial(2^k-1,2)
# vector(10,k,k++; hypercube_mean(k)*1.0)
require Graph::Maker::Star;
require Graph::Maker::Linear;
my @values;
lib/Graph/Maker/BinomialBoth.pm view on Meta::CPAN
0 E<lt>-E<gt> 1. Just one edge is added for this, by not applying the
set-lowest-0 rule at the low bit. Consequently there are 2^k-1 edges of
clear-lowest-1 and 2^(k-1)-1 edges of set-lowest-0 for total
num_edges(k) = / 0 if k = 0
\ 3 * 2^(k-1) - 2 if k >= 1
= 0, 1, 4, 10, 22, 46, 94, 190, ... (A296953)
=cut
# GP-DEFINE num_edges_formula(k) = 3*2^(k-1) - 2;
# GP-DEFINE num_edges(k) = if(k==0,0, num_edges_formula(k));
# GP-Test num_edges_formula(0) == -1/2
# GP-Test vector(8,k,k--; num_edges(k)) == [0, 1, 4, 10, 22, 46, 94, 190]
=pod
Each edge changes just one bit so binomial both is a sub-graph of hypercube
k (L<Graph::Maker::Hypercube>).
A top-down definition is to make order k from two copies of k-1. The max of
the first connects down to the max of the second, and the min of the first
connects down to the min of the second.
lib/Graph/Maker/BinomialBoth.pm view on Meta::CPAN
the half min and max in common, only one of those is the global min/max, so
no complementary pairs. The first half min has all of the second half as
descendants, so only first half min as global smallest and second max as
global biggest are a pair. Then the other 2^(k-1)-1 vertices of the first
half are complementary to the 2^(k-1)-1 vertices of the second half except
the second max which is the global maximum. For k=0, the single vertex is a
complementary pair 0,0.
=cut
# GP-DEFINE num_complementary_formula(k) = (2^(k-1) - 1)^2 + 1;
# GP-DEFINE num_complementary(k) = if(k==0,1, num_complementary_formula(k));
# GP-Test vector(6,k,k--; num_complementary(k)) == [1, 1, 2, 10, 50, 226]
=pod
=head2 Wiener Index
The top-down definition means the Wiener index of order k+1 is twice k plus
paths from the first k to the second k. Those paths go by the top edge or
the bottom edge between the halves, whichever is the shorter way. So a sum
over depth u in the first, depth v in the second, with respective numbers of
lib/Graph/Maker/BinomialTree.pm view on Meta::CPAN
# GP-DEFINE MeanDist_over_diameter_simplified(k) = \
# GP-DEFINE 1/2 - 1/(4*k - 2) + 1 /( (2 - 1/k) * (2^k-1) );
# GP-Test vector(100,k, MeanDist_over_diameter_simplified(k)) == \
# GP-Test vector(100,k, MeanDist_over_diameter(k))
# GP-Test my(k=100000); abs(MeanDist_over_diameter(k) - 1/2) < 1e-5
# binomial_mean -> 1/2
=pod
My C<vpar> includes an F<examples/binomial-tree-W.gp> with Wiener index
formulas for any N vertices
=over
L<http://user42.tuxfamily.org/pari-vpar/index.html>
=back
=head2 Balanced Binary
An ordered tree can be coded as pre-order balanced binary by writing at each
lib/Graph/Maker/Catalans.pm view on Meta::CPAN
rotate, so each tree edge gives a graph edge and the graph is regular of
degree N-1.
num edges = (N-1)/2*Catalan(N) or 0 if N=0
= binomial(2N-1, N-2)
= 0,0,1,5,21,84, ... (A002054)
degree N-1 regular (in-degree + out-degree)
=cut
# GP-DEFINE RotateNumEdges_formula(N) = (N-1)/2*Catalan_number(N);
# GP-DEFINE RotateNumEdges(N) = if(N==0,0, RotateNumEdges_formula(N));
# GP-Test vector(6,N,N--; RotateNumEdges(N)) == [0,0,1,5,21,84]
# GP-Test vector(20,N,N--; RotateNumEdges(N)) == \
# GP-Test vector(20,N,N--; binomial(2*N-1,N-2))
# GP-Test RotateNumEdges_formula(0) == -1/2
=pod
In terms of balanced binary, rotation moves a 1 to before the shortest
non-empty balanced substring immediately preceding,
edge from 1aaaa0 1 where 1aaaa0 shortest balanced
to 1 1aaaa0
Moving the 1 has the effect of shifting the 1A0 part up and right,
lib/Graph/Maker/FibonacciTree.pm view on Meta::CPAN
# GP-Test my(v=[0,0,1,4,11,26,56,114,223,424,789,1444,2608,4660,8253,14508]); vector(#v,k,k--; DTb(k))==v
# Iyer and Reddy preprint
# WTb(k-1) + WTb(k-2) + F(k+1) * DTb(k-2) <-- same
# + (F(k)-1) * DTb(k-1) \ different
# + F(k+1) * (F(k) - 1) /
=pod
A recurrence for the Wiener index is then as follows. (Not the same as the
WTb formula in their preprint. Is there a typo?)
WTb(k) = WTb(k-1) + WTb(k-2) + F(k+1)*DTb(k-2) + F(k)*DTb(k-1)
+ 2*F(k+1)*F(k) - F(k+2)
starting WTb(0) = WTb(1) = 0
=cut
# GP-DEFINE WTb_by_recurrence(k) = {
# GP-DEFINE if(k==0,0, k==1,0,
lib/Graph/Maker/GosperIsland.pm view on Meta::CPAN
# GP-DEFINE V(k) = 2*7^k + 3^(k+1) + 1;
# GP-DEFINE E(k) = 3*7^k + 3^(k+1);
# GP-Test vector(5,k,k--; H(k)) == [1, 7, 49, 343, 2401]
# GP-Test vector(5,k,k--; V(k)) == [6, 24, 126, 768, 5046]
# GP-Test vector(5,k,k--; E(k)) == [6, 30, 174, 1110, 7446]
# not in OEIS: 6, 24, 126, 768, 5046
# not in OEIS: 6, 30, 174, 1110, 7446
=pod
These formulas follow from a bottom-up construction. Each existing edge
becomes 3 edges and inside each hexagon is a new hexagon and edges to the
outside there to make the level 1 base figure.
=cut
# GP-Test vector(100,k,k--; V(k)+H(k)) == vector(100,k,k--; E(k)+1)
# GP-Test vector(100,k,k--; E(k+1)) == vector(100,k,k--; 3*E(k) + 12*H(k))
# GP-Test vector(100,k,k--; V(k+1)) == vector(100,k,k--; V(k)+2*E(k)+6*H(k))
=pod
lib/Graph/Maker/HanoiExchange.pm view on Meta::CPAN
#
# GP-Test OEIS_check_func("A341579")
#
# GP-Test-Last /* Stockmeyer et al, f in terms of g equation (1) */ \
# GP-Test-Last vector(100,n, f(n)) == \
# GP-Test-Last vector(100,n, 2*g(n-1) + 1)
# GP-Test-Last my(a=A341579); \
# GP-Test-Last vector(100,n, a(n)) == \
# GP-Test-Last vector(100,n, 2*A341580(n-1) + 1)
#
# GP-Test /* Stockmeyer et al, and formula above */ \
# GP-Test my(a=f); \
# GP-Test vector(100,n,n+=3; a(n)) == \
# GP-Test vector(100,n,n+=3; a(n-1) + a(n-2) + 2*a(n-4) + 3)
# GP-Test vector(100,N,N+=3; f(N) == f(N-1) + f(N-2) + 2*f(N-4) + 3) == \
# GP-Test vector(100,N,N+=3; 1)
#
# GP-Test /* f full recurrence */ \
# GP-Test my(a=f); \
# GP-Test vector(100,n,n+=4; a(n)) == \
# GP-Test vector(100,n,n+=4; 2*a(n-1) - a(n-3) + 2*a(n-4) - 2*a(n-5))
t/Catalans.t view on Meta::CPAN
ok ($predecessorless_vertices[0], '10'x$N,
'rotate_rightarm predecessorless_vertices is 10101010');
my @successorless_vertices = $graph->successorless_vertices;
ok (scalar(@successorless_vertices),
$N==0 ? 1 : $Catalan_number[$N-1],
'rotate_rightarm successorless_vertices count');
# A127632 c(x*c(x)), where c(x) = Catalans gf
# 11, 44, 185, 804, 3579
# ENHANCE-ME: Some binomial formula ?
ok (num_intervals($graph), $A127632_samples[$N],
"rotate_rightarm num_intervals N=$N");
#
# David Callan, "A Combinatorial Interpretation of the Catalan Transform
# of the Catalan Numbers", http://arxiv.org/abs/1111.0996
}
}
{
# undirected
t/Catalans.t view on Meta::CPAN
$d += ($bits[$i] ? 1 : -1);
if ($d==0 && $i < $#bits) { return 0; }
}
return 1;
}
ok ( balanced_str_is_indecomposable(''), 1);
ok ( balanced_str_is_indecomposable('10'), 1);
ok ( balanced_str_is_indecomposable('1100'), 1);
ok (! balanced_str_is_indecomposable('1010'), 1);
# Sapounakis, Tasoulas, Tsikouras, proposition 4.3 formula for num which are
# fillings, for $n >= 2.
# A086581 num Dyck words without 0011.
sub filling_num_predecessorful {
my ($n) = @_;
my $ret = 0;
foreach my $k (int($n/2) .. $n) {
$ret += (-1)**($n-$k) * binomial($k,$n-$k) * binomial(3*$k-$n, $k-1) / $k;
}
return $ret;
}
xt/BiStar-isomorphic.t view on Meta::CPAN
return ($N+$M)*($N+$M-3) + $N*$M + 2
+ ($M==0 ? $N-1 : 0)
+ ($N==0 ? $M-1 : 0);
}
{
foreach my $N (0 .. 5) {
foreach my $M (0 .. $N) {
my $bistar = Graph::Maker->new('bi_star', N=>$N, M=>$M, undirected=>1);
my $W_graph = MyGraphs::Graph_Wiener_index($bistar);
my $W_formula = BiStar_Wiener($N,$M);
ok ($W_formula, $W_graph, "BiStar Wiener N=$N, M=$M");
}
}
}
sub Star_Wiener {
my ($N) = @_;
return ($N-1)**2 + ($N==0 ? -1 : 0);
}
{
foreach my $N (0 .. 5) {
my $star = make_star(N=>$N, undirected=>1);
my $W_graph = MyGraphs::Graph_Wiener_index($star);
my $W_formula = Star_Wiener($N);
ok ($W_formula, $W_graph, "Star Wiener N=$N");
}
}
#------------------------------------------------------------------------------
sub BiStar_diameter {
my ($N,$M) = @_;
return ($N>=2) + ($M>=2) + ($N>=3 || $M>=3 || ($N>=1&&$M>=1));
}
{
foreach my $N (0 .. 5) {
foreach my $M (0 .. 5) {
my $graph = Graph::Maker->new('bi_star', N=>$N, M=>$M, undirected=>1);
my $d_graph = $graph->diameter || 0;
my $d_formula = BiStar_diameter($N,$M);
ok ($d_formula, $d_graph, "BiStar diameter N=$N, M=$M");
}
}
}
#------------------------------------------------------------------------------
# N=1 or M=1 or N=0 or M=0 same as star N+M
{
foreach my $N (0, 1) {
foreach my $M (0 .. 4) {
xt/MyGraphs-various.t view on Meta::CPAN
#------------------------------------------------------------------------------
### Graph_tree_domnum_count() of path ...
{
require Graph::Maker::Linear;
foreach my $n (1 .. 10) {
my $graph = Graph::Maker->new('linear', N => $n, undirected => 1);
if ($n) { $graph->add_vertex(1); } # bug in Graph::Maker on N=0
my $by_tree = Graph_tree_domnum($graph);
my $by_formula = int(($n+2) / 3);
ok ($by_tree, $by_formula, "path $n domnum tree=$by_tree formula=$by_formula");
}
}
#------------------------------------------------------------------------------
### Graph_tree_minimal_domsets_count() of path ...
{
require Graph::Maker::Linear;
foreach my $n (1 .. 10) {
my $graph = Graph::Maker->new('linear', N => $n, undirected => 1);
xt/MyGraphs-various.t view on Meta::CPAN
}
}
MyTestHelpers::diag("domsets_count tests $count");
ok ($bad, 0);
}
#------------------------------------------------------------------------------
### Graph_terminal_Wiener_index() of star ...
# formula in Gutman,Furtula,Petrovic
require Graph::Maker::Star;
foreach my $n (1 .. 15) {
my $graph = Graph::Maker->new('star', N => $n, undirected => 1);
my $got = MyGraphs::Graph_terminal_Wiener_index($graph);
# n<3 is a path
my $want = ($n<3 ? $n-1 : ($n-1)*($n-2));
ok ($got, $want, "star n=$n got $got want $want");
}
### Graph_terminal_Wiener_index() of path ...
# formula in Gutman,Furtula,Petrovic
require Graph::Maker::Linear;
foreach my $n (1 .. 15) {
my $graph = Graph::Maker->new('linear', N => $n, undirected => 1);
my $got = MyGraphs::Graph_terminal_Wiener_index($graph);
my $want = $n-1;
ok ($got, $want, "linear n=$n got $got want $want");
}
#------------------------------------------------------------------------------
exit 0;
xt/oeis/Catalans-oeis.t view on Meta::CPAN
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)) {
xt/oeis/Hanoi-oeis.t view on Meta::CPAN
}
} else {
# whole configuration
@path = map {cnv($_, 10, $options{'radix'})} @path;
}
$#path = $count-1;
return \@path;
});
}
# GP-DEFINE \\ formula in A055662
# GP-DEFINE A055662(n) = {
# GP-DEFINE n>=0 || error();
# GP-DEFINE sum(j=0,if(n,logint(n,2)),
# GP-DEFINE 10^j * (floor((n/2^j + 1)/2)*(-1)^j % 3));
# GP-DEFINE }
# GP-Test OEIS_check_func("A055662")
# GP-DEFINE A055661(n) = from_ternary(A055662(n));
# vector(1024,n,n--; A055661(n)) == \
# vector(1024,n,n--; OH_value(n,1))
#
xt/oeis/Hanoi-oeis.t view on Meta::CPAN
# GP-DEFINE other3(x,y) = {
# GP-DEFINE my(v=setminus([0,1,2],Set([x,y])));
# GP-DEFINE #v==1 || error();
# GP-DEFINE v[1];
# GP-DEFINE }
# GP-Test matrix(3,3,x,y,x--;y--; if(x!=y, other3(x,y))) == \
# GP-Test matrix(3,3,x,y,x--;y--; if(x!=y, 3-x-y))
# GP-DEFINE A060582(n) = if(n==0,0, (- A060582(n\3) - n)%3);
# GP-Test OEIS_check_func("A060582")
# GP-Test /* formula in A060582 */ \
# GP-Test vector(3^6,n,n--; A060582(n)) == \
# GP-Test vector(3^6,n,n--; (-A060582(floor(n/3)) - n)%3)
# GP-Test vector(3^6,n,n--; A060582(n)) == \
# GP-Test vector(3^6,n,n--; (-subst(Pol(digits(n,3)),'x,-1))%3)
# OEIS_data("A060582")
# GP-Test vector(3^6,n,n--; A060582(9*n+0)) == \
# GP-Test vector(3^6,n,n--; A060582(n))
# GP-Test vector(3^6,n,n--; A060582(9*n+4)) == \
# GP-Test vector(3^6,n,n--; A060582(n))
# GP-Test vector(3^6,n,n--; A060582(9*n+8)) == \
( run in 0.330 second using v1.01-cache-2.11-cpan-26ccb49234f )