OFFSET
0,3
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)
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
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
EXAMPLE
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)
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 j<nr and r[j]>sum(r[k], k=j+1..nr) do j:=j+1; od; # gives A040039
#while j<nr and r[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 *)
PROG
(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 */
(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 */
(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
CROSSREFS
Cf. A000123.
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.
A342098 counts partitions with all adjacent parts x > 2y.
A342337 counts partitions with all adjacent parts x = y or x = 2y.
KEYWORD
nonn,easy
AUTHOR
STATUS
approved