A002572 -id:A002572 - cp's OEIS frontend

A339479 Number of partitions consisting of n parts, each of which is a power of 2, where one part is 1 and no part is more than twice the sum of all smaller parts.

1, 2, 5, 13, 35, 95, 259, 708, 1938, 5308, 14543, 39852, 109216, 299326, 820378, 2248484, 6162671, 16890790, 46294769, 126886206, 347774063, 953191416, 2612541157, 7160547089, 19625887013, 53791344195, 147433273080, 404090482159, 1107545909953, 3035602173663

Offset: 1

Victor S. Miller, Apr 24 2021

nonn

a(n) is the number of n-tuples of nondecreasing integers, which are the exponents of 2 in the partition, the first of which is 0 and which are "reduced". The 1-tuple (0) is reduced. If the tuple is (x(1), ..., x(n)), then it is reduced if (x(1), ..., x(n-1)) is reduced and x(n) <= ceiling(log_2(1 + Sum_{i=1..n-1} 2^x(i))). This sequence arose in analyzing the types of partitions of a positive integer into parts which are powers of 2.

			The a(2) = 2 partitions are {1,1} and {1,2}.
The a(3) = 5 partitions are {1,1,1}, {1,1,2}, {1,1,4}, {1,2,2}, {1,2,4}.
The a(4) = 13 partitions are {1,1,1,1}, {1,1,1,2}, {1,1,1,4}, {1,1,2,2}, {1,1,2,4}, {1,1,2,8}, {1,1,4,4}, {1,1,4,8}, {1,2,2,2}, {1,2,2,4}, {1,2,2,8}, {1,2,4,4}, {1,2,4,8}.

Alois P. Heinz, Table of n, a(n) for n = 1..2285

Cf. A002572, A018819, A086449, A174980, A343801.

b:= proc(n, t) option remember; `if`(n=0, 1,
     `if`(t=0, 0, b(n, iquo(t, 2))+b(n-1, t+2)))
    end:
a:= n-> b(n, 1):
seq(a(n), n=1..30);  # Alois P. Heinz, Apr 27 2021

b[n_, t_] := b[n, t] = If[n == 0, 1, If[t == 0, 0, b[n, Quotient[t, 2]] + b[n - 1, t + 2]]];
a[n_] := b[n, 1];
Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Jul 07 2021, after Alois P. Heinz *)

seq(n)={my(v=vector(n), a=vector(n)); a[1]=v[1]=1; for(n=2, n, for(j=1, n-1, v[n-(n-j)\2] += v[j]); a[n]=vecsum(v)); a} \\ Andrew Howroyd, Apr 25 2021

from functools import cache
@cache
def r339479(n, k):
    if n == 0:
        return 1
    elif k == 0:
        return r339479(n - 1, 1)
    else:
        return r339479(n - 1, k + 1) + r339479(n, k // 2)
def a339479(n): return r339479(n,0)
print([a339479(n) for n in range(1, 100)])

G.f.: x/(1 - x - B(x)) where B(x) is the g.f. of A002572.

a(n) = F(n,0) where F(0,k) = 1, F(n,0) = F(n-1,1) for n > 0 and F(n,k) = F(n-1,k+1) + F(n, floor(k/2)) for n,k > 0. In this recursion, F(n,k) gives the number of partitions with n parts where the sum of all parts smaller than the current part size being considered is between k and k+1 multiples of the part size. This function is independent of the current part size. In the case that k is zero, the only choice is to add a part of the current part size, otherwise parts of double the size are also a possibility. - Andrew Howroyd, Apr 24 2021

Terms a(19) and beyond from Andrew Howroyd, Apr 24 2021

A002844 Number of non-isentropic binary rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 5, 13, 36, 102, 296, 871, 2599, 7830, 23799, 72855, 224455, 695303, 2164491

Offset: 1

N. J. A. Sloane

From Richard Guy's 1971 letter: "[Studied by] Helen Alderson, J. H. Conway, etc. at Cambridge. These are rooted trees with two branches at each stage and if A,B,C,D (see drawing [in letter]) are further growths, then one treats (AB)(CD) as equivalent to (AC)(BD) - otherwise one distinguishes left and right. [The sequence gives] the number of equivalence classes of such trees."

R. K. Guy, personal communication.
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).

Tyler Foster, A Noncommutative Version of the Natural Numbers, arXiv:1003.2081 [math.QA], 2010. See D(n) Table 2 p. 3.
R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: front, back [Annotated scanned copy, with permission] See sequence C.
N. J. A. Sloane, Winter Fruits: New Problems from the OEIS, Dec. 2016 - Jan. 2017 (Part 1), Jan 26 2017.
N. J. A. Sloane, Winter Fruits: New Problems from the OEIS, Dec. 2016 - Jan. 2017 (slides)
Doron Zeilberger, Maple program for A002844
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Bears a superficial resemblance to A036765.

Revised by N. J. A. Sloane, Dec 15 2016
a(11)-a(14) from Doron Zeilberger, Jan 31 2017
a(15)-a(16) from Sean A. Irvine, Sep 29 2023

A014167 Partial sums of binary rooted tree numbers.

Original entry on oeis.org

1, 2, 4, 7, 12, 21, 37, 65, 115, 204, 363, 648, 1158, 2072, 3711, 6649, 11918, 21369, 38321, 68731, 123286, 221157, 396743, 711759, 1276927, 2290903, 4110101, 7373976, 13229809, 23735984, 42585539, 76404333, 137080119, 245941267, 441254017, 791673611

Offset: 1

N. J. A. Sloane

nonn

			G.f. = x + 2*x^2 + 4*x^3 + 7*x^4 + 12*x^5 + 21*x^6 + 37*x^7 + 65*x^8 + 115*x^9 + ...

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Index entries for sequences related to rooted trees

Cf. A002572.

v:= proc(c,d) option remember; if d<0 or c<0 then 0 elif d=c then 1 else add(v(i,d-c), i=1..2*c) fi end: a:= proc(n) option remember; if n=0 then 0 else a(n-1) +v(1,n) fi end: seq(a(n), n=1..40); # Alois P. Heinz, Aug 22 2008

v[c_, d_] := v[c, d] = If[d<0 || c<0, 0, If[d == c, 1, Sum[v[i, d-c], {i, 1, 2c}]]]; a[n_] := a[n] = If[n == 0, 0, a[n-1]+v[1, n]]; Table[a[n], {n, 1, 29}] (* Jean-François Alcover, Mar 03 2014, after Alois P. Heinz *)

G.f.: (B(x)-x)/(x(1-x)) where B(x) is g.f. of A002572.

A279196 Number of polynomials of the form P(x,y) = 1 + (x+y-1) * Q(x,y) such that P(1,1) = n and both polynomials P and Q have nonnegative integer coefficients.

Original entry on oeis.org

1, 1, 2, 5, 13, 36, 102, 295, 864, 2557, 7624, 22868, 68920, 208527, 632987, 1926752, 5878738, 17973523, 55050690, 168881464, 518818523, 1595878573, 4914522147, 15150038699, 46747391412, 144370209690, 446214862158, 1380161749537, 4271808447154, 13230257155092, 40999697820032

Offset: 1

N. J. A. Sloane, Dec 15 2016

nonn

Original definition did not have the requirement for Q to have nonnegative coefficients. However, this results in different terms given by A363933. We have a(n) <= A363933(n), which is strict for n >= 5. - Max Alekseyev, Jun 28 2023

In colorful terms, one can view a polynomial as a configuration made of piles of tokens located at lattice points (i>=0, j>=0). One introduces the notion of "degradation of a configuration": to degrade a configuration, choose a nonempty pile of tokens in it, say that at (i,j); remove one token from that pile; then add one token at (i+1,j) and one token at (i,j+1). This is a nondeterministic process. a(n) is the number of distinct configurations one can possibly get after (n-1) degradations of the initial configuration consisting of just one token at (0,0). In this metaphor, the P's are the resulting configurations and the Q's are records of where the tokens have been taken. - Luc Rousseau, Jun 30 2023

			From _Peter Kagey_, Feb 03 2017 (Start):
For n = 1 the a(1) = 1 solution is:
  1 = 0(x + y - 1) + 1.
For n = 2 the a(2) = 1 solution is:
  x + y = (x + y - 1) + 1.
For n = 3 the a(3) = 2 solutions are:
  xy + x + y^2 = (y + 1)(x + y - 1) + 1;
  xy + y + x^2 = (x + 1)(x + y - 1) + 1.
For n = 4 the a(4) = 5 solutions are:
  x^2 + 2xy + y^2       = (x + y + 1)(x + y - 1) + 1;
  x^2y + x^2 + xy^2 + y = (xy + x + 1)(x + y - 1) + 1;
  x^2y + xy^2 + x + y^2 = (xy + y + 1)(x + y - 1) + 1;
  xy^2 + xy + x + y^3   = (y^2 + y + 1)(x + y - 1) + 1;
  x^3 + x^2y + xy + y   = (x^2 + x + 1)(x + y - 1) + 1.
(End) [Corrected by _Luc Rousseau_, Jun 30 2023]

Luc Rousseau, Table of n, a(n) for n = 1..45
R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: front, back [Annotated scanned copy, with permission] See sequence "D".
Luc Rousseau, a Java program for A279196, by degradation.
Luc Rousseau, a Java + Prolog program for A279196, nonnegativity CLP version.
Luc Rousseau, a Prolog program for A279196, divide and conquer, memoized version.
Luc Rousseau, Illustration of the degradation process, n=1..5
N. J. A. Sloane, Winter Fruits: New Problems from OEIS, Dec. 2016 - Jan. 2017 (part 1), 2017-01-26, (discussion from 6:23-10:00).
N. J. A. Sloane, Winter Fruits: New Problems from the OEIS, Dec. 2016 - Jan. 2017 (slides)

Cf. A363933.

// See Rousseau link.
(Java + Prolog) // See Rousseau link.

Prolog
```
% See Rousseau link.
```

Definition corrected by Max Alekseyev, Jun 28 2023
a(10)-a(18) from Luc Rousseau, Jun 30 2023
a(19)-a(25) from Max Alekseyev, Jul 04 2023
a(26)-a(29) from Luc Rousseau, Jul 31 2023
a(30) from Luc Rousseau, Nov 10 2023
a(31) from Luc Rousseau, Dec 18 2023

A363933 Number of polynomials P(x,y) with nonnegative integer coefficients such that P(x,y) == 1 (mod x+y-1) and P(1,1) = n.

Original entry on oeis.org

1, 1, 2, 5, 14, 40, 119, 361, 1113, 3476, 10971, 34919, 111949, 361100, 1171130

Offset: 1

Max Alekseyev, Jun 28 2023

The definition was originally used in A279196, which however happened to additionally require the quotient Q(x,y) = (P(x,y)-1) / (x+y-1) to have nonnegative coefficients as well. The current sequence allows these coefficients be negative. Hence a(n) >= A279196(n).

Let Q_d(x,y) be the homogeneous part of Q(x,y) of degree d, and c_d = Q_d(1,1). Then c_0 = 1, c_1, ... form a sequence of nonnegative integers such that c_d <= 2*c_{d-1} and c_0 + c_1 + ... = n-1 (cf. A002572). It follows that Q(x,y) and P(x,y) have degree at most n-2 and at most n-1, respectively.

			For n = 5, this sequence but not A279196 accounts for polynomial x^3 + 3xy + y^3 = 1 + (x + y - 1) * (x^2 + y^2 - xy + x + y + 1), explaining why a(5) = 14 while A279196(5) = 13.

Cf. A279196.

A014168 Apply partial sum operator twice to binary rooted tree numbers.

Original entry on oeis.org

1, 3, 7, 14, 26, 47, 84, 149, 264, 468, 831, 1479, 2637, 4709, 8420, 15069, 26987, 48356, 86677, 155408, 278694, 499851, 896594, 1608353, 2885280, 5176183, 9286284, 16660260, 29890069, 53626053, 96211592, 172615925, 309696044, 555637311, 996891328, 1788564939

Offset: 1

N. J. A. Sloane

nonn

Cf. A002572. Partial sums of A014167, not of A173404.

G.f.: (B(x)-x)/x(1-x)^2 where B(x) is g.f. of A002572.

A014169 Apply partial sum operator thrice to binary rooted tree numbers.

Original entry on oeis.org

1, 4, 11, 25, 51, 98, 182, 331, 595, 1063, 1894, 3373, 6010, 10719, 19139, 34208, 61195, 109551, 196228, 351636, 630330, 1130181, 2026775, 3635128, 6520408, 11696591, 20982875, 37643135, 67533204

Offset: 1

N. J. A. Sloane

nonn

Index entries for sequences related to rooted trees

Cf. A002572.

G.f.: (B(x)-x)/x(1-x)^3 where B(x) is g.f. of A002572.

A014171 Apply partial sum operator 4 times to binary rooted tree numbers.

Original entry on oeis.org

1, 5, 16, 41, 92, 190, 372, 703, 1298, 2361, 4255, 7628, 13638, 24357, 43496, 77704, 138899, 248450, 444678, 796314, 1426644, 2556825, 4583600, 8218728, 14739136, 26435727, 47418602, 85061737, 152594941

Offset: 1

N. J. A. Sloane

nonn

Index entries for sequences related to rooted trees

Cf. A002572.

G.f.: (B(x)-x)/x(1-x)^4 where B(x) is g.f. of A002572.

A249018 Decimal expansion of the Flajolet-Prodinger constant 'K', a constant related to asymptotically enumerating level number sequences for binary trees.

Original entry on oeis.org

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

Offset: 0

Jean-François Alcover, Jan 12 2015

			0.254505523565319513370881770031546156046493741725...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.5 Kalmar's composition constant, p. 294.

Philippe Flajolet and Helmut Prodinger, Level number sequences for trees.

Cf. A002572, A102375.

digits = 105; m0 = 5; dm = 2; Clear[f, g, v, K]; v[c_, d_] := v[c, d] = If[d<0 || c<0, 0, If[d == c, 1, Sum[v[i, d-c], {i, 1, 2*c}]]]; H[n_] := v[1, n]; H[1] = 1; f[x_, m_] := Sum[((-1)^(j+1)*x^(2^(j+1)-2-j))/Product[1-x^(2^k-1), {k, 1, j}], {j, 1, m}] // N[#, digits]&; g[m_] := g[m] = (1/x /. FindRoot[f[x, m] == 1, {x, 5/9, 4/9, 6/9}, WorkingPrecision -> digits]); g[m0]; g[m = m0+dm]; While[RealDigits[g[m], 10, digits+5] != RealDigits[g[m-dm], 10, digits+5], m = m+dm]; nu = g[m]; K[m_] := K[m] = H[m]/nu^m; dm=100; K[m = 100]; K[m = m+dm]; While[Print[m]; RealDigits[K[m], 10, digits+5] != RealDigits[K[m-dm], 10, digits+5], m = m+dm]; RealDigits[K[m], 10, digits-5] // First

H(n) ~ K*nu^n, where H(n) is number of level number sequences associated to binary trees (Cf. A002572) and 'nu' is the constant A102375.

cp's OEIS Frontend

A339479 Number of partitions consisting of n parts, each of which is a power of 2, where one part is 1 and no part is more than twice the sum of all smaller parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A002844 Number of non-isentropic binary rooted trees with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A014167 Partial sums of binary rooted tree numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A279196 Number of polynomials of the form P(x,y) = 1 + (x+y-1) * Q(x,y) such that P(1,1) = n and both polynomials P and Q have nonnegative integer coefficients.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Prolog

Extensions

A363933 Number of polynomials P(x,y) with nonnegative integer coefficients such that P(x,y) == 1 (mod x+y-1) and P(1,1) = n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A014168 Apply partial sum operator twice to binary rooted tree numbers.

Views

Author

Keywords

Links

Crossrefs

Formula

A014169 Apply partial sum operator thrice to binary rooted tree numbers.

Views

Author

Keywords

Links

Crossrefs

Formula

A014171 Apply partial sum operator 4 times to binary rooted tree numbers.

Views

Author

Keywords

Links

Crossrefs

Formula

A249018 Decimal expansion of the Flajolet-Prodinger constant 'K', a constant related to asymptotically enumerating level number sequences for binary trees.

Views

Author

Keywords