%I #53 May 15 2022 11:37:55
%S 1,1,2,3,5,8,14,25,46,87,167,324,634,1248,2466,4887,9706,19308,38455,
%T 76659,152925,305232,609488,1217429,2432399,4860881,9715511,19421029,
%U 38826059,77626471,155211785,310357462,620608652,1241046343,2481817484,4963191718,9925669171,19850186856,39698516655,79394037319
%N Number of compositions (p0, p1, p2, ...) of n with pi - p0 <= i and pi >= p0.
%C a(0)=1, otherwise row sums of A179748.
%C For n>=1 cumulative sums of A008930.
%C 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]
%C From _Gus Wiseman_, Mar 31 2022: (Start)
%C 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:
%C (1) (2) (3) (4) (5)
%C (11) (21) (31) (41)
%C (111) (112) (212)
%C (211) (311)
%C (1111) (1112)
%C (1121)
%C (2111)
%C (11111)
%C (End)
%F 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]
%e From _Joerg Arndt_, Mar 24 2014: (Start)
%e The a(7) = 25 such compositions are:
%e 01: [ 1 1 1 1 1 1 1 ]
%e 02: [ 1 1 1 1 1 2 ]
%e 03: [ 1 1 1 1 2 1 ]
%e 04: [ 1 1 1 1 3 ]
%e 05: [ 1 1 1 2 1 1 ]
%e 06: [ 1 1 1 2 2 ]
%e 07: [ 1 1 1 3 1 ]
%e 08: [ 1 1 1 4 ]
%e 09: [ 1 1 2 1 1 1 ]
%e 10: [ 1 1 2 1 2 ]
%e 11: [ 1 1 2 2 1 ]
%e 12: [ 1 1 2 3 ]
%e 13: [ 1 1 3 1 1 ]
%e 14: [ 1 1 3 2 ]
%e 15: [ 1 2 1 1 1 1 ]
%e 16: [ 1 2 1 1 2 ]
%e 17: [ 1 2 1 2 1 ]
%e 18: [ 1 2 1 3 ]
%e 19: [ 1 2 2 1 1 ]
%e 20: [ 1 2 2 2 ]
%e 21: [ 1 2 3 1 ]
%e 22: [ 2 2 3 ]
%e 23: [ 2 3 2 ]
%e 24: [ 3 4 ]
%e 25: [ 7 ]
%e (End)
%p 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:
%p A177510 := proc(n) add(A179748(n,k),k=1..n) ;end proc:
%p seq(A177510(n),n=1..20) ; # _R. J. Mathar_, Dec 14 2010
%t 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 *)
%t 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 *)
%o (Sage)
%o @CachedFunction
%o def T(n, k): # A179748
%o if n == 0: return int(k==0);
%o if k == 1: return int(n>=1);
%o return sum( T(n-i, k-1) for i in [1..k-1] );
%o # to display triangle A179748 including column zero = [1,0,0,0,...]:
%o #for n in [0..10]: print([ T(n,k) for k in [0..n] ])
%o def a(n): return sum( T(n,k) for k in [0..n] )
%o print([a(n) for n in [0..66]])
%o # _Joerg Arndt_, Mar 24 2014
%o (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
%Y Cf. A238859 (compositions with subdiagonal growth), A238876 (partitions with subdiagonal growth), A001227 (partitions into distinct parts with subdiagonal growth).
%Y Cf. A238860 (partitions with superdiagonal growth), A238861 (compositions with superdiagonal growth), A000009 (partitions into distinct parts have superdiagonal growth by definition).
%Y The version for partitions is A001477, strong A002620.
%Y The version for permutations is A057427, strong A000295.
%Y The opposite version is A238874, first column of A352522.
%Y The version for fixed points is A240736, nonfixed A352520.
%Y The strong version is A351983, column k=1 of A352524.
%Y This is column k = 1 of A352525.
%Y A238349 counts compositions by fixed points, first col A238351.
%Y A352517 counts weak excedances of standard compositions.
%Y Cf. A008930, A010054, A088218, A098825, A114088, A219282, A238352, A319005, A350839, A352488, A352489, A352514, A352515, A352516.
%K nonn
%O 0,3
%A _Mats Granvik_, Dec 11 2010
%E New name and a(0) = 1 prepended, _Joerg Arndt_, Mar 24 2014
|