|
|
A177510
|
|
Number of compositions (p0, p1, p2, ...) of n with pi - p0 <= i and pi >= p0.
|
|
24
|
|
|
1, 1, 2, 3, 5, 8, 14, 25, 46, 87, 167, 324, 634, 1248, 2466, 4887, 9706, 19308, 38455, 76659, 152925, 305232, 609488, 1217429, 2432399, 4860881, 9715511, 19421029, 38826059, 77626471, 155211785, 310357462, 620608652, 1241046343, 2481817484, 4963191718, 9925669171, 19850186856, 39698516655, 79394037319
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(0)=1, otherwise row sums of A179748.
For n>=1 cumulative sums of A008930.
Also the number of integer compositions of n with exactly one part on or above the diagonal. For example, the a(1) = 1 through a(5) = 8 compositions are:
(1) (2) (3) (4) (5)
(11) (21) (31) (41)
(111) (112) (212)
(211) (311)
(1111) (1112)
(1121)
(2111)
(11111)
(End)
|
|
LINKS
|
|
|
FORMULA
|
G.f.: 1 + q/(1-q) * sum(n>=0, q^n * prod(k=1..n, (1-q^k)/(1-q) ) ). [Joerg Arndt, Mar 24 2014]
|
|
EXAMPLE
|
The a(7) = 25 such compositions are:
01: [ 1 1 1 1 1 1 1 ]
02: [ 1 1 1 1 1 2 ]
03: [ 1 1 1 1 2 1 ]
04: [ 1 1 1 1 3 ]
05: [ 1 1 1 2 1 1 ]
06: [ 1 1 1 2 2 ]
07: [ 1 1 1 3 1 ]
08: [ 1 1 1 4 ]
09: [ 1 1 2 1 1 1 ]
10: [ 1 1 2 1 2 ]
11: [ 1 1 2 2 1 ]
12: [ 1 1 2 3 ]
13: [ 1 1 3 1 1 ]
14: [ 1 1 3 2 ]
15: [ 1 2 1 1 1 1 ]
16: [ 1 2 1 1 2 ]
17: [ 1 2 1 2 1 ]
18: [ 1 2 1 3 ]
19: [ 1 2 2 1 1 ]
20: [ 1 2 2 2 ]
21: [ 1 2 3 1 ]
22: [ 2 2 3 ]
23: [ 2 3 2 ]
24: [ 3 4 ]
25: [ 7 ]
(End)
|
|
MAPLE
|
A179748 := proc(n, k) option remember; if k= 1 then 1; elif k> n then 0 ; else add( procname(n-i, k-1), i=1..k-1) ; end if; end proc:
|
|
MATHEMATICA
|
Clear[t, nn]; nn = 39; t[n_, 1] = 1; t[n_, k_] := t[n, k] = If[n >= k, Sum[t[n - i, k - 1], {i, 1, k - 1}], 0]; Table[Sum[t[n, k], {k, 1, n}], {n, 1, nn}] (* Mats Granvik, Jan 01 2015 *)
pdw[y_]:=Length[Select[Range[Length[y]], #<=y[[#]]&]]; Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], pdw[#]==1&]], {n, 0, 10}] (* Gus Wiseman, Mar 31 2022 *)
|
|
PROG
|
(Sage)
@CachedFunction
if n == 0: return int(k==0);
if k == 1: return int(n>=1);
return sum( T(n-i, k-1) for i in [1..k-1] );
# to display triangle A179748 including column zero = [1, 0, 0, 0, ...]:
#for n in [0..10]: print([ T(n, k) for k in [0..n] ])
def a(n): return sum( T(n, k) for k in [0..n] )
print([a(n) for n in [0..66]])
(PARI) N=66; q='q+O('q^N); Vec( 1 + q/(1-q) * sum(n=0, N, q^n * prod(k=1, n, (1-q^k)/(1-q) ) ) ) \\ Joerg Arndt, Mar 24 2014
|
|
CROSSREFS
|
Cf. A238859 (compositions with subdiagonal growth), A238876 (partitions with subdiagonal growth), A001227 (partitions into distinct parts with subdiagonal growth).
Cf. A238860 (partitions with superdiagonal growth), A238861 (compositions with superdiagonal growth), A000009 (partitions into distinct parts have superdiagonal growth by definition).
A352517 counts weak excedances of standard compositions.
Cf. A008930, A010054, A088218, A098825, A114088, A219282, A238352, A319005, A350839, A352488, A352489, A352514, A352515, A352516.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
New name and a(0) = 1 prepended, Joerg Arndt, Mar 24 2014
|
|
STATUS
|
approved
|
|
|
|