A079500 Number of compositions of the integer n in which the first part is >= the other parts.
1, 1, 2, 3, 5, 8, 14, 24, 43, 77, 140, 256, 472, 874, 1628, 3045, 5719, 10780, 20388, 38674, 73562, 140268, 268066, 513350, 984911, 1892875, 3643570, 7023562, 13557020, 26200182, 50691978, 98182666, 190353370, 369393466, 717457656, 1394632365, 2713061899
Offset: 0
Keywords
Examples
From _Joerg Arndt_, Dec 29 2012: (Start)
There are a(7)=24 compositions p(1)+p(2)+...+p(m)=7 such that p(k) <= p(1):
[ 1] [ 1 1 1 1 1 1 1 ]
[ 2] [ 2 1 1 1 1 1 ]
[ 3] [ 2 1 1 1 2 ]
[ 4] [ 2 1 1 2 1 ]
[ 5] [ 2 1 2 1 1 ]
[ 6] [ 2 1 2 2 ]
[ 7] [ 2 2 1 1 1 ]
[ 8] [ 2 2 1 2 ]
[ 9] [ 2 2 2 1 ]
[10] [ 3 1 1 1 1 ]
[11] [ 3 1 1 2 ]
[12] [ 3 1 2 1 ]
[13] [ 3 1 3 ]
[14] [ 3 2 1 1 ]
[15] [ 3 2 2 ]
[16] [ 3 3 1 ]
[17] [ 4 1 1 1 ]
[18] [ 4 1 2 ]
[19] [ 4 2 1 ]
[20] [ 4 3 ]
[21] [ 5 1 1 ]
[22] [ 5 2 ]
[23] [ 6 1 ]
[24] [ 7 ]
(End)
From _Joerg Arndt_, Jul 20 2014: (Start)
The a(7) = 24 balanced ordered rooted trees with 7 non-root nodes are, as level sequences (of the pre-order walk):
01: [ 0 1 1 1 1 1 1 1 ]
02: [ 0 1 2 1 2 1 2 2 ]
03: [ 0 1 2 1 2 2 1 2 ]
04: [ 0 1 2 1 2 2 2 2 ]
05: [ 0 1 2 2 1 2 1 2 ]
06: [ 0 1 2 2 1 2 2 2 ]
07: [ 0 1 2 2 2 1 2 2 ]
08: [ 0 1 2 2 2 2 1 2 ]
09: [ 0 1 2 2 2 2 2 2 ]
10: [ 0 1 2 3 1 2 3 3 ]
11: [ 0 1 2 3 2 3 2 3 ]
12: [ 0 1 2 3 2 3 3 3 ]
13: [ 0 1 2 3 3 1 2 3 ]
14: [ 0 1 2 3 3 2 3 3 ]
15: [ 0 1 2 3 3 3 2 3 ]
16: [ 0 1 2 3 3 3 3 3 ]
17: [ 0 1 2 3 4 2 3 4 ]
18: [ 0 1 2 3 4 3 4 4 ]
19: [ 0 1 2 3 4 4 3 4 ]
20: [ 0 1 2 3 4 4 4 4 ]
21: [ 0 1 2 3 4 5 4 5 ]
22: [ 0 1 2 3 4 5 5 5 ]
23: [ 0 1 2 3 4 5 6 6 ]
24: [ 0 1 2 3 4 5 6 7 ]
(End)
From _Gus Wiseman_, Oct 07 2018: (Start)
The a(0) = 1 through a(6) = 14 balanced rooted plane trees:
o (o) (oo) (ooo) (oooo) (ooooo) (oooooo)
((o)) ((oo)) ((ooo)) ((oooo)) ((ooooo))
(((o))) (((oo))) (((ooo))) (((oooo)))
((o)(o)) ((o)(oo)) ((o)(ooo))
((((o)))) ((oo)(o)) ((oo)(oo))
((((oo)))) ((ooo)(o))
(((o)(o))) ((((ooo))))
(((((o))))) (((o)(oo)))
(((oo)(o)))
((o)(o)(o))
(((((oo)))))
((((o)(o))))
(((o))((o)))
((((((o))))))
(End)
References
- Arnold Knopfmacher and Neville Robbins, Compositions with parts constrained by the leading summand, Ars Combin. 76 (2005), 287-295.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 400 terms from T. D. Noe)
- D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, arXiv:1107.1130 [math.NT], 2011. [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
- D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
- Srecko Brlek, Andrea Frosini, Simone Rinaldi, and Laurent Vuillon, Tilings by translation: enumeration by a rational language approach, The Electronic Journal of Combinatorics, vol.13, (2006).
- A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.1.
- R. Kemp, Balanced ordered trees, Random Structures Algorithms, 5 (1994), pp. 99-121.
- Index entries for sequences related to dismal (or lunar) arithmetic
Crossrefs
Programs
-
Maple
M:=101: t1:=add( (1-x)*x^k/(1-2*x+x^k), k=1..M): series(t1,x,M-1); seriestolist(%); # second Maple program: b:= proc(n, m) option remember; `if`(n=0, 1, `if`(m=0, add(b(n-j, j), j=1..n), add(b(n-j, min(n-j, m)), j=1..min(n, m)))) end: a:= n-> b(n, 0): seq(a(n), n=0..40); # Alois P. Heinz, May 01 2014 -
Mathematica
nn=36;CoefficientList[Series[Sum[x^i/(1-(x-x^(i+1))/(1-x)),{i,0,nn}],{x,0,nn}],x] (* Geoffrey Critzer, Mar 12 2013 *) b[n_, m_] := b[n, m] = If[n==0, 1, If[m==0, Sum[b[n-j, j], {j, 1, n}], Sum[ b[n-j, Min[n-j, m]], {j, 1, Min[n, m]}]]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 23 2015, after Alois P. Heinz *)
Formula
G.f.: (1-z) * Sum_{k>=0} z^k/(1 - 2*z + z^(k+1)).
a(n) = A048888(n) - 1.
G.f.: -((1 + x^2 + 1/(x-1))/x)*( 1 + x*(x-1)^3*(1-x+x^3)/( Q(0) - x*(x-1)^3*(1-x+x^3)) ), where Q(k) = (x+1)*(2*x-1)*(1-x)^2 + x^(k+2)*(x+x^2+x^3-2*x^4-1 - x^(k+3) + x^(k+5)) - x*(-1+2*x-x^(k+3))*(1-2*x+x^2+x^(k+4)-x^(k+5))*(-1+4*x-5*x^2+2*x^3 - x^(k+2)- x^(k+5) + 2*x^(k+3) - x^(2*k+5) + x^(2*k+6))/Q(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Dec 14 2013
a(n) = Sum_{j=1..n} F(j, n+1-j), where F(n,k) is the n-th k-generalized Fibonacci number A092921(k,n). - Gregory L. Simay, Aug 21 2022
Extensions
Offset corrected by N. J. A. Sloane, Feb 23 2011
More terms from N. J. A. Sloane, Feb 24 2011
Further edits (required in order to clarify the definition - is the first part >= the rest. or only > the rest? Answer: the former; for the latter, see A007059) by N. J. A. Sloane, May 08 2011
Comments