A003238 -id:A003238 - cp's OEIS frontend

A358377 Numbers k such that the k-th standard ordered rooted tree is a generalized Bethe tree (counted by A003238).

1, 2, 3, 4, 5, 8, 9, 11, 16, 17, 32, 37, 43, 64, 128, 129, 137, 171, 256, 257, 293, 512, 529, 683, 1024, 1025, 2048, 2185, 2341, 2731, 4096, 8192, 10923, 16384, 16913, 18725, 32768, 32769, 32897, 34953, 43691, 65536, 65537, 131072, 131329, 149797, 174763

Offset: 1

Gus Wiseman, Nov 14 2022

nonn

We define the n-th standard ordered rooted tree to be obtained by taking the (n-1)-th composition in standard order (graded reverse-lexicographic, A066099) as root and replacing each part with its own standard ordered rooted tree. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.

A generalized Bethe tree is an unlabeled rooted tree where all branches directly under the same root are equal.

			The terms together with their corresponding ordered rooted trees begin:
    1: o
    2: (o)
    3: ((o))
    4: (oo)
    5: (((o)))
    8: (ooo)
    9: ((oo))
   11: ((o)(o))
   16: (oooo)
   17: ((((o))))
   32: (ooooo)
   37: (((o))((o)))
   43: ((o)(o)(o))
   64: (oooooo)
  128: (ooooooo)
  129: ((ooo))
  137: ((oo)(oo))
  171: ((o)(o)(o)(o))

Gus Wiseman, Statistics, classes, and transformations of standard compositions

These trees are counted by A003238.
The unordered version is A214577, also counted by A003238.
A000081 counts unlabeled rooted trees, ranked by A358378.
A358371 and A358372 count leaves and nodes in standard ordered rooted trees.
A358374 ranks ordered identity trees, counted by A032027.
Cf. A001263, A004111, A004249, A005043, A063895, A276625, A331490, A358373, A358375, A358376.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Select[Range[1000],FreeQ[srt[#],[_]?(!SameQ@@#&)]&]

A152434 Triangle read by rows, A051731 * (A003238 * 0^(n-k)).

Original entry on oeis.org

1, 1, 1, 1, 0, 2, 1, 1, 0, 3, 1, 0, 0, 0, 5, 1, 1, 1, 2, 0, 0, 6, 1, 0, 0, 0, 0, 0, 10, 1, 1, 0, 3, 0, 0, 0, 11, 1, 0, 2, 0, 0, 0, 0, 0, 16, 1, 1, 0, 0, 5, 0, 0, 0, 0, 19, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 26, 1, 1, 2, 3, 0, 6, 0, 0, 0, 0, 0, 27

Offset: 1

Gary W. Adamson, Dec 04 2008

Row sums = A003238(n+1)

			First few rows of the triangle =
1;
1, 1;
1, 0, 2;
1, 1, 0, 3;
1, 0, 0, 0, 5;
1, 1, 2, 0, 0, 6;
1, 0, 0, 0, 0, 0, 10;
1, 1, 0, 3, 0, 0, 0, 11;
1, 0, 2, 0, 0, 0, 0, 0, 16;
1, 1, 0, 0, 5, 0, 0, 0, 0, 19;
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 26;
1, 1, 2, 3, 0, 6, 0, 0, 0, 0, 0, 27;
...
Row 4 = (1, 1, 0, 3) = termwise products of (1, 1, 0, 1) and (1, 1, 2, 3)

A051731, A003238

Triangle read by rows, A051731 * (A003238 * 0^(n-k)). A051731 = the inverse

Mobius transform.

A002033 Number of perfect partitions of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3, 8, 1, 8, 1, 8, 3, 3, 1, 20, 2, 3, 4, 8, 1, 13, 1, 16, 3, 3, 3, 26, 1, 3, 3, 20, 1, 13, 1, 8, 8, 3, 1, 48, 2, 8, 3, 8, 1, 20, 3, 20, 3, 3, 1, 44, 1, 3, 8, 32, 3, 13, 1, 8, 3, 13, 1, 76, 1, 3, 8, 8, 3, 13, 1, 48, 8, 3, 1, 44, 3, 3, 3, 20, 1, 44, 3, 8, 3, 3, 3, 112

Offset: 0

N. J. A. Sloane

A perfect partition of n is one which contains just one partition of every number less than n when repeated parts are regarded as indistinguishable. Thus 1^n is a perfect partition for every n; and for n = 7, 4 1^3, 4 2 1, 2^3 1 and 1^7 are all perfect partitions. [Riordan]
Also number of ordered factorizations of n+1, see A074206.
Also number of gozinta chains from 1 to n (see A034776). - David W. Wilson
a(n) is the permanent of the n X n matrix with (i,j) entry = 1 if j|i+1 and = 0 otherwise. For n=3 the matrix is {{1, 1, 0}, {1, 0, 1}, {1, 1, 0}} with permanent = 2. - David Callan, Oct 19 2005
Appears to be the number of permutations that contribute to the determinant that gives the Moebius function. Verified up to a(9). - Mats Granvik, Sep 13 2008
Dirichlet inverse of A153881 (assuming offset 1). - Mats Granvik, Jan 03 2009
Equals row sums of triangle A176917. - Gary W. Adamson, Apr 28 2010
A partition is perfect iff it is complete (A126796) and knapsack (A108917). - Gus Wiseman, Jun 22 2016
a(n) is also the number of series-reduced planted achiral trees with n + 1 unlabeled leaves, where a rooted tree is series-reduced if all terminal subtrees have at least two branches, and achiral if all branches directly under any given node are equal. Also Moebius transform of A067824. - Gus Wiseman, Jul 13 2018

			n=0: 1 (the empty partition)
n=1: 1 (1)
n=2: 1 (11)
n=3: 2 (21, 111)
n=4: 1 (1111)
n=5: 3 (311, 221, 11111)
n=6: 1 (111111)
n=7: 4 (4111, 421, 2221, 1111111)
From _Gus Wiseman_, Jul 13 2018: (Start)
The a(11) = 8 series-reduced planted achiral trees with 12 unlabeled leaves:
  (oooooooooooo)
  ((oooooo)(oooooo))
  ((oooo)(oooo)(oooo))
  ((ooo)(ooo)(ooo)(ooo))
  ((oo)(oo)(oo)(oo)(oo)(oo))
  (((ooo)(ooo))((ooo)(ooo)))
  (((oo)(oo)(oo))((oo)(oo)(oo)))
  (((oo)(oo))((oo)(oo))((oo)(oo)))
(End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.
R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.
D. E. Knuth, The Art of Computer Programming, Pre-Fasc. 3b, Sect. 7.2.1.5, no. 67, p. 25.
P. A. MacMahon, The theory of perfect partitions and the compositions of multipartite numbers, Messenger Math., 20 (1891), 103-119.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 123-124.
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..9999
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
HoKyu Lee, Double perfect partitions, Discrete Math., 306 (2006), 519-525.
Paul Pollack, On the parity of the number of multiplicative partitions and related problems, Proc. Amer. Math. Soc. 140 (2012), 3793-3803.
J. Riordan, Letter to N. J. A. Sloane, Dec. 1970
Eric Weisstein's World of Mathematics, Perfect Partition
Eric Weisstein's World of Mathematics, Dirichlet Series Generating Function
Index entries for "core" sequences

Same as A074206, up to the offset and initial term there.
Cf. A001055, A050324.
a(A002110)=A000670.
Cf. A000123, A100529, A117621.
Cf. A176917.
For parity see A008966.
Cf. A126796, A108917.
Cf. A001678, A003238, A067824, A167865, A214577, A289078, A292504, A316782.

a := array(1..150): for k from 1 to 150 do a[k] := 0 od: a[1] := 1: for j from 2 to 150 do for m from 1 to j-1 do if j mod m = 0 then a[j] := a[j]+a[m] fi: od: od: for k from 1 to 150 do printf(`%d,`,a[k]) od: # James Sellers, Dec 07 2000
# alternative
A002033 := proc(n)
    option remember;
    local a;
    if n <= 2 then
        return 1;
    else
        a := 0 ;
        for i from 0 to n-1 do
            if modp(n+1,i+1) = 0 then
                a := a+procname(i);
            end if;
        end do:
    end if;
    a ;
end proc: # R. J. Mathar, May 25 2017

a[0] = 1; a[1] = 1; a[n_] := a[n] = a /@ Most[Divisors[n]] // Total; a /@ Range[96]  (* Jean-François Alcover, Apr 06 2011, updated Sep 23 2014. NOTE: This produces A074206(n) = a(n-1). - M. F. Hasler, Oct 12 2018 *)

A002033(n) = if(n,sumdiv(n+1,i,if(i<=n,A002033(i-1))),1) \\ Michael B. Porter, Nov 01 2009, corrected by M. F. Hasler, Oct 12 2018

from functools import lru_cache
from sympy import divisors
@lru_cache(maxsize=None)
def A002033(n):
    if n <= 1:
        return 1
    return sum(A002033(i-1) for i in divisors(n+1,generator=True) if i <= n) # Chai Wah Wu, Jan 12 2022

From David Wasserman, Nov 14 2006: (Start)
a(n-1) = Sum_{i|d, i < n} a(i-1).
a(p^k-1) = 2^(k-1).
a(n-1) = A067824(n)/2 for n > 1.
a(A122408(n)-1) = A122408(n)/2. (End)
a(A025487(n)-1) = A050324(n). - R. J. Mathar, May 26 2017
a(n) = (A253249(n+1)+1)/4, n > 0. - Geoffrey Critzer, Aug 19 2020

Edited by M. F. Hasler, Oct 12 2018

A032741 a(0) = 0; for n > 0, a(n) = number of proper divisors of n (divisors of n which are less than n).

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 3, 1, 3, 2, 3, 1, 5, 1, 3, 3, 4, 1, 5, 1, 5, 3, 3, 1, 7, 2, 3, 3, 5, 1, 7, 1, 5, 3, 3, 3, 8, 1, 3, 3, 7, 1, 7, 1, 5, 5, 3, 1, 9, 2, 5, 3, 5, 1, 7, 3, 7, 3, 3, 1, 11, 1, 3, 5, 6, 3, 7, 1, 5, 3, 7, 1, 11, 1, 3, 5, 5, 3, 7, 1, 9, 4, 3, 1, 11, 3, 3, 3, 7, 1, 11, 3, 5, 3, 3, 3, 11, 1, 5, 5

Offset: 0

Patrick De Geest, May 15 1998

Number of d < n which divide n.
Call an integer k between 1 and n a "semi-divisor" of n if n leaves a remainder of 1 when divided by k, i.e., n == 1 (mod k). a(n) gives the number of semi-divisors of n+1. - Joseph L. Pe, Sep 11 2002
a(n+1) is also the number of k, 0 <= k <= n-1, such that C(n,k) divides C(n,k+1). - Benoit Cloitre, Oct 17 2002
a(n+1) is also the number of factors of the n-th degree polynomial x^n + x^(n-1) + x^(n-2) + ... + x^2 + x + 1. Example: 1 + x + x^2 + x^3 = (1+x)(1+x^2) implies a(4)=2.
a(n) is also the number of factors of the n-th Fibonacci polynomial. - T. D. Noe, Mar 09 2006
Number of partitions of n into 2 parts with the second dividing the first. - Franklin T. Adams-Watters, Sep 20 2006
Number of partitions of n+1 into exactly one q and at least one q+1. Example: a(12)=5; indeed, we have 13 = 7 + 6 = 5 + 4 + 4 = 4 + 3 + 3 + 3 = 3 + 2 + 2 + 2 + 2 + 2 = 2 + 11*1.
Differences of A002541. - George Beck, Feb 12 2012
For n > 1: number of ones in row n+1 of triangle A051778. - Reinhard Zumkeller, Dec 03 2014
For n > 0, a(n) is the number of strong divisors of n. - Omar E. Pol, May 03 2015
a(n) is also the number of factors of the (n-1)-th degree polynomial ((x+1)^n-1)/x. Example: for n=6, ((x+1)^6-1)/x = x^5 + 6*x^4 + 15*x^3 + 20*x^2 + 15*x + 6 = (2+x)(1+x+x^2)(3+3x+x^2) implies a(6)=3. - Federico Provvedi, Oct 09 2018
Consider the polynomial P(n,z) = Sum_{i=1..q} d(i)*z^(i-1) where d(1), d(2), ..., d(q) are are the q ordered divisors of n. The sequence lists the numbers of zeros of P(n,z) strictly inside the unit circle. - Michel Lagneau, Apr 06 2025

			a(6) = 3 since the proper divisors of 6 are 1, 2, 3.

André Weil, Number Theory, An approach through history, From Hammurapi to Legendre, Birkhäuser, 1984, page 5.

T. D. Noe, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Proper divisors.

Column 2 of A122934.
Cf. A003238, A001065, A027749, A027751 (list of proper divisors).
Cf. A001620, A039653, A051778, A070824, A091818.

Concatenation([0],List([1..100],n->Tau(n)-1)); # Muniru A Asiru, Oct 09 2018

a032741 n = if n == 0 then 0 else a000005 n - 1
-- Reinhard Zumkeller, Jul 31 2014

A032741 := proc(n)
    if n = 0 then
        0 ;
    else
        numtheory[tau](n)-1 ;
    end if;
end proc: # R. J. Mathar, Feb 03 2013

Prepend[DivisorSigma[0, Range[99]]-1, 0] (* Jayanta Basu, May 25 2013 *)

PARI
```
a(n) = if(n<1,0,numdiv(n)-1)
```

{a(n)=polcoeff(2*sum(m=1,n\2+1,sumdiv(m,d,log(1-x^(m/d) +x*O(x^n) )^(2*d)/(2*d)!)), n)} \\ Paul D. Hanna, Aug 21 2014

from sympy import divisor_count
def A032741(n): return divisor_count(n)-1 if n else 0 # Chai Wah Wu, Mar 14 2023

a(n) = tau(n)-1 = A000005(n)-1. Cf. A039653.
G.f.: Sum_{n>=1} x^(2*n)/(1-x^n). - Michael Somos, Apr 29 2003
G.f.: Sum_{i>=1} (1-x^i+x^(2*i))/(1-x^i). - Jon Perry, Jul 03 2004
a(n) = Sum_{k=1..floor(n/2)} A051731(n-k,k). - Reinhard Zumkeller, Nov 01 2009
G.f.: 2*Sum_{n>=1} Sum_{d|n} log(1 - x^(n/d))^(2*d) / (2*d)!. - Paul D. Hanna, Aug 21 2014
Dirichlet g.f.: zeta(s)*(zeta(s)-1). - Geoffrey Critzer, Dec 06 2014
a(n) = Sum_{k=1..n-1} binomial((n-1) mod k, k-1). - Wesley Ivan Hurt, Sep 26 2016
a(n) = Sum_{i=1..n-1} floor(n/i)-floor((n-1)/i). - Wesley Ivan Hurt, Nov 15 2017
a(n) = Sum_{i=1..n-1} 1-sign(i mod (n-i)). - Wesley Ivan Hurt, Sep 27 2018
Sum_{k=1..n} a(k) ~ n*log(n) + 2*(gamma - 1)*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 27 2022

Typos in definition corrected by Omar E. Pol, Dec 13 2008

A067824 a(1) = 1; for n > 1, a(n) = 1 + Sum_{0 < d < n, d|n} a(d).

Original entry on oeis.org

1, 2, 2, 4, 2, 6, 2, 8, 4, 6, 2, 16, 2, 6, 6, 16, 2, 16, 2, 16, 6, 6, 2, 40, 4, 6, 8, 16, 2, 26, 2, 32, 6, 6, 6, 52, 2, 6, 6, 40, 2, 26, 2, 16, 16, 6, 2, 96, 4, 16, 6, 16, 2, 40, 6, 40, 6, 6, 2, 88, 2, 6, 16, 64, 6, 26, 2, 16, 6, 26, 2, 152, 2, 6, 16, 16, 6, 26, 2, 96, 16, 6, 2, 88, 6, 6, 6, 40, 2, 88, 6, 16, 6, 6, 6, 224, 2, 16, 16, 52

Offset: 1

Reinhard Zumkeller, Feb 08 2002

nonn

By a result of Karhumaki and Lifshits, this is also the number of polynomials p(x) with coefficients in {0,1} that divide x^n-1 and such that (x^n-1)/ {(x-1)p(x)} has all coefficients in {0,1}.
The number of tiles of a discrete interval of length n (an interval of Z). - Eric H. Rivals (rivals(AT)lirmm.fr), Mar 13 2007
Bodini and Rivals proved this is the number of tiles of a discrete interval of length n and also is the number (A107067) of polynomials p(x) with coefficients in {0,1} that divide x^n-1 and such that (x^n-1)/ {(x-1)p(x)} has all coefficients in {0,1} (Bodini, Rivals, 2006). This structure of such tiles is also known as Krasner's factorization (Krasner and Ranulac, 1937). The proof also gives an algorithm to recognize if a set is a tile in optimal time and in this case, to compute the smallest interval it can tile (Bodini, Rivals, 2006). - Eric H. Rivals (rivals(AT)lirmm.fr), Mar 13 2007
Number of lone-child-avoiding rooted achiral (or generalized Bethe) trees with positive integer leaves summing to n, where a rooted tree is lone-child-avoiding if all terminal subtrees have at least two branches, and achiral if all branches directly under any given node are equal. For example, the a(6) = 6 trees are 6, (111111), (222), ((11)(11)(11)), (33), ((111)(111)). - Gus Wiseman, Jul 13 2018. Updated Aug 22 2020.
From Gus Wiseman, Aug 20 2020: (Start)
Also the number of strict chains of divisors starting with n. For example, the a(n) chains for n = 1, 2, 4, 6, 8, 12 are:
  1  2    4      6      8        12
     2/1  4/1    6/1    8/1      12/1
          4/2    6/2    8/2      12/2
          4/2/1  6/3    8/4      12/3
                 6/2/1  8/2/1    12/4
                 6/3/1  8/4/1    12/6
                        8/4/2    12/2/1
                        8/4/2/1  12/3/1
                                 12/4/1
                                 12/4/2
                                 12/6/1
                                 12/6/2
                                 12/6/3
                                 12/4/2/1
                                 12/6/2/1
                                 12/6/3/1
(End)
a(n) is the number of chains including n of the divisor lattice of divisors of n, which is to say, a(n) is the number of (d_1,d_2,...,d_k) such that d_1 < d_2 < ... < d_k = n and d_i divides d_{i+1} for 1 <= i <= k-1. Using this definition, the recurrence a(n) = 1 + Sum_{0 < d < n, d|n} a(d) is evident by enumerating the preceding element of n in the chains. If we count instead the chains whose LCM of members is n, then a(1) would be 2 because the empty chain is included, and we would obtain 2*A074206(n). - Jianing Song, Aug 21 2024

			a(12) = 1 + a(6) + a(4) + a(3) + a(2) + a(1)
= 1+(1+a(3)+a(2)+a(1))+(1+a(2)+a(1))+(1+a(1))+(1+a(1))+(1)
= 1+(1+(1+a(1))+(1+a(1))+1)+(1+(1+a(1))+1)+(1+1)+(1+1)+(1)
= 1+(1+(1+1)+(1+1)+1)+(1+(1+1)+1)+(1+1)+(1+1)+(1)
= 1 + 6 + 4 + 2 + 2 + 1 = 16.

Olivier Bodini and Eric Rivals. Tiling an Interval of the Discrete Line. In M. Lewenstein and G. Valiente, editors, Proc. of the 17th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 4009 of Lecture Notes in Computer Science, pages 117-128. Springer Verlag, 2006.
Juhani Karhumaki, Yury Lifshits and Wojciech Rytter, Tiling Periodicity, in Combinatorial Pattern Matching, Lecture Notes in Computer Science, Volume 4580/2007, Springer-Verlag.

Reinhard Zumkeller, Table = of n, a(n) for n = 1..10000
Olivier Bodini and Eric Rivals, Tiling an Interval of the Discrete Line
Thomas Fink, Recursively divisible numbers, arXiv:1912.07979 [math.NT], 2019. See Table 1 p. 8.
T. M. A. Fink, Properties of the recursive divisor function and the number of ordered factorizations, arXiv:2307.09140 [math.NT], 2023.
Michael Greene and Robin Michaels, One Dimensional Tilings, Eureka (Cambridge) 54 (1996), 4-13.
G. Hajos, Sur le problème de factorisation des groupes cycliques, Acta Math. Acad. Sci. Hung., 1:189-195, 1950.
J. Karhumaki and Y. Lifshits, Tiling periodicity.
M. Krasner and B. Ranulac, Sur une propriété des polynomes de la division du cercle, Comptes Rendus Académie des Sciences Paris, 240:397-399, 1937.
Eric H. Rivals, Tiling
Index entries for sequences computed from exponents in factorization of n

Cf. A000005, A001678, A003238, A107067, A107748, A167865, A316782.
Cf. A122408 (fixed points).
Inverse Möbius transform of A074206.
A001055 counts factorizations.
A008480 counts maximal chains of divisors starting with n.
A074206 counts chains of divisors from n to 1.
A253249 counts nonempty chains of divisors.
A337070 counts chains of divisors starting with A006939(n).
A337071 counts chains of divisors starting with n!.
A337256 counts chains of divisors.
Cf. A001221, A001222, A002033, A124010, A337074, A337105, A378223, A378225 (Dirichlet inverse).

a067824 n = 1 + sum (map a067824 [d | d <- [1..n-1], mod n d == 0])
-- Reinhard Zumkeller, Oct 13 2011

a:= proc(n) option remember;
      1+add(a(d), d=numtheory[divisors](n) minus {n})
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Apr 17 2021

a[1]=1; a[n_] := a[n] = 1+Sum[If[Mod[n,d]==0, a[d], 0], {d, 1, n-1}]; Array[a,100] (* Jean-François Alcover, Apr 28 2011 *)

A=vector(100);A[1]=1; for(n=2,#A,A[n]=1+sumdiv(n,d,A[d])); A \\ Charles R Greathouse IV, Nov 20 2012

a(n) = 2*A074206(n), n>1. - Vladeta Jovovic, Jul 03 2005
a(p^k) = 2^k for primes p. - Reinhard Zumkeller, Sep 03 2006
a(n) = Sum_{d|n} A002033(d-1) = Sum_{d|n} A074206(d). - Gus Wiseman, Jul 13 2018
Dirichlet g.f.: zeta(s) / (2 - zeta(s)). - Álvar Ibeas, Dec 30 2018
G.f. A(x) satisfies: A(x) = x/(1 - x) + Sum_{k>=2} A(x^k). - Ilya Gutkovskiy, May 18 2019

Entry revised by N. J. A. Sloane, Aug 27 2006

A167865 Number of partitions of n into distinct parts greater than 1, with each part divisible by the next.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 4, 1, 3, 3, 3, 1, 5, 1, 5, 4, 3, 1, 6, 2, 5, 4, 5, 1, 9, 1, 6, 4, 4, 4, 8, 1, 6, 6, 7, 1, 11, 1, 8, 8, 4, 1, 10, 3, 10, 5, 8, 1, 11, 4, 10, 7, 6, 1, 13, 1, 10, 11, 7, 6, 15, 1, 9, 5, 11, 1, 14, 1, 9, 12, 8, 5, 15, 1, 16, 9, 8, 1, 18, 5, 12, 7, 10, 1, 21, 7, 13, 11, 5

Offset: 0

Max Alekseyev, Nov 13 2009

Number of lone-child-avoiding achiral rooted trees with n + 1 vertices, where a rooted tree is lone-child-avoiding if all terminal subtrees have at least two branches, and achiral if all branches directly under any given vertex are equal. The Matula-Goebel numbers of these trees are given by A331967. - Gus Wiseman, Feb 07 2020

			a(12) = 4: [12], [10,2], [9,3], [8,4].
a(14) = 3: [14], [12,2], [8,4,2].
a(18) = 5: [18], [16,2], [15,3], [12,6], [12,4,2].
From _Gus Wiseman_, Jul 13 2018: (Start)
The a(36) = 8 lone-child-avoiding achiral rooted trees with 37 vertices:
  (oooooooooooooooooooooooooooooooooooo)
  ((oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo))
  ((ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo))
  ((ooooo)(ooooo)(ooooo)(ooooo)(ooooo)(ooooo))
  ((oooooooo)(oooooooo)(oooooooo)(oooooooo))
  (((ooo)(ooo))((ooo)(ooo))((ooo)(ooo))((ooo)(ooo)))
  ((ooooooooooo)(ooooooooooo)(ooooooooooo))
  ((ooooooooooooooooo)(ooooooooooooooooo))
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Cf. A001678, A067824, A122651, A167439, A167865, A167866, A184998, A316782.
The semi-achiral version is A320268.
Matula-Goebel numbers of these trees are A331967.
The semi-lone-child-avoiding version is A331991.
Achiral rooted trees are counted by A003238.
Cf. A000081, A000669, A289079, A320222, A331912, A331933, A331936, A331992.

with(numtheory):
a:= proc(n) option remember;
      `if`(n=0, 1, add(a((n-d)/d), d=divisors(n) minus{1}))
    end:
seq(a(n), n=0..200);  # Alois P. Heinz, Mar 28 2011

a[0] = 1; a[n_] := a[n] = DivisorSum[n, a[(n-#)/#]&, #>1&]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 07 2015 *)

{ A167865(n) = if(n==0,return(1)); sumdiv(n,d, if(d>1, A167865((n-d)\d) ) ) }

a(0) = 1 and for n>=1, a(n) = Sum_{d|n, d>1} a((n-d)/d).

G.f. A(x) satisfies: A(x) = 1 + x^2*A(x^2) + x^3*A(x^3) + x^4*A(x^4) + ... - Ilya Gutkovskiy, May 09 2019

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 6, 8, 4, 1, 0, 1, 9, 18, 14, 5, 1, 0, 1, 12, 35, 39, 21, 6, 1, 0, 1, 16, 62, 97, 72, 30, 7, 1, 0, 1, 20, 103, 212, 214, 120, 40, 8, 1, 0, 1, 25, 161, 429, 563, 416, 185, 52, 9, 1, 0, 1, 30, 241, 804, 1344, 1268, 732, 270, 65, 10, 1, 0

Offset: 1

Christian G. Bower, May 09 2000

Harary denotes the g.f. as P(x, y) on page 33 "... , and let P(x,y) = Sum Sum P_{nm} x^ny^m where P_{nm} is the number of planted trees with n points and m endpoints, in which again the plant has not been counted either as a point or as an endpoint." - Michael Somos, Nov 02 2014

			From _Joerg Arndt_, Aug 18 2014: (Start)
Triangle starts:
01: 1
02: 1    0
03: 1    1    0
04: 1    2    1    0
05: 1    4    3    1    0
06: 1    6    8    4    1    0
07: 1    9   18   14    5    1    0
08: 1   12   35   39   21    6    1    0
09: 1   16   62   97   72   30    7    1    0
10: 1   20  103  212  214  120   40    8    1    0
11: 1   25  161  429  563  416  185   52    9    1    0
12: 1   30  241  804 1344 1268  732  270   65   10    1    0
13: 1   36  348 1427 2958 3499 2544 1203  378   80   11    1    0
...
The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
:     1:  [ 0 1 2 3 4 ]   1
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]   2
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]   2
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]   2
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]   3
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]   3
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]   2
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]   3
:  O--o--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 ]   4
:  O--o
:  .--o
:  .--o
:  .--o
:
This gives [1, 4, 3, 1, 0], row n=5 of the triangle.
(End)
G.f. = x*(y + x*y + x^2*(y + y^2) + x^3*(y + 2*y^2 + y^3) + x^4*(y + 4*y^2 + 3*x^3 + y^4) + ...).

F. Harary, Recent results on graphical enumeration, pp. 29-36 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees

Row sums give A000081.
Columns 2 through 12: A002620(n-1), A055278-A055287.
Cf. A055288, A055289, A055290.
Cf. A001190, A003238, A004111, A055327, A214575, A290689, A298422, A298426, A301342, A301343, A301344, A301345.

rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
Table[Length[Select[rut[n],Count[#,{},{-2}]===k&]],{n,13},{k,n}] (* Gus Wiseman, Mar 19 2018 *)

{T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*(y - 1  + exp( sum(i=1, j, 1/i * subst( subst( A + x * O(x^(j\i)), x, x^i), y, y^i) ) ))); polcoeff( polcoeff(A, n), k))}; /* Michael Somos, Aug 24 2015 */

G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.
G.f. satisfies A(x, y) = x*y - x + x * exp(Sum_{i>0} A(x^i, y^i) / i). [Harary, p. 34, equation (10)]. - Michael Somos, Nov 02 2014
Sum_k T(n, k) = A000081(n). - Michael Somos, Aug 24 2015

A047968 a(n) = Sum_{d|n} p(d), where p(d) = A000041 = number of partitions of d.

Original entry on oeis.org

1, 3, 4, 8, 8, 17, 16, 30, 34, 52, 57, 99, 102, 153, 187, 261, 298, 432, 491, 684, 811, 1061, 1256, 1696, 1966, 2540, 3044, 3876, 4566, 5846, 6843, 8610, 10203, 12610, 14906, 18491, 21638, 26508, 31290, 38044, 44584, 54133, 63262, 76241

Offset: 1

N. J. A. Sloane, Dec 11 1999

nonn

Inverse Moebius transform of A000041.
Row sums of triangle A137587. - Gary W. Adamson, Jan 27 2008
Row sums of triangle A168021. - Omar E. Pol, Nov 20 2009
Row sums of triangle A168017. Row sums of triangle A168018. - Omar E. Pol, Nov 25 2009
Sum of the partition numbers of the divisors of n. - Omar E. Pol, Feb 25 2014
Conjecture: for n > 6, a(n) is strictly increasing. - Franklin T. Adams-Watters, Apr 19 2014
Number of constant multiset partitions of multisets spanning an initial interval of positive integers with multiplicities an integer partition of n. - Gus Wiseman, Sep 16 2018

			For n = 10 the divisors of 10 are 1, 2, 5, 10, hence the partition numbers of the divisors of 10 are 1, 2, 7, 42, so a(10) = 1 + 2 + 7 + 42 = 52. - _Omar E. Pol_, Feb 26 2014
From _Gus Wiseman_, Sep 16 2018: (Start)
The a(6) = 17 constant multiset partitions:
  (111111)  (111)(111)    (11)(11)(11)  (1)(1)(1)(1)(1)(1)
  (111222)  (12)(12)(12)
  (111122)  (112)(112)
  (112233)  (123)(123)
  (111112)
  (111123)
  (111223)
  (111234)
  (112234)
  (112345)
  (123456)
(End)

T. D. Noe, Table of n, a(n) for n=1..1000
N. J. A. Sloane, Transforms

Cf. A000041, A000837, A047966, A055893, A137587, A003606 (Euler transform).

Cf. A002033, A003238, A018783, A034729, A052409, A078392, A100953, A319162.

with(combinat): with(numtheory): a := proc(n) c := 0: l := sort(convert(divisors(n), list)): for i from 1 to nops(l) do c := c+numbpart(l[i]) od: RETURN(c): end: for j from 1 to 60 do printf(`%d, `, a(j)) od: # Zerinvary Lajos, Apr 14 2007

a[n_] := Sum[ PartitionsP[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 44}] (* Jean-François Alcover, Oct 03 2013 *)

G.f.: Sum_{k>0} (-1+1/Product_{i>0} (1-z^(k*i))). - Vladeta Jovovic, Jun 22 2003
G.f.: sum(n>0,A000041(n)*x^n/(1-x^n)). - Mircea Merca, Feb 24 2014.
a(n) = A168111(n) + A000041(n). - Omar E. Pol, Feb 26 2014
a(n) = Sum_{y is a partition of n} A000005(GCD(y)). - Gus Wiseman, Sep 16 2018

A303362 Number of strict integer partitions of n with pairwise indivisible parts.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 3, 4, 5, 4, 6, 7, 7, 9, 11, 12, 13, 15, 17, 20, 23, 25, 27, 32, 35, 40, 45, 50, 55, 58, 67, 78, 84, 95, 101, 113, 124, 137, 153, 169, 180, 198, 219, 242, 268, 291, 319, 342, 374, 412, 450, 492, 535, 573, 632, 685, 746, 813, 868, 944

Offset: 1

Gus Wiseman, Apr 22 2018

nonn

			The a(14) = 7 strict integer partitions are (14), (11,3), (10,4), (9,5), (8,6), (7,5,2), (7,4,3).

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..450, (terms up to a(250) from Andrew Howroyd)

Cf. A000009, A000837, A003238, A006126, A051424, A259936, A275307, A281116, A285572, A285573, A290103, A293606, A293993, A303364.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Select[Tuples[#,2],UnsameQ@@#&&Divisible@@#&]==={}&]],{n,60}]

lista(nn)={local(Cache=Map());
  my(excl=vector(nn, n, sumdiv(n, d, 2^(n-d))));
  my(a(n, m=n, b=0)=
     if(n==0, 1,
        while(m>n || bittest(b,0), m--; b>>=1);
        my(hk=[n, m, b], z);
        if(!mapisdefined(Cache, hk, &z),
          z = if(m, self()(n, m-1, b>>1) + self()(n-m, m, bitor(b, excl[m])), 0);
          mapput(Cache, hk, z)); z));
   for(n=1, nn, print1(a(n), ", "))
} \\ Andrew Howroyd, Nov 02 2019

A032305 Number of rooted trees where any 2 subtrees extending from the same node have a different number of nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 12, 25, 51, 111, 240, 533, 1181, 2671, 6014, 13795, 31480, 72905, 168361, 393077, 914784, 2150810, 5040953, 11914240, 28089793, 66702160, 158013093, 376777192, 896262811, 2144279852, 5120176632, 12286984432, 29428496034, 70815501209

Offset: 1

Christian G. Bower

nonn

			The a(6) = 6 fully unbalanced trees: (((((o))))), (((o(o)))), ((o((o)))), (o(((o)))), (o(o(o))), ((o)((o))). - _Gus Wiseman_, Jan 10 2018

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Gus Wiseman, Illustration of the first 8 terms of A032305.
Index entries for sequences related to rooted trees

Cf. A000081, A001678, A003238, A004111, A213920, A273873, A290689, A291443, A297571.

Column k=1 of A318753.

A:= proc(n) if n<=1 then x else convert(series(x* (product(1+ coeff(A(n-1), x,i)*x^i, i=1..n-1)), x=0, n+1), polynom) fi end: a:= n-> coeff(A(n), x,n): seq(a(n), n=1..31);  # Alois P. Heinz, Aug 22 2008
# second Maple program:
g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(`if`(j=0, 1, g((i-1)$2))*g(n-i*j, i-1), j=0..min(1, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=1..35);  # Alois P. Heinz, Mar 04 2013

nn=30;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0 == Series[f[x]-x Product[1+a[i]x^i,{i,1,nn}],{x,0,nn}],x];Table[a[n],{n,1,nn}]/.sol  (* Geoffrey Critzer, Nov 17 2012 *)
allnim[n_]:=If[n===1,{{}},Join@@Function[c,Select[Union[Sort/@Tuples[allnim/@c]],UnsameQ@@(Count[#,_List,{0,Infinity}]&/@#)&]]/@IntegerPartitions[n-1]];
Table[Length[allnim[n]],{n,15}] (* Gus Wiseman, Jan 10 2018 *)
g[n_, i_] := g[n, i] = If[n == 0, 1, If[i < 1, 0,
     Sum[If[j == 0, 1, g[i-1, i-1]]*g[n-i*j, i-1], {j, 0, Min[1, n/i]}]]];
a[n_] := g[n-1, n-1];
Array[a, 35] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)

a(n)=polcoeff(x*prod(i=1,n-1,1+a(i)*x^i)+x*O(x^n),n)

Shifts left under "EFK" (unordered, size, unlabeled) transform.
G.f.: A(x) = x*Product_{n>=1} (1+a(n)*x^n) = Sum_{n>=1} a(n)*x^n. - Paul D. Hanna, Apr 07 2004
Lim_{n->infinity} a(n)^(1/n) = 2.5119824... - Vaclav Kotesovec, Nov 20 2019
G.f.: x * exp(Sum_{n>=1} Sum_{k>=1} (-1)^(k+1) * a(n)^k * x^(n*k) / k). - Ilya Gutkovskiy, Jun 30 2021

cp's OEIS Frontend

A358377 Numbers k such that the k-th standard ordered rooted tree is a generalized Bethe tree (counted by A003238).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A152434 Triangle read by rows, A051731 * (A003238 * 0^(n-k)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A002033 Number of perfect partitions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A032741 a(0) = 0; for n > 0, a(n) = number of proper divisors of n (divisors of n which are less than n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A067824 a(1) = 1; for n > 1, a(n) = 1 + Sum_{0 < d < n, d|n} a(d).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A167865 Number of partitions of n into distinct parts greater than 1, with each part divisible by the next.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple