cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A040039 #69 Jul 08 2023 23:05:56
%S A040039 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,
%T A040039 70,70,83,83,101,101,119,119,142,142,165,165,195,195,225,225,262,262,
%U A040039 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
%N A040039 First differences of A033485; also A033485 with terms repeated.
%C A040039 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
%C A040039 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.
%C A040039 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
%C A040039 From _Gus Wiseman_, Apr 06 2021: (Start)
%C A040039 This sequence counts both of the following essentially equivalent things:
%C A040039 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:
%C A040039   {1}  {2}  {3}    {4}    {5}    {6}    {7}      {8}      {9}
%C A040039             {1,3}  {1,4}  {1,5}  {1,6}  {1,7}    {1,8}    {1,9}
%C A040039                           {2,5}  {2,6}  {2,7}    {2,8}    {2,9}
%C A040039                                         {3,7}    {3,8}    {3,9}
%C A040039                                         {1,3,7}  {1,3,8}  {4,9}
%C A040039                                                           {1,3,9}
%C A040039                                                           {1,4,9}
%C A040039 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).
%C A040039 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:
%C A040039   1  11  21   211   221    2211    421      4211      4221
%C A040039          111  1111  2111   21111   2221     22211     22221
%C A040039                     11111  111111  22111    221111    42111
%C A040039                                    211111   2111111   222111
%C A040039                                    1111111  11111111  2211111
%C A040039                                                       21111111
%C A040039                                                       111111111
%C A040039 (End)
%H A040039 Seiichi Manyama, <a href="/A040039/b040039.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..500 from Joerg Arndt)
%H A040039 Christine Bessenrodt, Jorn B. Olsson, and James A. Sellers, <a href="http://arxiv.org/abs/1107.1156">Unique path partitions: Characterization and Congruences</a>, arXiv:1107.1156 [math.CO], 2011-2012.
%H A040039 J. Jordan and R. Southwell, <a href="http://dx.doi.org/10.4236/am.2010.15045">Further Properties of Reproducing Graphs</a>, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013
%F A040039 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]
%F A040039 From _Joerg Arndt_, Oct 02 2013: (Start)
%F A040039 G.f.: sum(k>=1, x^(2^k-1) / prod(j=0..k-1, 1-x^(2^k) ) ) [Bessenrodt/Olsson/Sellers].
%F A040039 G.f.: 1/(2*x^2) * ( 1/prod(k>=0, 1 - x^(2^k) ) - (1 + x) ).
%F A040039 a(n) = 1/2 * A018819(n+2).
%F A040039 (End)
%F A040039 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
%F A040039 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
%e A040039 From _Joerg Arndt_, Dec 17 2012: (Start)
%e A040039 The a(19-1)=30 strongly decreasing partitions of 19 are (in lexicographic order)
%e A040039 [ 1]    [ 10 5 3 1 ]
%e A040039 [ 2]    [ 10 5 4 ]
%e A040039 [ 3]    [ 10 6 2 1 ]
%e A040039 [ 4]    [ 10 6 3 ]
%e A040039 [ 5]    [ 10 7 2 ]
%e A040039 [ 6]    [ 10 8 1 ]
%e A040039 [ 7]    [ 10 9 ]
%e A040039 [ 8]    [ 11 5 2 1 ]
%e A040039 [ 9]    [ 11 5 3 ]
%e A040039 [10]    [ 11 6 2 ]
%e A040039 [11]    [ 11 7 1 ]
%e A040039 [12]    [ 11 8 ]
%e A040039 [13]    [ 12 4 2 1 ]
%e A040039 [14]    [ 12 4 3 ]
%e A040039 [15]    [ 12 5 2 ]
%e A040039 [16]    [ 12 6 1 ]
%e A040039 [17]    [ 12 7 ]
%e A040039 [18]    [ 13 4 2 ]
%e A040039 [19]    [ 13 5 1 ]
%e A040039 [20]    [ 13 6 ]
%e A040039 [21]    [ 14 3 2 ]
%e A040039 [22]    [ 14 4 1 ]
%e A040039 [23]    [ 14 5 ]
%e A040039 [24]    [ 15 3 1 ]
%e A040039 [25]    [ 15 4 ]
%e A040039 [26]    [ 16 2 1 ]
%e A040039 [27]    [ 16 3 ]
%e A040039 [28]    [ 17 2 ]
%e A040039 [29]    [ 18 1 ]
%e A040039 [30]    [ 19 ]
%e A040039 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.
%e A040039 (End)
%e A040039 From _Gus Wiseman_, Oct 08 2018: (Start)
%e A040039 The a(-1) = 1 through a(4) = 3 semichiral binary rooted trees:
%e A040039   o  (oo)  (o(oo))  ((oo)(oo))  (o((oo)(oo)))  ((o(oo))(o(oo)))
%e A040039                     (o(o(oo)))  (o(o(o(oo))))  (o(o((oo)(oo))))
%e A040039                                                (o(o(o(o(oo)))))
%e A040039 (End)
%p A040039 # For example, the five partitions of 4, written in nonincreasing order, are
%p A040039 # [1,1,1,1], [2,1,1], [2,2], [3,1], [4].
%p A040039 # Only the last two satisfy the condition, and a(3)=2.
%p A040039 # The Maple program below verifies this for small values of n.
%p A040039 with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
%p A040039 for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
%p A040039 for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
%p A040039 while j<nr and r[j]>sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
%p A040039 #while j<nr and r[j]>= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
%p A040039 if j=nr then t:=t+1;fi od; a[n]:=t; od;
%p A040039 # John McKay
%t A040039 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];
%t A040039 a[n_] := T[n+1, 1];
%t A040039 Table[a[n], {n, 0, 80}] (* _Jean-François Alcover_, Jul 27 2018, after _Vladimir Kruchinin_ *)
%t A040039 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 *)
%o A040039 (PARI) /* compute as "A033485 with terms repeated" */
%o A040039 b(n) = if(n<2, 1, b(floor(n/2))+b(n-1));  /* A033485 */
%o A040039 a(n) = b(n\2+1); /* note different offsets */
%o A040039 for(n=0,99, print1(a(n),", ")); /* _Joerg Arndt_, Jan 21 2011 */
%o A040039 (Maxima)
%o A040039 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);
%o A040039 makelist(T(n+1,1),n,0,40); /* _Vladimir Kruchinin_, Mar 19 2015 */
%o A040039 (Python)
%o A040039 from itertools import islice
%o A040039 from collections import deque
%o A040039 def A040039_gen(): # generator of terms
%o A040039     aqueue, f, b, a = deque([2]), True, 1, 2
%o A040039     yield from (1, 1, 2, 2)
%o A040039     while True:
%o A040039         a += b
%o A040039         yield from (a, a)
%o A040039         aqueue.append(a)
%o A040039         if f: b = aqueue.popleft()
%o A040039         f = not f
%o A040039 A040039_list = list(islice(A040039_gen(),40)) # _Chai Wah Wu_, Jun 07 2022
%Y A040039 Cf. A000123.
%Y A040039 Cf. A088567, A089054.
%Y A040039 Cf. A001190, A003238, A111299, A292050, A317712, A320222, A320230, A320271.
%Y A040039 The equal case is A001511.
%Y A040039 The reflected version is A045690.
%Y A040039 The unequal (anti-run) version is A045691.
%Y A040039 A000929 counts partitions with all adjacent parts x >= 2y.
%Y A040039 A002843 counts compositions with all adjacent parts x <= 2y.
%Y A040039 A018819 counts partitions into powers of 2.
%Y A040039 A154402 counts partitions with all adjacent parts x = 2y.
%Y A040039 A274199 counts compositions with all adjacent parts x < 2y.
%Y A040039 A342094 counts partitions with all adjacent parts x <= 2y (strict: A342095).
%Y A040039 A342096 counts partitions without adjacent x >= 2y (strict: A342097).
%Y A040039 A342098 counts partitions with all adjacent parts x > 2y.
%Y A040039 A342337 counts partitions with all adjacent parts x = y or x = 2y.
%Y A040039 Cf. A000009, A003114, A003242, A224957, A342191, A342330.
%K A040039 nonn,easy
%O A040039 0,3
%A A040039 _N. J. A. Sloane_ and _J. H. Conway_