login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A040039 First differences of A033485; also A033485 with terms repeated. 28
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 (list; graph; refs; listen; history; text; internal format)
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
A040039_list = list(islice(A040039_gen(), 40)) # Chai Wah Wu, Jun 07 2022
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.
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.
Sequence in context: A064986 A349675 A029019 * A008667 A367221 A239880
KEYWORD
nonn,easy
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)