login
First differences of A033485; also A033485 with terms repeated.
28

%I #69 Jul 08 2023 23:05:56

%S 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 70,70,83,83,101,101,119,119,142,142,165,165,195,195,225,225,262,262,

%U 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 First differences of A033485; also A033485 with terms repeated.

%C 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 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 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 From _Gus Wiseman_, Apr 06 2021: (Start)

%C This sequence counts both of the following essentially equivalent things:

%C 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 {1} {2} {3} {4} {5} {6} {7} {8} {9}

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

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

%C {3,7} {3,8} {3,9}

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

%C {1,3,9}

%C {1,4,9}

%C 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 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 1 11 21 211 221 2211 421 4211 4221

%C 111 1111 2111 21111 2221 22211 22221

%C 11111 111111 22111 221111 42111

%C 211111 2111111 222111

%C 1111111 11111111 2211111

%C 21111111

%C 111111111

%C (End)

%H Seiichi Manyama, <a href="/A040039/b040039.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..500 from Joerg Arndt)

%H 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 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 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 From _Joerg Arndt_, Oct 02 2013: (Start)

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

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

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

%F (End)

%F 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 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 From _Joerg Arndt_, Dec 17 2012: (Start)

%e The a(19-1)=30 strongly decreasing partitions of 19 are (in lexicographic order)

%e [ 1] [ 10 5 3 1 ]

%e [ 2] [ 10 5 4 ]

%e [ 3] [ 10 6 2 1 ]

%e [ 4] [ 10 6 3 ]

%e [ 5] [ 10 7 2 ]

%e [ 6] [ 10 8 1 ]

%e [ 7] [ 10 9 ]

%e [ 8] [ 11 5 2 1 ]

%e [ 9] [ 11 5 3 ]

%e [10] [ 11 6 2 ]

%e [11] [ 11 7 1 ]

%e [12] [ 11 8 ]

%e [13] [ 12 4 2 1 ]

%e [14] [ 12 4 3 ]

%e [15] [ 12 5 2 ]

%e [16] [ 12 6 1 ]

%e [17] [ 12 7 ]

%e [18] [ 13 4 2 ]

%e [19] [ 13 5 1 ]

%e [20] [ 13 6 ]

%e [21] [ 14 3 2 ]

%e [22] [ 14 4 1 ]

%e [23] [ 14 5 ]

%e [24] [ 15 3 1 ]

%e [25] [ 15 4 ]

%e [26] [ 16 2 1 ]

%e [27] [ 16 3 ]

%e [28] [ 17 2 ]

%e [29] [ 18 1 ]

%e [30] [ 19 ]

%e 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 (End)

%e From _Gus Wiseman_, Oct 08 2018: (Start)

%e The a(-1) = 1 through a(4) = 3 semichiral binary rooted trees:

%e o (oo) (o(oo)) ((oo)(oo)) (o((oo)(oo))) ((o(oo))(o(oo)))

%e (o(o(oo))) (o(o(o(oo)))) (o(o((oo)(oo))))

%e (o(o(o(o(oo)))))

%e (End)

%p # For example, the five partitions of 4, written in nonincreasing order, are

%p # [1,1,1,1], [2,1,1], [2,2], [3,1], [4].

%p # Only the last two satisfy the condition, and a(3)=2.

%p # The Maple program below verifies this for small values of n.

%p with(combinat); N:=8; a:=array(1..N); c:=array(1..N);

%p for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;

%p for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;

%p while j<nr and r[j]>sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039

%p #while j<nr and r[j]>= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819

%p if j=nr then t:=t+1;fi od; a[n]:=t; od;

%p # John McKay

%t 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 a[n_] := T[n+1, 1];

%t Table[a[n], {n, 0, 80}] (* _Jean-François Alcover_, Jul 27 2018, after _Vladimir Kruchinin_ *)

%t 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 (PARI) /* compute as "A033485 with terms repeated" */

%o b(n) = if(n<2, 1, b(floor(n/2))+b(n-1)); /* A033485 */

%o a(n) = b(n\2+1); /* note different offsets */

%o for(n=0,99, print1(a(n),", ")); /* _Joerg Arndt_, Jan 21 2011 */

%o (Maxima)

%o 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 makelist(T(n+1,1),n,0,40); /* _Vladimir Kruchinin_, Mar 19 2015 */

%o (Python)

%o from itertools import islice

%o from collections import deque

%o def A040039_gen(): # generator of terms

%o aqueue, f, b, a = deque([2]), True, 1, 2

%o yield from (1, 1, 2, 2)

%o while True:

%o a += b

%o yield from (a, a)

%o aqueue.append(a)

%o if f: b = aqueue.popleft()

%o f = not f

%o A040039_list = list(islice(A040039_gen(),40)) # _Chai Wah Wu_, Jun 07 2022

%Y Cf. A000123.

%Y Cf. A088567, A089054.

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

%Y The equal case is A001511.

%Y The reflected version is A045690.

%Y The unequal (anti-run) version is A045691.

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

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

%Y A018819 counts partitions into powers of 2.

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

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

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

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

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

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

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

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_ and _J. H. Conway_