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
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.
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.
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 j
sum(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
Comments