cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-2 of 2 results.

A238414 Triangle read by rows: T(n,k) is the number of trees with n vertices having maximum vertex degree k (n>=1, 0<=k<=n-1).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 3, 1, 1, 0, 0, 1, 5, 3, 1, 1, 0, 0, 1, 10, 7, 3, 1, 1, 0, 0, 1, 17, 17, 7, 3, 1, 1, 0, 0, 1, 36, 38, 19, 7, 3, 1, 1, 0, 0, 1, 65, 93, 45, 19, 7, 3, 1, 1, 0, 0, 1, 134, 220, 118, 47, 19, 7, 3, 1, 1, 0, 0, 1, 264, 537, 296, 125, 47, 19, 7, 3, 1, 1
Offset: 1

Views

Author

Emeric Deutsch, Mar 05 2014

Keywords

Comments

Sum of entries in row n is A000055(n) (= number of trees with n vertices).
The author knows of no formula for T(n,k). The entries have been obtained in the following manner, explained for row n = 7. In A235111 we find that the 11 (= A000055(7)) trees with 7 vertices have M-indices 25, 27, 30, 35, 36, 40, 42, 48, 49, 56, and 64 (the M-index of a tree t is the smallest of the Matula numbers of the rooted trees isomorphic, as a tree, to t). Making use of the formula in A196046, from these Matula numbers one obtains the maximum vertex degrees: 2, 3, 3, 3, 4, 4, 3, 5, 3, 4, 6; the frequencies of 2,3,4,5,6 are 1, 5, 3, 1, 1, respectively. See the Maple program.
This sequence may be derived from A144528 which can be efficiently computed in the same manner as A000055. - Andrew Howroyd, Dec 17 2020

Examples

			Row n=4 is T(4,2)=1,T(4,3)=1; indeed, the maximum vertex degree in the path P[4] is 2, while in the star S[4] it is 3.
Triangle starts:
  1;
  0, 1;
  0, 0, 1;
  0, 0, 1,  1;
  0, 0, 1,  1,  1;
  0, 0, 1,  3,  1, 1;
  0, 0, 1,  5,  3, 1, 1;
  0, 0, 1, 10,  7, 3, 1, 1;
  0, 0, 1, 17, 17, 7, 3, 1, 1;
  ...

Links

Crossrefs

Row sums are A000055.
Cf. A144528, A196046, A235111, A332760 (connected graphs), A339788 (forests).

Programs

  • Maple
    MI := [25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64]: with(numtheory): a := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 0 elif bigomega(n) = 1 then max(a(pi(n)), 1+bigomega(pi(n))) else max(a(r(n)), a(s(n)), bigomega(r(n))+bigomega(s(n))) end if end proc: g := add(x^a(MI[j]), j = 1 .. nops(MI)): seq(coeff(g, x, q), q = 2 .. 6);
  • PARI
    \\ Here V(n, k) gives column k of A144528.
MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
M(n, m=n)={my(v=vector(m, k, V(n,k-1)[2..1+n]~)); Mat(vector(m, k, v[k]-if(k>1, v[k-1])))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) } \\ Andrew Howroyd, Dec 18 2020

Formula

T(n,k) = A144528(n,k) - A144528(n, k-1) for k > 0. - Andrew Howroyd, Dec 17 2020

Extensions

Columns k=0..1 inserted by Andrew Howroyd, Dec 18 2020

A196068 Visitation length of the rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 3, 6, 5, 10, 8, 9, 7, 11, 12, 15, 10, 13, 11, 15, 9, 14, 13, 12, 14, 14, 17, 17, 12, 19, 15, 16, 13, 18, 17, 21, 11, 20, 16, 18, 15, 16, 14, 18, 16, 19, 16, 17, 19, 20, 19, 22, 14, 17, 21, 19, 17, 15, 18, 24, 15, 17, 20, 20, 19, 20, 23, 19, 13, 22, 22, 18, 18, 22, 20, 21, 17, 21, 18, 24, 16, 23, 20, 24, 18
Offset: 1

Views

Author

Emeric Deutsch, Oct 04 2011

Keywords

Comments

The visitation length of a rooted tree is defined as the sum of the path length and the number of vertices. The path length of a rooted tree is defined as the sum of distances of all vertices to the root of the tree (see the Keijzer et al. reference).
The Matula-Goebel number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T.

Examples

			a(7)=9 because the rooted tree with Matula-Goebel number 7 is the rooted tree Y (1+2+2+4=9).
a(2^m) = 2m+1 because the rooted tree with Matula-Goebel number 2^m is a star with m edges (m+(m+1)=2m+1).

References

  • F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
  • I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
  • I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
  • M. Keijzer and J. Foster, Crossover bias in genetic programming, Lecture Notes in Computer Sciences, 4445, 2007, 33-44.
  • D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.

Links

Crossrefs

Cf. A196046, A196047.
Cf. A049084, A020639, A061775.

Programs

  • Haskell
    import Data.List (genericIndex)
a196068 n = genericIndex a196068_list (n - 1)
a196068_list = 1 : g 2 where
   g x = y : g (x + 1) where
     y | t > 0     = a196068 t + a061775 t + 1
       | otherwise = a196068 r + a196068 s - 1
       where t = a049084 x; r = a020639 x; s = x `div` r
-- Reinhard Zumkeller, Sep 03 2013
  • Maple
    with(numtheory): a := proc (n) local r, s, N: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: N := proc (n) if n = 1 then 1 elif bigomega(n) = 1 then 1+N(pi(n)) else N(r(n))+N(s(n))-1 end if end proc: if n = 1 then 1 elif bigomega(n) = 1 then a(pi(n))+N(pi(n))+1 else a(r(n))+a(s(n))-1 end if end proc: seq(a(n), n = 1 .. 80);
  • Mathematica
    r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
nn[n_] := Which[n == 1, 1, PrimeOmega[n] == 1, 1 + nn[PrimePi[n]], True, nn[r[n]] + nn[s[n]] - 1];
a[n_] := Which[n == 1, 1, PrimeOmega[n] == 1, a[PrimePi[n]] + nn[PrimePi[n]] + 1, True, a[r[n]] + a[s[n]] - 1];
Table[a[n], {n, 1, 80}] (* Jean-François Alcover, Jun 25 2024, after Maple code *)

Formula

a(1)=1; if n=prime(t) (= the t-th prime) then a(n)=a(t)+N(t)+1, where N(t) is the number of nodes of the rooted tree with Matula number t; if n=r*s (r,s>=2), then a(n)=a(r)+a(s)-1. The Maple program is based on this recursive formula.
Showing 1-2 of 2 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.