A177510 Number of compositions (p0, p1, p2, ...) of n with pi - p0 <= i and pi >= p0.

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

Offset: 0

Author

Mats Granvik, Dec 11 2010

Keywords

• nonn

Comments

a(0)=1, otherwise row sums of A179748.

For n>=1 cumulative sums of A008930.

a(n) is proportional to A048651*A000079. The error (a(n)-A048651*A000079) divided by sequence A186425 tends to the golden ratio A001622. This can be seen when using about 1000 decimals of the constant A048651 = 0.2887880950866024212... - [Mats Granvik, Jan 01 2015]

From Gus Wiseman, Mar 31 2022: (Start)

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)

Examples

			From _Joerg Arndt_, Mar 24 2014: (Start)
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)
		

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).

The version for partitions is A001477, strong A002620.

The version for permutations is A057427, strong A000295.

The opposite version is A238874, first column of A352522.

The version for fixed points is A240736, nonfixed A352520.

The strong version is A351983, column k=1 of A352524.

This is column k = 1 of A352525.

A238349 counts compositions by fixed points, first col A238351.

A352517 counts weak excedances of standard compositions.

Cf. A008930, A010054, A088218, A098825, A114088, A219282, A238352, A319005, A350839, A352488, A352489, A352514, A352515, A352516.

Programs

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:
A177510 := proc(n) add(A179748(n,k),k=1..n) ;end proc:
seq(A177510(n),n=1..20) ; # R. J. Mathar, Dec 14 2010

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 *)

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

Sage

@CachedFunction
def T(n, k): # A179748
    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]])
# Joerg Arndt, Mar 24 2014

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]

Extensions

New name and a(0) = 1 prepended, Joerg Arndt, Mar 24 2014