|
| |
|
|
A079500
|
|
Number of compositions of the integer n in which the first part is >= the other parts.
|
|
43
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
In lunar arithmetic in base 2, this is the number of lunar divisors of the number 111...1 (with n 1's). E.g., 1111 has a(4) = 5 divisors (see A048888). - N. J. A. Sloane, Feb 23 2011.
Number of balanced ordered rooted trees with n non-root nodes (see A048816 for unordered balanced trees); see example. The compositions are obtained from the level sequences by identifying a length-k run of (non-root) levels [t, t+1, t+2, ..., t+k-1] with a part k. - Joerg Arndt, Jul 20 2014
|
|
|
REFERENCES
|
Arnold Knopfmacher and Neville Robbins, Compositions with parts constrained by the leading summand, Ars Combin. 76 (2005), 287-295.
|
|
|
LINKS
|
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.
|
|
|
FORMULA
|
G.f.: (1-z) * Sum_{k>=0} z^k/(1 - 2*z + z^(k+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
|
|
|
EXAMPLE
|
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)
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)
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)
|
|
|
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):
|
|
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
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
|
|
|
STATUS
|
approved
|
| |
|
|
