A040039 First differences of A033485; also A033485 with terms repeated.

1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 10, 10, 13, 13, 18, 18, 23, 23, 30, 30, 37, 37, 47, 47, 57, 57, 70, 70, 83, 83, 101, 101, 119, 119, 142, 142, 165, 165, 195, 195, 225, 225, 262, 262, 299, 299, 346, 346, 393, 393, 450, 450, 507, 507, 577, 577, 647, 647, 730, 730, 813, 813, 914, 914, 1015, 1015, 1134, 1134, 1253, 1253, 1395, 1395

Offset: 0

Author

N. J. A. Sloane and J. H. Conway

Keywords

• nonn
• easy

Comments

Apparently a(n) = number of partitions (p_1, p_2, ..., p_k) of n+1, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i > p_{i+1}+...+p_k. - John McKay (mac(AT)mathstat.concordia.ca), Mar 06 2009

Comment from John McKay confirmed in paper by Bessenrodt, Olsson, and Sellers. Such partitions are called "strongly decreasing" partitions in the paper, see the function s(n) therein.

Also the number of unlabeled binary rooted trees with 2*n + 3 nodes in which the two branches directly under any given non-leaf node are either equal or at least one of them is a leaf. - Gus Wiseman, Oct 08 2018

From Gus Wiseman, Apr 06 2021: (Start)

This sequence counts both of the following essentially equivalent things:

1. Sets of distinct positive integers with maximum n + 1 in which all adjacent elements have quotients < 1/2. For example, the a(0) = 1 through a(8) = 7 subsets are:

{1} {2} {3} {4} {5} {6} {7} {8} {9}

{1,3} {1,4} {1,5} {1,6} {1,7} {1,8} {1,9}

{2,5} {2,6} {2,7} {2,8} {2,9}

{3,7} {3,8} {3,9}

{1,3,7} {1,3,8} {4,9}

{1,3,9}

{1,4,9}

2. Sets of distinct positive integers with maximum n + 1 whose first differences are term-wise greater than their decapitation (remove the maximum). For example, the set q = {1,4,9} has first differences (3,5), which are greater than (1,4), so q is counted under a(8). On the other hand, r = {1,5,9} has first differences (4,4), which are not greater than (1,5), so r is not counted under a(8).

Also the number of partitions of n + 1 into powers of 2 covering an initial interval of powers of 2. For example, the a(0) = 1 through a(8) = 7 partitions are:

1 11 21 211 221 2211 421 4211 4221

111 1111 2111 21111 2221 22211 22221

11111 111111 22111 221111 42111

211111 2111111 222111

1111111 11111111 2211111

21111111

111111111

(End)

Examples

			From _Joerg Arndt_, Dec 17 2012: (Start)
The a(19-1)=30 strongly decreasing partitions of 19 are (in lexicographic order)
[ 1]    [ 10 5 3 1 ]
[ 2]    [ 10 5 4 ]
[ 3]    [ 10 6 2 1 ]
[ 4]    [ 10 6 3 ]
[ 5]    [ 10 7 2 ]
[ 6]    [ 10 8 1 ]
[ 7]    [ 10 9 ]
[ 8]    [ 11 5 2 1 ]
[ 9]    [ 11 5 3 ]
[10]    [ 11 6 2 ]
[11]    [ 11 7 1 ]
[12]    [ 11 8 ]
[13]    [ 12 4 2 1 ]
[14]    [ 12 4 3 ]
[15]    [ 12 5 2 ]
[16]    [ 12 6 1 ]
[17]    [ 12 7 ]
[18]    [ 13 4 2 ]
[19]    [ 13 5 1 ]
[20]    [ 13 6 ]
[21]    [ 14 3 2 ]
[22]    [ 14 4 1 ]
[23]    [ 14 5 ]
[24]    [ 15 3 1 ]
[25]    [ 15 4 ]
[26]    [ 16 2 1 ]
[27]    [ 16 3 ]
[28]    [ 17 2 ]
[29]    [ 18 1 ]
[30]    [ 19 ]
The a(20-1)=30 strongly decreasing partitions of 20 are obtained by adding 1 to the first part in each partition in the list.
(End)
From _Gus Wiseman_, Oct 08 2018: (Start)
The a(-1) = 1 through a(4) = 3 semichiral binary rooted trees:
  o  (oo)  (o(oo))  ((oo)(oo))  (o((oo)(oo)))  ((o(oo))(o(oo)))
                    (o(o(oo)))  (o(o(o(oo))))  (o(o((oo)(oo))))
                                               (o(o(o(o(oo)))))
(End)
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..500 from Joerg Arndt)
• Christine Bessenrodt, Jorn B. Olsson, and James A. Sellers, Unique path partitions: Characterization and Congruences, arXiv:1107.1156 [math.CO], 2011-2012.
• J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013

Crossrefs

Cf. A000123.

Cf. A088567, A089054.

Cf. A001190, A003238, A111299, A292050, A317712, A320222, A320230, A320271.

The equal case is A001511.

The reflected version is A045690.

The unequal (anti-run) version is A045691.

A000929 counts partitions with all adjacent parts x >= 2y.

A002843 counts compositions with all adjacent parts x <= 2y.

A018819 counts partitions into powers of 2.

A154402 counts partitions with all adjacent parts x = 2y.

A274199 counts compositions with all adjacent parts x < 2y.

A342094 counts partitions with all adjacent parts x <= 2y (strict: A342095).

A342096 counts partitions without adjacent x >= 2y (strict: A342097).

A342098 counts partitions with all adjacent parts x > 2y.

A342337 counts partitions with all adjacent parts x = y or x = 2y.

Cf. A000009, A003114, A003242, A224957, A342191, A342330.

Programs

Maple

# For example, the five partitions of 4, written in nonincreasing order, are
# [1,1,1,1], [2,1,1], [2,2], [3,1], [4].
# Only the last two satisfy the condition, and a(3)=2.
# The Maple program below verifies this for small values of n.
with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
#while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
if j=nr then t:=t+1;fi od; a[n]:=t; od;
# John McKay

Mathematica

T[n_, m_] := T[n, m] = Sum[Binomial[n-2k-1, n-2k-m] Sum[Binomial[m, i] T[k, i], {i, 1, k}], {k, 0, (n-m)/2}] + Binomial[n-1, n-m];
a[n_] := T[n+1, 1];
Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Jul 27 2018, after Vladimir Kruchinin *)
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&And@@Table[#[[i-1]]/#[[i]]<1/2,{i,2,Length[#]}]&]],{n,15}] (* Gus Wiseman, Apr 06 2021 *)

Maxima

T(n,m):=sum(binomial(n-2*k-1,n-2*k-m)*sum(binomial(m,i)*T(k,i),i,1,k),k,0,(n-m)/2)+binomial(n-1,n-m);
makelist(T(n+1,1),n,0,40); /* Vladimir Kruchinin, Mar 19 2015 */

PARI

/* compute as "A033485 with terms repeated" */
b(n) = if(n<2, 1, b(floor(n/2))+b(n-1));  /* A033485 */
a(n) = b(n\2+1); /* note different offsets */
for(n=0,99, print1(a(n),", ")); /* Joerg Arndt, Jan 21 2011 */

Python

from itertools import islice
from collections import deque
def A040039_gen(): # generator of terms
    aqueue, f, b, a = deque([2]), True, 1, 2
    yield from (1, 1, 2, 2)
    while True:
        a += b
        yield from (a, a)
        aqueue.append(a)
        if f: b = aqueue.popleft()
        f = not f
A040039_list = list(islice(A040039_gen(),40)) # Chai Wah Wu, Jun 07 2022

Formula

Let T(x) be the g.f, then T(x) = 1 + x/(1-x)*T(x^2) = 1 + x/(1-x) * ( 1 + x^2/(1-x^2) * ( 1 + x^4/(1-x^4) * ( 1 + x^8/(1-x^8) *(...) ))). [Joerg Arndt, May 11 2010]

From Joerg Arndt, Oct 02 2013: (Start)

G.f.: sum(k>=1, x^(2^k-1) / prod(j=0..k-1, 1-x^(2^k) ) ) [Bessenrodt/Olsson/Sellers].

G.f.: 1/(2*x^2) * ( 1/prod(k>=0, 1 - x^(2^k) ) - (1 + x) ).

a(n) = 1/2 * A018819(n+2).

(End)

a(n) = T(n+1,1), where T(n,m)=sum(k..0,(n-m)/2, binomial(n-2*k-1,n-2*k-m)*sum(i=1..k, binomial(m,i)*T(k,i)))+binomial(n-1,n-m). - Vladimir Kruchinin, Mar 19 2015

Using offset 1: a(1) = 1; a(n even) = a(n-1); a(n odd) = a(n-1) + a((n-1)/2). - Gus Wiseman, Oct 08 2018