A001192 -id:A001192 - cp's OEIS frontend

A290689 Number of transitive rooted trees with n nodes.

1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 88, 143, 229, 370, 592, 955, 1527, 2457, 3929, 6304, 10081

Offset: 1

Gus Wiseman, Oct 19 2017

A rooted tree is transitive if every proper terminal subtree is also a branch of the root. First differs from A206139 at a(13) = 143.

Regarding the notation, a rooted tree is a finite multiset of rooted trees. For example, the rooted tree (o(o)(oo)) is short for {{},{{}},{{},{}}}. Each "o" is a leaf. Each pair of parentheses corresponds to a non-leaf node (such as the root). Its contents "(...)" represent a branch. - Gus Wiseman, Nov 16 2024

			The a(7) = 8 7-node transitive rooted trees are: (o(oooo)), (oo(ooo)), (o(o)((o))), (o(o)(oo)), (ooo(oo)), (oo(o)(o)), (oooo(o)), (oooooo).

Robert P. P. McKone, The transitive rooted trees with n=1 to n=22 nodes.

The restriction to identity trees (A004111) is A279861, ranks A290760.
These trees are ranked by A290822.
The anti-transitive version is A306844, ranks A324758.
The totally transitive case is A318185 (by leaves A318187), ranks A318186.
A version for integer partitions is A324753, for subsets A324736.
The ordered version is A358453, ranks A358457, undirected A358454.
Cf. A000081, A001192, A001678, A324770, A324969, A325705, A358455, A358460.

nn=18;
rtall[n_]:=If[n===1,{{}},Module[{cas},Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])]]];
Table[Length[Select[rtall[n],Complement[Union@@#,#]==={}&]],{n,nn}]

a(20) from Robert Price, Sep 13 2018

a(21)-a(22) from Robert P. P. McKone, Dec 16 2023

A290760 Matula-Goebel numbers of transitive rooted identity trees (or transitive finitary sets).

Original entry on oeis.org

1, 2, 6, 30, 78, 330, 390, 870, 1410, 3198, 3390, 4290, 7878, 9570, 10230, 11310, 13026, 15510, 15990, 18330, 26070, 30966, 37290, 39390, 40890, 44070, 45210, 65130, 84810, 94830, 98310, 104610, 122070, 124410, 132990, 154830, 159330, 175890, 198330, 201630

Offset: 1

Gus Wiseman, Oct 19 2017

nonn

A rooted tree is transitive if every terminal subtree is a branch of the root. A finitary set is transitive if every element is also a subset.

			Let o = {}. The sequence of transitive finitary sets begins:
1     o
2     {o}
6     {o,{o}}
30    {o,{o},{{o}}}
78    {o,{o},{o,{o}}}
330   {o,{o},{{o}},{{{o}}}}
390   {o,{o},{{o}},{o,{o}}}
870   {o,{o},{{o}},{o,{{o}}}}
1410  {o,{o},{{o}},{{o},{{o}}}}
3198  {o,{o},{o,{o}},{{o,{o}}}}
3390  {o,{o},{{o}},{o,{o},{{o}}}}
4290  {o,{o},{{o}},{{{o}}},{o,{o}}}
7878  {o,{o},{o,{o}},{o,{o,{o}}}}
9570  {o,{o},{{o}},{{{o}}},{o,{{o}}}}
10230 {o,{o},{{o}},{{{o}}},{{{{o}}}}}
11310 {o,{o},{{o}},{o,{o}},{o,{{o}}}}
13026 {o,{o},{o,{o}},{{o},{o,{o}}}}
15510 {o,{o},{{o}},{{{o}}},{{o},{{o}}}}
15990 {o,{o},{{o}},{o,{o}},{{o,{o}}}}
18330 {o,{o},{{o}},{o,{o}},{{o},{{o}}}}

Cf. A000081, A001192, A004111, A007097, A076146, A276625, A279861, A290689, A290822.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
finitaryQ[n_]:=finitaryQ[n]=Or[n===1,With[{m=primeMS[n]},{UnsameQ@@m,finitaryQ/@m}]/.List->And];
subprimes[n_]:=If[n===1,{},Union@@Cases[FactorInteger[n],{p_,_}:>FactorInteger[PrimePi[p]][[All,1]]]];
transitaryQ[n_]:=Divisible[n,Times@@subprimes[n]];
nn=100000;Fold[Select,Range[nn],{finitaryQ,transitaryQ}]

A279861 Number of transitive finitary sets with n brackets. Number of transitive rooted identity trees with n nodes.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 2, 1, 2, 2, 2, 5, 4, 6, 8, 10, 14, 23, 26, 34, 46, 64, 81, 115, 158, 199, 277, 376, 505, 684, 934, 1241, 1711, 2300, 3123, 4236, 5763, 7814, 10647, 14456, 19662

Offset: 1

Gus Wiseman, Dec 21 2016

nonn

A finitary set is transitive if every element is also a subset. Transitive sets are also called full sets.

			Sequence of transitive finitary sets begins:
1  ()
2  (())
4  (()(()))
7  (()(())((())))
8  (()(())(()(())))
11 (()(())((()))(((()))))
   (()(())((()))(()(())))
12 (()(())((()))(()((()))))
13 (()(())((()))((())((()))))
   (()(())(()(()))((()(()))))
14 (()(())((()))(()(())((()))))
   (()(())(()(()))(()(()(()))))
15 (()(())((()))(((())))(()(())))
   (()(())(()(()))((())(()(()))))
16 (()(())((()))(((())))((((())))))
   (()(())((()))(((())))(()((()))))
   (()(())((()))(()(()))(()((()))))
   (()(())((()))(()(()))((()(()))))
   (()(())(()(()))(()(())(()(()))))
17 (()(())((()))(((())))(()(((())))))
   (()(())((()))(((())))((())((()))))
   (()(())((()))(()(()))(()(()(()))))
   (()(())((()))(()(()))((())((()))))
18 (()(())((()))(((())))((())(((())))))
   (()(())((()))(((())))(()(())((()))))
   (()(())((()))(()(()))((())(()(()))))
   (()(())((()))(()(()))(()(())((()))))
   (()(())((()))((()((()))))(()((()))))
   (()(())((()))(()((())))((())((()))))

Wikipedia, Transitive set
Gus Wiseman, Transitive rooted identity trees example n=23

Cf. A001192, A004111, A061773, A279614, A276625, A279065, A279863.

transfins[n_]:=transfins[n]=If[n===1,{{}},Select[Union@@FixedPointList[Complement[Union@@Function[fin,Cases[Complement[Subsets[fin],fin],sub_:>With[{nov=Sort[Append[fin,sub]]},nov/;Count[nov,_List,{0,Infinity}]<=n]]]/@#,#]&,Array[transfins,n-1,1,Union]],Count[#,_List,{0,Infinity}]===n&]];
Table[Length[transfins[n]],{n,20}]

A137156 Matrix inverse of triangle A137153(n,k) = C(2^k+n-k-1, n-k), read by rows.

Original entry on oeis.org

1, -1, 1, 1, -2, 1, -2, 5, -4, 1, 9, -24, 22, -8, 1, -88, 239, -228, 92, -16, 1, 1802, -4920, 4749, -1976, 376, -32, 1, -75598, 206727, -200240, 84086, -16432, 1520, -64, 1, 6421599, -17568408, 17034964, -7173240, 1413084, -133984, 6112, -128, 1

Offset: 0

Paul D. Hanna, Jan 24 2008

Unsigned column 0 = A001192, number of full sets of size n.

			Triangle begins:
        1;
       -1,         1;
        1,        -2,        1;
       -2,         5,       -4,        1;
        9,       -24,       22,       -8,       1;
      -88,       239,     -228,       92,     -16,       1;
     1802,     -4920,     4749,    -1976,     376,     -32,    1;
   -75598,    206727,  -200240,    84086,  -16432,    1520,  -64,    1;
  6421599, -17568408, 17034964, -7173240, 1413084, -133984, 6112, -128, 1;
  ...

Cf. A137153 (matrix inverse); unsigned columns: A001192, A137157, A137158, A137159; unsigned row sums: A137160.

/* As matrix inverse of A137153: */
{T(n,k) = local(M=matrix(n+1,n+1,r,c,if(r>=c,binomial(2^(c-1)+r-c-1,r-c)))); if(n

/* Using the g.f.: */
{T(n,k) = if(n

G.f. of column k: 1 = Sum_{n>=0} T(n+k,k)*x^n/(1-x)^(2^(n+k)).

A137157 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1+x)^(22^n).

Original entry on oeis.org

1, 2, 5, 24, 239, 4920, 206727, 17568408, 3003763243, 1030272816360, 707851744149198, 973425618916674288, 2678332881795756783639, 14741522294008025924154864, 162290544340043699103996962253, 3573515596966915773419766367302288, 157376160486791180710467411977740266927

Offset: 0

Paul D. Hanna, Jan 24 2008

nonn

Equals unsigned column 1 of triangle A137156.

Cf. A137156; A001192, A137158, A137159, A137160.

{a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+x+x*O(x^n))^(2^(k+1)) ), n)}

a(15)-a(16) from Alois P. Heinz, Jan 04 2023

A137158 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1+x)^(42^n).

Original entry on oeis.org

1, 4, 22, 228, 4749, 200240, 17034964, 2913479848, 999402129243, 686662003846640, 944294243796543974, 2598186366278914473948, 14300408328085246335179009, 157434326611214704329370130880

Offset: 0

Paul D. Hanna, Jan 24 2008

nonn

Equals unsigned column 2 of triangle A137156.

Cf. A137156; A001192, A137157, A137159, A137160.

{a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+x+x*O(x^n))^(2^(k+2)) ), n)}

A137159 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1+x)^(82^n).

Original entry on oeis.org

1, 8, 92, 1976, 84086, 7173240, 1227862380, 421296930984, 289484024512093, 398106386971472608, 1095381029276651137560, 6028986377761538637043792, 66373632185586959347740452492, 1461497816340787260620205149915824

Offset: 0

Paul D. Hanna, Jan 24 2008

nonn

Equals unsigned column 3 of triangle A137156.

Cf. A137156; A001192, A137157, A137158, A137160.

{a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+x+x*O(x^n))^(2^(k+3)) ), n)}

A137160 G.f.: 1 = Sum_{n>=0} a(n)x^n(1-x)/(1+x)^(2^n).

Original entry on oeis.org

1, 2, 4, 12, 64, 664, 13856, 584668, 49751520, 8509625760, 2919099754336, 2005648412219832, 2758163973596156000, 7588978611071894509464, 41769719229784446295570112, 459846172005153447271276789620

Offset: 0

Paul D. Hanna, Jan 24 2008

nonn

Equals the unsigned row sums of triangle A137156.

Cf. A137156; A001192, A137157, A137158, A137159.

{a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k*(1-x)/(1+x+x*O(x^n))^(2^k) ), n)}

A182162 Triangle read by rows: number of extensional acyclic digraphs on n labeled nodes with k sources.

Original entry on oeis.org

1, 2, 12, 192, 24, 8160, 2400, 898560, 384480, 14400, 245145600, 126040320, 9777600, 50400, 159035627520, 90043269120, 9660672000, 179222400, 80640, 237882053283840, 141969202744320, 17961178152960, 547498828800, 2586608640, 802369403419852800

Offset: 1

N. J. A. Sloane, Apr 15 2012

			Triangle begins:
          1;
          2;
         12;
        192,        24;
       8160,      2400;
     898560,    384480,   14400;
  245145600, 126040320, 9777600, 50400;
  ...

S. Wagner, Asymptotic enumeration of extensional acyclic digraphs, in Proceedings of the SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12).

Row sums give A182161. First column is A182163. Row lengths are A182220.

A001192 := proc(n) option remember: if(n=0)then return 1: fi: return add((-1)^(n-k-1)*binomial(2^k-k,n-k)*procname(k), k=0..n-1); end: A182162 := proc(n,l) local vl: vl := add((-1)^(k-l)*binomial(n,k)*binomial(k,l)*binomial(2^(n-k)-n+k,k)*k!*(n-k)!*A001192(n-k), k=l..n): if(vl = 0)then return NULL: fi: return vl: end: for n from 1 to 10 do seq(A182162(n,l), l=1..n); od; # Nathaniel Johnston, Apr 18 2012

A001192[n_] := A001192[n] = If[n == 0, 1, Sum[(-1)^(n - k - 1)*Binomial[2^k - k, n - k]*A001192[k], {k, 0, n - 1}]];
A182162[n_, l_] := Module[{vl}, vl = Sum[(-1)^(k - l)* Binomial[n, k]*Binomial[k, l]*Binomial[2^(n - k) - n + k, k]*k!*(n - k)!*A001192[n - k], {k, l, n}]; If[vl == 0, Nothing, vl]];
Table[A182162[n, l], {n, 1, 10}, {l, 1, n}] // Flatten (* Jean-François Alcover, Mar 09 2023, after Nathaniel Johnston *)

a(15)-a(25) from Nathaniel Johnston, Apr 18 2012

A172400 G.f.: 1/(1-x) = (1-xy) Sum_{k>=0} Sum_{n>=k} T(n,k)x^ny^k/(1+x)^(2^n-2^k).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 6, 3, 1, 1, 32, 16, 5, 1, 1, 332, 166, 51, 9, 1, 1, 6928, 3464, 1059, 181, 17, 1, 1, 292334, 146167, 44620, 7557, 681, 33, 1, 1, 24875760, 12437880, 3795202, 641035, 57097, 2641, 65, 1, 1, 4254812880, 2127406440, 649054326, 109540639

Offset: 0

Paul D. Hanna, Feb 01 2010

			Triangle begins:
1;
1, 1;
2, 1, 1;
6, 3, 1, 1;
32, 16, 5, 1, 1;
332, 166, 51, 9, 1, 1;
6928, 3464, 1059, 181, 17, 1, 1;
292334, 146167, 44620, 7557, 681, 33, 1, 1;
24875760, 12437880, 3795202, 641035, 57097, 2641, 65, 1, 1;
4254812880, 2127406440, 649054326, 109540639, 9723237, 443921, 10401, 129, 1, 1; ...
Matrix inverse of this triangle begins:
1;
-1,1;
-1,-1,1;
-2,-2,-1,1;
-9,-9,-4,-1,1;
-88,-88,-38,-8,-1,1;
-1802,-1802,-772,-156,-16,-1,1;
-75598,-75598,-32313,-6456,-632,-32,-1,1; ...
in which unsigned column 0 = A001192, number of full sets of size n.

Cf. A001192, columns: A172401, A172402, A172403.

{T(n,k)=if(n==k,1,polcoeff(-(1-x)*sum(m=0,n-k-1,T(m+k,k)*x^m/(1+x +x*O(x^n))^(2^(m+k)-2^k)),n-k))}

{T(n,k)=local(M,N); M=matrix(n+1,n+1,r,c,if(r>=c,polcoeff(1/(1-x+O(x^(r-c+1)))^1*(1+x)^(2^(r-1)-2^(c-1)),r-c))); N=matrix(n+1,n+1,r,c,if(r>=c,polcoeff(1/(1-x+O(x^(r-c+1)))^2*(1+x)^(2^(r-1)-2^(c-1)),r-c))); (M^-1*N)[n+1,k+1]}

Unsigned column 0 of matrix inverse forms A001192, which is the number of full sets of size n.

cp's OEIS Frontend

A290689 Number of transitive rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A290760 Matula-Goebel numbers of transitive rooted identity trees (or transitive finitary sets).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A279861 Number of transitive finitary sets with n brackets. Number of transitive rooted identity trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A137156 Matrix inverse of triangle A137153(n,k) = C(2^k+n-k-1, n-k), read by rows.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

Formula

A137157 G.f.: 1 = Sum_{n>=0} a(n)*x^n/(1+x)^(2*2^n).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A137158 G.f.: 1 = Sum_{n>=0} a(n)*x^n/(1+x)^(4*2^n).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A137159 G.f.: 1 = Sum_{n>=0} a(n)*x^n/(1+x)^(8*2^n).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A137160 G.f.: 1 = Sum_{n>=0} a(n)*x^n*(1-x)/(1+x)^(2^n).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A182162 Triangle read by rows: number of extensional acyclic digraphs on n labeled nodes with k sources.

Views

Author

Keywords

Examples

A137157 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1+x)^(22^n).

A137158 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1+x)^(42^n).

A137159 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1+x)^(82^n).

A137160 G.f.: 1 = Sum_{n>=0} a(n)x^n(1-x)/(1+x)^(2^n).

A172400 G.f.: 1/(1-x) = (1-xy) Sum_{k>=0} Sum_{n>=k} T(n,k)x^ny^k/(1+x)^(2^n-2^k).