A279861 -id:A279861 - cp's OEIS frontend

A001192 Number of full sets of size n.

1, 1, 1, 2, 9, 88, 1802, 75598, 6421599, 1097780312, 376516036188, 258683018091900, 355735062429124915, 978786413996934006272, 5387230452634185460127166, 59308424712939278997978128490, 1305926814154452720947815884466579

Offset: 0

N. J. A. Sloane

A set x is full if every element of x is also a subset of x.
Equals the subpartitions of Eulerian numbers (A000295(n)=2^n-n-1); see A115728 for the definition of subpartitions of a partition. - Paul D. Hanna, Jul 03 2006
Also number of transitive rooted identity trees with n branches. - Gus Wiseman, Dec 21 2016

			Examples of full sets are 0 := {}, 1 := {0}, 2 := {1,0}, 3a := {2,1,0}, 3b := { {1}, 1, 0}, 4a := { 3a, 2, 1, 0 }.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 123, Problem 20.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..50
Bojan Bašić, Paul Ellis, Dana C. Ernst, Danijela Popović, and Nándor Sieben, Categories of impartial rulegraphs and gamegraphs, arXiv:2312.00650 [math.CO], 2023. See p. 20.
Alberto Casagrande, Carla Piazza, and Alberto Policriti, Is hyper-extensionality preservable under deletions of graph elements?, Elec. Notes Theor. Comp. Sci. (2016) Vol. 322, 103-118.
Richard Peddicord, The number of full sets with n elements, Proc. Amer. Math. Soc., 13 (1962), 825-828.
John Riordan, Letter to N. J. A. Sloane, Jul. 1970
Alexandru Ioan Tomescu, Sets as Graphs, Ph. D. Thesis, Università degli Studi di Udine, Dipartimento di Matematica e Informatica, Dottorato di Ricerca in Informatica, Dec. 2011.
Stephan Wagner, Asymptotic enumeration of extensional acyclic digraphs, in Proceedings of the SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12).
Gus Wiseman, Transitive rooted identity trees with n=5 branches

Cf. A000295, A004111, A115728, A182161, A279861, A279863.

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: seq(A001192(n), n=0..16); # Nathaniel Johnston, Apr 18 2012

max = 16; f[x_] := Sum[a[n]*(x^n/(1+x)^2^n), {n, 0, max}] - 1; cc = CoefficientList[ Series[f[x], {x, 0, max}], x]; Table[a[n], {n, 0, max}] /. First[ Solve[ Thread[cc == 0]]] (* Jean-François Alcover, Nov 02 2011, after Vladeta Jovovic *)

{a(n)=polcoeff(x^n-sum(k=0, n-1, a(k)*x^k*(1-x+x*O(x^n))^(2^k-k-1) ), n)} \\ Paul D. Hanna, Jul 03 2006

1 = Sum_{n>=0} a(n)*x^n/(1+x)^(2^n). E.g., 1 = 1/(1+x) + 1*x/(1+x)^2 + 1*x^2/(1+x)^4 + 2*x^3/(1+x)^8 + 9*x^4/(1+x)^16 + 88*x^5/(1+x)^32 + 1802*x^6/(1+x)^64 + ... . - Vladeta Jovovic, May 26 2005
Equivalently, a(n) = (-1)^n*C(2^n+n-1, n) - Sum_{k=0..n-1} a(k)*(-1)^(n-k)*C(2^n+2^k+n-k-1, n-k). - Paul D. Hanna, May 26 2005
G.f.: 1/(1-x) = Sum_{n>=0} a(n)*x^n*(1-x)^(2^n-n-1) = 1*(1-x)^0 + 1*x*(1-x)^0 + 1*x^2*(1-x)^1 + 2*x^3*(1-x)^4 + 9*x^3*(1-x)^11 + ... + a(n)*x^n*(1-x)^(2^n-n-1) + ... . - Paul D. Hanna, Jul 03 2006

More terms from Ryan Propper, Jun 13 2005

A324768 Number of fully anti-transitive rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 3, 6, 11, 27, 60, 152, 376, 968, 2492, 6549, 17259, 46000, 123214, 332304, 900406, 2451999, 6703925

Offset: 1

Gus Wiseman, Mar 17 2019

An unlabeled rooted tree is fully anti-transitive if no proper terminal subtree of any branch of the root is a branch of the root.

			The a(1) = 1 through a(6) = 11 rooted trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))
                 (((o)))  (((oo)))   (((ooo)))
                          ((o)(o))   ((o)(oo))
                          ((o(o)))   ((o(oo)))
                          ((((o))))  ((oo(o)))
                                     ((((oo))))
                                     (((o)(o)))
                                     (((o(o))))
                                     ((o((o))))
                                     (((((o)))))

Cf. A000081, A279861, A290689, A304360, A306844, A318185.
Cf. A324695, A324751, A324756, A324758, A324763, A324765, A324769, A324770.
Cf. A324838, A324840, A324844, A324846.

rtall[n_]:=Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])];
Table[Length[Select[rtall[n],Intersection[Union@@Rest[FixedPointList[Union@@#&,#]],#]=={}&]],{n,10}]

a(17)-a(20) from Jinyuan Wang, Jun 20 2020

A324738 Number of subsets of {1...n} containing no element > 1 whose prime indices all belong to the subset.

Original entry on oeis.org

1, 2, 3, 5, 8, 13, 26, 42, 72, 120, 232, 376, 752, 1128, 2256, 4512, 8256, 13632, 27264, 42048, 82944, 158976, 313344, 497664, 995328, 1700352, 3350016, 5815296, 11630592, 17491968, 34983936, 56954880, 108933120, 210788352, 418258944, 804667392, 1609334784

Offset: 0

Gus Wiseman, Mar 13 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The a(0) = 1 through a(6) = 26 subsets:
  {}  {}   {}   {}     {}     {}       {}
      {1}  {1}  {1}    {1}    {1}      {1}
           {2}  {2}    {2}    {2}      {2}
                {3}    {3}    {3}      {3}
                {1,3}  {4}    {4}      {4}
                       {1,3}  {5}      {5}
                       {2,4}  {1,3}    {6}
                       {3,4}  {1,5}    {1,3}
                              {2,4}    {1,5}
                              {2,5}    {1,6}
                              {3,4}    {2,4}
                              {4,5}    {2,5}
                              {2,4,5}  {2,6}
                                       {3,4}
                                       {3,6}
                                       {4,5}
                                       {4,6}
                                       {5,6}
                                       {1,3,6}
                                       {1,5,6}
                                       {2,4,5}
                                       {2,4,6}
                                       {2,5,6}
                                       {3,4,6}
                                       {4,5,6}
                                       {2,4,5,6}

Andrew Howroyd, Table of n, a(n) for n = 0..100

The maximal case is A324744. The case of subsets of {2...n} is A324739. The strict integer partition version is A324749. The integer partition version is A324754. The Heinz number version is A324759. An infinite version is A324694.
Cf. A000720, A001221, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A279861, A290689, A290822, A304360, A306844.
Cf. A324695, A324736, A324741, A324750, A324755, A324760.

Table[Length[Select[Subsets[Range[n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]],{n,0,10}]

pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,if(k==1, 1, pset(k))), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(bitnegimply(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019

Terms a(21) and beyond from Andrew Howroyd, Aug 16 2019

A324843 Number of unlabeled rooted trees with n nodes where the branches of any branch of any terminal subtree form a submultiset of the branches of the same subtree.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 4, 8, 9, 15, 17, 31, 35, 57, 70, 111, 136, 213, 265, 405, 517, 763, 987, 1458, 1893, 2736, 3611, 5161, 6836, 9702

Offset: 1

Gus Wiseman, Mar 18 2019

A subset of totally transitive rooted trees (A318185).

			The a(1) = 1 through a(8) = 8 rooted trees:
  o  (o)  (oo)  (ooo)   (oooo)   (ooooo)    (oooooo)    (ooooooo)
                (o(o))  (oo(o))  (oo(oo))   (ooo(oo))   (ooo(ooo))
                                 (ooo(o))   (oooo(o))   (oooo(oo))
                                 (o(o)(o))  (oo(o)(o))  (ooooo(o))
                                                        (oo(o)(oo))
                                                        (ooo(o)(o))
                                                        (o(o)(o)(o))
                                                        (o(o)(o(o)))

The Matula-Goebel numbers of these trees are given by A324842.
Cf. A000081, A279861, A290689, A290822, A318185.
Cf. A324704, A324736, A324748, A324753, A324847, A324848, A324854.

submultQ[cap_,fat_]:=And@@Function[i,Count[fat,i]>=Count[cap,i]]/@Union[List@@cap];
rallt[n_]:=Select[Union[Sort/@Join@@(Tuples[rallt/@#]&/@IntegerPartitions[n-1])],And@@Table[submultQ[b,#],{b,#}]&];
Table[Length[rallt[n]],{n,10}]

A301345 Regular triangle where T(n,k) is the number of transitive rooted trees with n nodes and k leaves.

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 1, 3, 1, 0, 0, 0, 1, 2, 4, 1, 0, 0, 0, 0, 3, 4, 5, 1, 0, 0, 0, 0, 2, 6, 6, 6, 1, 0, 0, 0, 0, 1, 6, 10, 9, 7, 1, 0, 0, 0, 0, 1, 5, 12, 16, 12, 8, 1, 0, 0, 0, 0, 0, 4, 13, 22, 23, 16, 9, 1, 0, 0, 0, 0, 0, 3, 14, 27, 36, 32, 20, 10, 1, 0, 0, 0, 0, 0, 2, 11

Offset: 1

Gus Wiseman, Mar 19 2018

			Triangle begins:
1
1   0
0   1   0
0   1   1   0
0   0   2   1   0
0   0   1   3   1   0
0   0   1   2   4   1   0
0   0   0   3   4   5   1   0
0   0   0   2   6   6   6   1   0
0   0   0   1   6  10   9   7   1   0
0   0   0   1   5  12  16  12   8   1   0
The T(9,5) = 6 transitive rooted trees: (o(o)(oo(o))), (o((oo))(oo)), (oo(o)(o(o))), (o(o)(o)(oo)), (ooo(o)((o))), (oo(o)(o)(o)).

Row sums are A290689.

Cf. A000081, A001190, A003238, A004111, A032305, A055277, A276625, A279861, A290760, A290822, A298422, A298426, A301342, A301343, A301344.

rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
trat[n_]:=Select[rut[n],Complement[Union@@#,#]==={}&];
Table[Length[Select[trat[n],Count[#,{},{-2}]===k&]],{n,15},{k,n}]

A324748 Number of strict integer partitions of n containing all prime indices of the parts.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 1, 0, 2, 1, 2, 3, 2, 2, 4, 3, 4, 3, 5, 6, 9, 8, 7, 8, 11, 12, 13, 15, 17, 22, 22, 20, 28, 31, 32, 36, 41, 43, 53, 53, 59, 70, 76, 77, 89, 99, 108, 124, 135, 139, 160, 172, 188, 209, 229, 243, 274, 298, 315, 353, 391, 417, 457, 496, 538, 588

Offset: 0

Gus Wiseman, Mar 15 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The first 15 terms count the following integer partitions.
   1: (1)
   3: (2,1)
   5: (4,1)
   6: (3,2,1)
   7: (4,2,1)
   9: (8,1)
   9: (6,2,1)
  10: (4,3,2,1)
  11: (8,2,1)
  11: (5,3,2,1)
  12: (9,2,1)
  12: (7,4,1)
  12: (6,3,2,1)
  13: (8,4,1)
  13: (6,4,2,1)
  14: (8,3,2,1)
  14: (7,4,2,1)
  15: (12,2,1)
  15: (9,3,2,1)
  15: (8,4,2,1)
  15: (5,4,3,2,1)
An example for n = 6 is (20,18,11,5,3,2,1), with prime indices:
  20: {1,1,3}
  18: {1,2,2}
  11: {5}
   5: {3}
   3: {2}
   2: {1}
   1: {}
All of these prime indices {1,2,3,5} belong to the partition, as required.

The subset version is A324736. The non-strict version is A324753. The Heinz number version is A290822. An infinite version is A324698.
Cf. A000720, A001462, A007097, A074971, A078374, A112798, A276625, A279861, A290689, A290760, A305713.
Cf. A324697, A324737, A324751.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&SubsetQ[#,PrimePi/@First/@Join@@FactorInteger/@DeleteCases[#,1]]&]],{n,0,30}]

A318186 Totally transitive numbers. Matula-Goebel numbers of totally transitive rooted trees.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 14, 16, 18, 24, 28, 32, 36, 38, 42, 48, 54, 56, 64, 72, 76, 78, 84, 96, 98, 106, 108, 112, 114, 126, 128, 144, 152, 156, 162, 168, 192, 196, 212, 216, 222, 224, 228, 234, 252, 256, 262, 266, 288, 294, 304, 312, 318, 324, 336, 342, 366, 378

Offset: 1

Gus Wiseman, Aug 20 2018

nonn

A number x is totally transitive if (1) whenever prime(y) divides x it follows that y is totally transitive and (2) if prime(y) divides x and prime(z) divides y then prime(z) also divides x.

			The sequence of all totally transitive rooted trees together with their Matula-Goebel numbers begins:
   1: o
   2: (o)
   4: (oo)
   6: (o(o))
   8: (ooo)
  12: (oo(o))
  14: (o(oo))
  16: (oooo)
  18: (o(o)(o))
  24: (ooo(o))
  28: (oo(oo))
  32: (ooooo)
  36: (oo(o)(o))
  38: (o(ooo))
  42: (o(o)(oo))
  48: (oooo(o))
  54: (o(o)(o)(o))
  56: (ooo(oo))
  64: (oooooo)
  72: (ooo(o)(o))
  76: (oo(ooo))
  78: (o(o)(o(o)))
  84: (oo(o)(oo))
  96: (ooooo(o))
  98: (o(oo)(oo))

Cf. A000081, A001678, A004111, A007097, A061775, A276625, A279861, A290689, A290760, A290822, A291636, A318185, A318187.

subprimes[n_]:=If[n==1,{},Union@@Cases[FactorInteger[n],{p_,_}:>FactorInteger[PrimePi[p]][[All,1]]]];
trmgQ[n_]:=Or[n==1,And[Divisible[n,Times@@subprimes[n]],And@@Cases[FactorInteger[n],{p_,_}:>trmgQ[PrimePi[p]]]]];
Select[Range[100],trmgQ]

A324767 Number of recursively anti-transitive rooted identity trees with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 5, 9, 17, 33, 63, 126, 254, 511, 1039, 2124, 4371, 9059, 18839, 39339, 82385, 173111, 364829, 771010, 1633313

Offset: 1

Gus Wiseman, Mar 17 2019

An unlabeled rooted tree is recursively anti-transitive if no branch of a branch of any terminal subtree is a branch of the same subtree. It is an identity tree if there are no repeated branches directly under a common root.
Also the number of finitary sets with n brackets where, at any level, no element of an element of a set is an element of the same set. For example, the a(8) = 9 finitary sets are (o = {}):
  {{{{{{{o}}}}}}}
  {{{{o,{{o}}}}}}
  {{{o,{{{o}}}}}}
  {{o,{{{{o}}}}}}
  {{{o},{{{o}}}}}
  {o,{{{{{o}}}}}}
  {o,{{o,{{o}}}}}
  {{o},{{{{o}}}}}
  {{o},{o,{{o}}}}
The Matula-Goebel numbers of these trees are given by A324766.

			The a(4) = 1 through a(8) = 9 recursively anti-transitive rooted identity trees:
  (((o)))  (o((o)))   ((o((o))))   (((o((o)))))   ((o)(o((o))))
           ((((o))))  (o(((o))))   ((o)(((o))))   (o((o((o)))))
                      (((((o)))))  ((o(((o)))))   ((((o((o))))))
                                   (o((((o)))))   (((o)(((o)))))
                                   ((((((o))))))  (((o(((o))))))
                                                  ((o)((((o)))))
                                                  ((o((((o))))))
                                                  (o(((((o))))))
                                                  (((((((o)))))))

Cf. A000081, A004111, A276625, A279861, A290689, A290760, A304360, A306844, A316500.

Cf. A324695, A324751, A324758, A324764 (non-recursive version), A324765 (non-identity version), A324766, A324770, A324839, A324840, A324844.

iallt[n_]:=Select[Union[Sort/@Join@@(Tuples[iallt/@#]&/@IntegerPartitions[n-1])],UnsameQ@@#&&Intersection[Union@@#,#]=={}&];
Table[Length[iallt[n]],{n,10}]

A324770 Number of fully anti-transitive rooted identity trees with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 13, 27, 58, 128, 286, 640, 1452, 3308, 7594, 17512, 40591, 94449, 220672

Offset: 1

Gus Wiseman, Mar 17 2019

An unlabeled rooted tree is fully anti-transitive if no proper terminal subtree of any branch of the root is a branch of the root. It is an identity tree if there are no repeated branches directly under the same root.

			The a(1) = 1 through a(7) = 6 fully anti-transitive rooted identity trees:
  o  (o)  ((o))  (((o)))  ((o(o)))   (((o(o))))   ((o(o(o))))
                          ((((o))))  ((o((o))))   ((((o(o)))))
                                     (((((o)))))  (((o)((o))))
                                                  (((o((o)))))
                                                  ((o(((o)))))
                                                  ((((((o))))))

Gus Wiseman, The a(11) = 128 fully anti-transitive rooted identity trees.

Cf. A000081, A004111, A276625, A279861, A290760, A304360, A306844.
Cf. A324695, A324751, A324763, A324764, A324765, A324767, A324769.
Cf. A324839, A324840, A324843, A324844, A324846.

idall[n_]:=If[n==1,{{}},Select[Union[Sort/@Join@@(Tuples[idall/@#]&/@IntegerPartitions[n-1])],UnsameQ@@#&]];
Table[Length[Select[idall[n],Intersection[Union@@Rest[FixedPointList[Union@@#&,#]],#]=={}&]],{n,10}]

A318229 Number of inequivalent leaf-colorings of transitive rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 5, 13, 34, 92, 255

Offset: 1

Gus Wiseman, Aug 21 2018

In a transitive rooted tree, every branch of a branch of the root is also a branch of the root.

			Inequivalent representatives of the a(5) = 13 leaf-colorings:
  (1111)  (1(11))  (11(1))
  (1112)  (1(12))  (11(2))
  (1122)  (1(22))  (12(1))
  (1123)  (1(23))  (12(3))
  (1234)

Cf. A000081, A001190, A001678, A003238, A004111, A279861, A290689, A290822, A318185, A304486.

Cf. A318226, A318227, A318228, A318230, A318231, A318234.

cp's OEIS Frontend

A001192 Number of full sets of size n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A324768 Number of fully anti-transitive rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A324738 Number of subsets of {1...n} containing no element > 1 whose prime indices all belong to the subset.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A324843 Number of unlabeled rooted trees with n nodes where the branches of any branch of any terminal subtree form a submultiset of the branches of the same subtree.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A301345 Regular triangle where T(n,k) is the number of transitive rooted trees with n nodes and k leaves.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A324748 Number of strict integer partitions of n containing all prime indices of the parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A318186 Totally transitive numbers. Matula-Goebel numbers of totally transitive rooted trees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A324767 Number of recursively anti-transitive rooted identity trees with n nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs