A092921 -id:A092921 - cp's OEIS frontend

A007059 Number of balanced ordered trees with n nodes.

0, 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

Offset: 0

N. J. A. Sloane, Mira Bernstein, R. Kemp

Essentially the same as A079500: a(0)=0 and a(n)=A079500(n-1) for n >= 1.
Diagonal sums of the "postage stamp" array: for rows n >= -1, column m >= 0 is given by F(n,m) = F(n-1,m) + F(n-2,m) + ... + F(n-m,m) with F(0,m)=1 (m >= 0), F(n,m)=0 (n < 0) and F(n,0)=0 (n > 0). (Rows indicate the required sum, columns indicate the integers available {0,...,m}, entries F(n,m) indicate number of ordered ways sum can be achieved (e.g., n=3, m=2: 3 = 1+1+1 = 1+2 = 2+1 so F(3,2)=3 ways)). - Richard L. Ollerton
Conjecture: for n > 0, a(n+1) is the number of "numbral" divisors of (4^n-1)/3 = A002450(n) (see A048888 for the definition of numbral arithmetic). This has been verified computationally up to n=15. - John W. Layman, Dec 18 2001 [This conjecture follows immediately from Proposition 2.3 of Frosini and Rinaldi. - N. J. A. Sloane, Apr 29 2011]
Also number of Dyck paths of semi-length n-1 with all peaks at the same height. (not mentioned in Frosini reference) - David Scambler, Nov 19 2010
For n >= 1, a(n) is the number of compositions of n where all parts are smaller than the first part, see example. For n >= 1, a(n-1) = A079500(n) is the number of compositions of n where no part exceeds the first part, see the example in A079500. - Joerg Arndt, Dec 29 2012

			F(-1,0)=0 so a(0)=0. F(0,0)=1, F(-1,1)=0 so a(1)=1. F(1,0)=0, F(0,1)=1, F(-1,2)=0 so a(2)=1. F(2,0)=0, F(1,1)=1, F(0,2)=1, F(-1,3)=0 so a(3)=2.
From _Joerg Arndt_, Dec 29 2012: (Start)
There are a(8)=24 compositions p(1) + p(2) + ... + p(m) = 8 such that p(k) < p(1):
[ 1]  [ 2 1 1 1 1 1 1 ]
[ 2]  [ 3 1 1 1 1 1 ]
[ 3]  [ 3 1 1 1 2 ]
[ 4]  [ 3 1 1 2 1 ]
[ 5]  [ 3 1 2 1 1 ]
[ 6]  [ 3 1 2 2 ]
[ 7]  [ 3 2 1 1 1 ]
[ 8]  [ 3 2 1 2 ]
[ 9]  [ 3 2 2 1 ]
[10]  [ 4 1 1 1 1 ]
[11]  [ 4 1 1 2 ]
[12]  [ 4 1 2 1 ]
[13]  [ 4 1 3 ]
[14]  [ 4 2 1 1 ]
[15]  [ 4 2 2 ]
[16]  [ 4 3 1 ]
[17]  [ 5 1 1 1 ]
[18]  [ 5 1 2 ]
[19]  [ 5 2 1 ]
[20]  [ 5 3 ]
[21]  [ 6 1 1 ]
[22]  [ 6 2 ]
[23]  [ 7 1 ]
[24]  [ 8 ]
(End)

Arnold Knopfmacher and Neville Robbins, Compositions with parts constrained by the leading summand, Ars Combin. 76 (2005), 287-295.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 401 terms from T. D. Noe)
D. Applegate, M. LeBrun, and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, J. Integer Seq., 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 trees

Cf. A048888, A092921.

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-1, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, May 01 2014

f[ n_, m_ ] := f[ n, m ]=Which[ n>0, Sum[ f[ n-i, m ], {i, 1, m} ], n<0, 0, n==0, 1 ] Table[ Sum[ f[ i, n-i ], {i, 0, n} ], {n, -1, 40} ]

from functools import cache
@cache
def F(k, n):
    return sum(F(k, n-j) for j in range(1, min(k, n))) if n > 1 else n
def A007059(n): return sum(F(k, n+1-k) for k in range(1, n+1))
print([A007059(n) for n in range(36)])  # Peter Luschny, Jan 05 2024

Define generalized Fibonacci numbers by Sum_{h>=0} F(p, h)z^n = z^(p-1)(1-z)/(1-2z+z^p+1). Then a(n) = 1 + Sum_{h=2..n} F(h-1, n-2).
G.f.: Sum_{k>0} x^k*(1 - 2*x + x^2 + (1-x)*x^(k+1))/(1 - 2*x + x^(k+1)). - Vladeta Jovovic, Feb 25 2003
G.f.: -(1 + x^2 + 1/(x-1))*(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
G.f.: Sum_{n>=1} q^n/(1-q*(1-q^n)/(1-q)) = Sum_{n>=1} q^n/(1 - Sum_{k=1..n} q^k ). - Joerg Arndt, Jan 03 2024

More terms from Vladeta Jovovic, Apr 08 2000

A048887 Array T read by antidiagonals, where T(m,n) = number of compositions of n into parts <= m.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 4, 5, 1, 1, 2, 4, 7, 8, 1, 1, 2, 4, 8, 13, 13, 1, 1, 2, 4, 8, 15, 24, 21, 1, 1, 2, 4, 8, 16, 29, 44, 34, 1, 1, 2, 4, 8, 16, 31, 56, 81, 55, 1, 1, 2, 4, 8, 16, 32, 61, 108, 149, 89, 1, 1, 2, 4, 8, 16, 32, 63, 120, 208, 274, 144, 1

Offset: 1

Clark Kimberling

Taking finite differences of array columns from the top down, we obtain (1; 1,1; 1,2,1; 1,4,2,1; ...) = A048004 rows. - Gary W. Adamson, Aug 20 2010

T(m,n) is the number of binary words of length n-1 with < m consecutive 1's. - Geoffrey Critzer, Sep 02 2012

			T(2,5) counts 11111, 1112, 1121, 1211, 2111, 122, 212, 221, where "1211" abbreviates the composition 1+2+1+1.
These eight compositions correspond respectively to: {0,0,0,0}, {0,0,0,1}, {0,0,1,0}, {0,1,0,0}, {1,0,0,0}, {0,1,0,1}, {1,0,0,1}, {1,0,1,0} per the bijection given by _N. J. A. Sloane_ in A048004. - _Geoffrey Critzer_, Sep 02 2012
The array begins:
  1,  1,  1,  1,  1,  1,  1, ...
  1,  2,  3,  5,  8, 13, ...
  1,  2,  4,  7, 13, ...
  1,  2,  4,  8, ...
  1,  2,  4, ...
  1,  2, ...
  1, ...

J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978, p. 154.

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Hsin-Po Wang and Chi-Wei Chin, On Counting Subsequences and Higher-Order Fibonacci Numbers, arXiv:2405.17499 [cs.IT], 2024. See p. 2.

Rows: A000045 (Fibonacci), A000073 (tribonacci), A000078 (tetranacci), etc.

Essentially a reflected version of A092921. See A048004 and A126198 for closely related arrays.

G := t->(1-z)/(1-2*z+z^(t+1)): T := (m,n)->coeff(series(G(m),z=0,30),z^n): matrix(7,12,T);
# second Maple program:
T:= proc(m, n) option remember; `if`(n=0 or m=1, 1,
      add(T(m, n-j), j=1..min(n, m)))
    end:
seq(seq(T(1+d-n, n), n=1..d), d=1..14); # Alois P. Heinz, May 21 2013

Table[nn=10;a=(1-x^k)/(1-x);b=1/(1-x);c=(1-x^(k-1))/(1-x); CoefficientList[ Series[a b/(1-x^2 b c), {x,0,nn}],x],{k,1,nn}]//Grid  (* Geoffrey Critzer, Sep 02 2012 *)
T[m_, n_] := T[m, n] = If[n == 0 || m == 1, 1, Sum[T[m, n-j], {j, 1, Min[n, m]}]]; Table[Table[T[1+d-n, n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Nov 12 2014, after Alois P. Heinz *)

G.f.: (1-z)/[1-2z+z^(t+1)].

A126198 Triangle read by rows: T(n,k) (1 <= k <= n) = number of compositions of n into parts of size <= k.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 5, 7, 8, 1, 8, 13, 15, 16, 1, 13, 24, 29, 31, 32, 1, 21, 44, 56, 61, 63, 64, 1, 34, 81, 108, 120, 125, 127, 128, 1, 55, 149, 208, 236, 248, 253, 255, 256, 1, 89, 274, 401, 464, 492, 504, 509, 511, 512, 1, 144, 504, 773, 912, 976, 1004, 1016, 1021, 1023, 1024

Offset: 1

N. J. A. Sloane, Mar 09 2007

Also has an interpretation as number of binary vectors of length n-1 in which the length of the longest run of 1's is <= k (see A048004). - N. J. A. Sloane, Apr 03 2011

Higher Order Fibonacci numbers: A126198(n,k) = Sum_{h=0..k} A048004(n,h); for example, A126198(7,3) = Sum_{h=0..3} A048004(7,h) or A126198(7,3) = 1 + 33 + 47 + 27 = 108, the 7th tetranacci number. A048004 row(7) produces A126198 row(7) list of 1,34,81,108,120,125,127,128 which are 1, the 7th Fibonacci, the 7th tribonacci, ... 7th octanacci numbers. - Richard Southern, Aug 04 2017

			Triangle begins:
  1;
  1,  2;
  1,  3,  4;
  1,  5,  7,  8;
  1,  8, 13, 15, 16;
  1, 13, 24, 29, 31, 32;
  1, 21, 44, 56, 61, 63, 64;
Could also be extended to a square array:
  1  1  1  1  1  1  1 ...
  1  2  2  2  2  2  2 ...
  1  3  4  4  4  4  4 ...
  1  5  7  8  8  8  8 ...
  1  8 13 15 16 16 16 ...
  1 13 24 29 31 32 32 ...
  1 21 44 56 61 63 64 ...
which when read by antidiagonals (downwards) gives A048887.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 154-155.

Alois P. Heinz, Rows n = 1..141

Rows are partial sums of rows of A048004. Cf. A048887, A092921 for other versions.
2nd column = Fibonacci numbers, next two columns are A000073, A000078; last three diagonals are 2^n, 2^n-1, 2^n-3.
Cf. A082267.

A126198 := proc(n,k) coeftayl( x*(1-x^k)/(1-2*x+x^(k+1)),x=0,n); end: for n from 1 to 11 do for k from 1 to n do printf("%d, ",A126198(n,k)); od; od; # R. J. Mathar, Mar 09 2007
# second Maple program:
T:= proc(n, k) option remember;
      if n=0 or k=1 then 1
    else add(T(n-j, k), j=1..min(n, k))
      fi
    end:
seq(seq(T(n, k), k=1..n), n=1..15);  # Alois P. Heinz, Oct 23 2011

rows = 11; t[n_, k_] := Sum[ (-1)^i*2^(n-i*(k+1))*Binomial[ n-i*k, i], {i, 0, Floor[n/(k+1)]}] - Sum[ (-1)^i*2^((-i)*(k+1)+n-1)*Binomial[ n-i*k-1, i], {i, 0, Floor[(n-1)/(k+1)]}]; Flatten[ Table[ t[n, k], {n, 1, rows}, {k, 1, n}]](* Jean-François Alcover, Nov 17 2011, after Max Alekseyev *)

G.f. for column k: (x-x^(k+1))/(1-2*x+x^(k+1)). [Riordan]
T(n,3) = A008937(n) - A008937(n-3) for n>=3. T(n,4) = A107066(n-1) - A107066(n-5) for n>=5. T(n,5) = A001949(n+4) - A001949(n-1) for n>=5. - R. J. Mathar, Mar 09 2007
T(n,k) = A181695(n,k) - A181695(n-1,k). - Max Alekseyev, Nov 18 2010
Conjecture: Sum_{k=1..n} T(n,k) = A039671(n), n>0. - L. Edson Jeffery, Nov 29 2013

More terms from R. J. Mathar, Mar 09 2007

A125127 Array L(k,n) read by antidiagonals: k-step Lucas numbers.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 3, 4, 1, 1, 3, 7, 7, 1, 1, 3, 7, 11, 11, 1, 1, 3, 7, 15, 21, 18, 1, 1, 3, 7, 15, 26, 39, 29, 1, 1, 3, 7, 15, 31, 51, 71, 47, 1, 1, 3, 7, 15, 31, 57, 99, 131, 76, 1, 1, 3, 7, 15, 31, 63, 113, 191, 241, 123, 1

Offset: 1

Jonathan Vos Post, Nov 21 2006

			Table begins:
1 | 1  1  1   1   1   1    1    1    1    1
2 | 1  3  4   7  11  18   29   47   76  123
3 | 1  3  7  11  21  39   71  131  241  443
4 | 1  3  7  15  26  51   99  191  367  708
5 | 1  3  7  15  31  57  113  223  439  863
6 | 1  3  7  15  31  63  120  239  475  943
7 | 1  3  7  15  31  63  127  247  493  983
8 | 1  3  7  15  31  63  127  255  502 1003
9 | 1  3  7  15  31  63  127  255  511 1013

Freddy Barrera, Table of n, a(n) for n = 1..5050
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
Eric Weisstein's World of Mathematics, Lucas n-Step Number

n-step Lucas number analog of A092921 Array F(k, n) read by antidiagonals: k-generalized Fibonacci numbers (and see related A048887, A048888). L(1, n) = "1-step Lucas numbers" = A000012. L(2, n) = 2-step Lucas numbers = A000204. L(3, n) = 3-step Lucas numbers = A001644. L(4, n) = 4-step Lucas numbers = A001648 Tetranacci numbers A073817 without the leading term 4. L(5, n) = 5-step Lucas numbers = A074048 Pentanacci numbers with initial conditions a(0)=5, a(1)=1, a(2)=3, a(3)=7, a(4)=15. L(6, n) = 6-step Lucas numbers = A074584 Esanacci ("6-anacci") numbers. L(7, n) = 7-step Lucas numbers = A104621 Heptanacci-Lucas numbers. L(8, n) = 8-step Lucas numbers = A105754. L(9, n) = 9-step Lucas numbers = A105755. See A000295, A125129 for comments on partial sums of diagonals.

Cf. A000012, A000032, A000204, A001644, A001648, A048887, A048888, A074048, A074584, A092921, A104621, A105754, A105755, A125129.

def L(k, n):
    if n < 0:
        return -1
    a = [-1]*(k-1) + [k] # [-1, -1, ..., -1, k]
    for i in range(1, n+1):
        a[:] = a[1:] + [sum(a)]
    return a[-1]
[L(k, n) for d in (1..12) for k, n in zip((d..1, step=-1), (1..d))] # Freddy Barrera, Jan 10 2019

L(k,n) = L(k,n-1) + L(k,n-2) + ... + L(k,n-k); L(k,n) = -1 for n < 0, and L(k,0) = k.

G.f. for row k: x*(dB(k,x)/dx)/(1-B(k,x)), where B(k,x) = x + x^2 + ... + x^k. - Petros Hadjicostas, Jan 24 2019

Corrected by Freddy Barrera, Jan 10 2019

A368279 a(n) is the number of compositions of n where the first part is the largest part and the last part is not 1. Row sums of A368579.

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 6, 10, 19, 34, 63, 116, 216, 402, 754, 1417, 2674, 5061, 9608, 18286, 34888, 66706, 127798, 245284, 471561, 907964, 1750695, 3379992, 6533458, 12643162, 24491796, 47490688, 92170704, 179040096, 348064190, 677174709, 1318429534, 2568691317

Offset: 0

Peter Luschny, Jan 04 2024

nonn

Considering more generally the family of generating functions (1 - x)^n * Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k)) one finds several sequences related to compositions as indicated in the cross-references.

The compositions considered here can also be understood as perfectly balanced, ordered trees. See the linked illustrations. - Peter Luschny, Feb 26 2024

			a(0) = card({[0]}) = 1.
a(1) = card({}) = 0.
a(2) = card({[2]}) = 1.
a(3) = card({[3]}) = 1.
a(4) = card({[2, 2], [4]}) = 2.
a(5) = card({[2, 1, 2], [3, 2], [5]}) = 3.
a(6) = card({[2, 2, 2], [2, 1, 1, 2], [3, 3], [3, 1, 2], [4, 2], [6]}) = 6.
a(7) = card({[2, 2, 1, 2], [2, 1, 2, 2], [2, 1, 1, 1, 2], [3, 2, 2], [3, 1, 3], [3, 1, 1, 2], [4, 3], [4, 1, 2], [5, 2], [7]}) = 10.
a(8) = card({[2, 2, 2, 2],  [2, 2, 1, 1, 2], [2, 1, 2, 1, 2], [2, 1, 1, 2, 2], [2, 1, 1, 1, 1, 2], [3, 3, 2], [3, 2, 3], [3, 2, 1, 2], [3, 1, 2, 2], [3, 1, 1, 3], [3, 1, 1, 1, 2], [4, 4], [4, 2, 2], [4, 1, 3], [4, 1, 1, 2], [5, 3], [5, 1, 2], [6, 2], [8]}) = 19.

Peter Luschny, A generator for the A368279 compositions.
Peter Luschny, Some perfectly balanced, ordered trees illustrating A368279.

Cf. A368579, A369492, A007059, A092921, A188541.

Cf. A369115 (n=-2), A186537 left shifted (n=-1), A079500 (n=0), this sequence (n=1), A369116 (n=2).

gf := (1 - x)*sum(x^j / (1 - sum(x^k, k = 1..j)), j = 0..42):
ser := series(gf, x, 40): seq(coeff(ser, x, n), n = 0..37);
# Peter Luschny, Jan 19 2024

from functools import cache
@cache
def F(k, n):
    return sum(F(k,n-j) for j in range(1,min(k,n))) if n>1 else n
def a(n): return sum(F(k+1, n+1-k) - F(k+1, n-k) for k in range(n+1))
print([a(n) for n in range(38)])

def C(n): return sum(Compositions(n, max_part=k, inner=[k]).cardinality()
                 for k in (0..n))
def a(n): return C(n) - C(n-1) if n > 1 else 1 - n
print([a(n) for n in (0..28)])

a(n) = Sum_{k=0..n} (F(k+1, n+1-k) - F(k+1, n-k)) where F(k, n) = Sum_{j=1..min(k, n)} F(k, n-j) if n > 1 and otherwise n. F(k, n) refers to the generalized Fibonacci number A092921.
a(n) = A007059(n+1) - A007059(n).
G.f.: (1 - x)*(Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k ))) = (1 - x) * GfA079500. - Peter Luschny, Jan 20 2024

A247506 Generalized Fibonacci numbers: square array A(n,k) read by ascending antidiagonals, A(n,k) = [x^k]((1-Sum_{j=1..n} x^j)^(-1)), (n>=0, k>=0).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 4, 5, 1, 0, 1, 1, 2, 4, 7, 8, 1, 0, 1, 1, 2, 4, 8, 13, 13, 1, 0, 1, 1, 2, 4, 8, 15, 24, 21, 1, 0, 1, 1, 2, 4, 8, 16, 29, 44, 34, 1, 0, 1, 1, 2, 4, 8, 16, 31, 56, 81, 55, 1, 0

Offset: 0

Peter Luschny, Nov 02 2014

			[n\k] [0][1][2][3][4] [5] [6] [7]  [8]  [9] [10]  [11]  [12]
   [0] 1, 0, 0, 0, 0,  0,  0,  0,   0,   0,   0,    0,    0
   [1] 1, 1, 1, 1, 1,  1,  1,  1,   1,   1,   1,    1,    1
   [2] 1, 1, 2, 3, 5,  8, 13, 21,  34,  55,  89,  144,  233  [A000045]
   [3] 1, 1, 2, 4, 7, 13, 24, 44,  81, 149, 274,  504,  927  [A000073]
   [4] 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401,  773, 1490  [A000078]
   [5] 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464,  912, 1793  [A001591]
   [6] 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492,  976, 1936  [A001592]
   [7] 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000  [A066178]
   [8] 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028  [A079262]
   [.] .  .  .  .  .   .   .   .    .    .    .     .     .
  [oo] 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048  [A011782]
.
As a triangular array, starts:
  1,
  1, 0,
  1, 1, 0,
  1, 1, 1, 0,
  1, 1, 2, 1, 0,
  1, 1, 2, 3, 1, 0,
  1, 1, 2, 4, 5, 1, 0,
  1, 1, 2, 4, 7, 8, 1, 0,
  1, 1, 2, 4, 8, 13, 13, 1, 0,
  1, 1, 2, 4, 8, 15, 24, 21, 1, 0,
  ...

Stefano Spezia, First 140 antidiagonals of the array, flattened
Harold R. Parks and Dean C. Wills, Sum of k-bonacci Numbers, arXiv:2208.01224 [math.CO], 2022. See p. 5.

Cf. A247505, A011782, A000045, A000073, A000078, A001591, A001592, A066178, A079262.

Cf. A048887, A092921, A144406.

A := (n,k) -> coeff(series((1-add(x^j, j=1..n))^(-1),x,k+2),x,k):
seq(print(seq(A(n,k), k=0..12)), n=0..9);

A[n_, k_] := A[n, k] = If[k<0, 0, If[k==0, 1, Sum[A[n, j], {j, k-n, k-1}]]]; Table[A[n-k, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 08 2019 *)

A(n, k) = Sum_{j=0..floor(k/(n+1))} (-1)^j*((k - j*n) + j + delta(k,0))/(2*(k - j*n) + delta(k,0))*binomial(k - j*n, j)*2^(k-j*(n+1)), where delta denotes the Kronecker delta (see Corollary 3.2 in Parks and Wills). - Stefano Spezia, Aug 06 2022

A125129 Partial sums of diagonals of array of k-step Lucas numbers as in A125127, read by antidiagonals.

Original entry on oeis.org

1, 1, 4, 1, 8, 11, 1, 12, 19, 26, 1, 19, 33, 45, 57, 1, 30, 58, 84, 102, 120, 1, 48, 101, 157, 197, 222, 247, 1, 77, 179, 292, 380, 436, 469, 502, 1, 124, 318, 546, 731, 855, 929, 971, 1013, 1, 200, 567, 1026, 1409, 1674, 1838, 1932, 1984, 2036

Offset: 1

Jonathan Vos Post, Nov 23 2006

Array of partial sums of diagonals of L(k,n) begins: 0.|.1...4..11...26...57..120..247..502.1013.2036.
|.1...8..19...45..102..222..469..971.1984.
|.1..12..33...84..197..436..929.1932.
|.1..19..58..157..380..855.1838.
|.1..30.101..292..731.1674.
|.1..48.179..546.1409.
|.1..77.318.1026.
|.1.124.567.
|.1.200.
|.1.

			Row 1 of the derived array is the partial sum of the diagonal above the main diagonal of array of k-step Lucas numbers as in A125127, hence the partial sums of: 1, 7, 11, 26, 57, 120, 247, 502, 103, ... are 1 = 1; 8 = 1 + 7; 19 = 1 + 7 + 11; 45 = 1 + 7 + 11 + 26; and so forth.

Cf. A000012, A000032, A000204, A001644, A001648, A048887, A048888, A074048, A074584, A092921, A104621, A105754, A105755, A125127, A000295.

Row 0 = SUM[i=1..n]L(i,i) = A127128 = partial sum of main diagonal of array of A125127. Row 1 = SUM[i=1..n]L(i,i+1) = partial sum of diagonal above main diagonal of array of A125127. Row 2 = SUM[i=1..n]L(i,i+2) = partial sum of diagonal 2 above main diagonal of array of A125127. .. Row m = SUM[i=1..n]L(i,i+m) = partial sum of diagonal 2 above main diagonal of array of A125127.

A144406 Rectangular array A read by upward antidiagonals: entry A(n,k) in row n and column k gives the number of compositions of k in which no part exceeds n, n>=1, k>=0.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 4, 5, 1, 1, 1, 2, 4, 7, 8, 1, 1, 1, 2, 4, 8, 13, 13, 1, 1, 1, 2, 4, 8, 15, 24, 21, 1, 1, 1, 2, 4, 8, 16, 29, 44, 34, 1, 1, 1, 2, 4, 8, 16, 31, 56, 81, 55, 1, 1, 1, 2, 4, 8, 16, 32, 61, 108, 149, 89, 1, 1, 1, 2, 4, 8, 16, 32, 63, 120, 208, 274, 144, 1

Offset: 1

Roger L. Bagula and Gary W. Adamson, Sep 29 2008

Polynomial expansion as antidiagonal of p(x,n) = (x-1)/(x^n*(-x+(2*x-1)/x^n)). Based on the Pisot general polynomial type q(x,n) = x^n - (x^n-1)/(x-1) (the original name of the sequence).
Row sums are 1, 2, 3, 5, 8, 14, ... (A079500).
Conjecture: Since the array row sequences successively tend to A000079, the absolute values of nonzero differences between two successive row sequences tend to A045623 = {1,2,5,12,28,64,144,320,704,1536,...}, as k -> infinity. - L. Edson Jeffery, Dec 26 2013

			Array A begins:
  {1, 1, 1, 1, 1,  1,  1,  1,   1,   1,   1, ...}
  {1, 1, 2, 3, 5,  8, 13, 21,  34,  55,  89, ...}
  {1, 1, 2, 4, 7, 13, 24, 44,  81, 149, 274, ...}
  {1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, ...}
  {1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, ...}
  {1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, ...}
  {1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, ...}
  {1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, ...}
  {1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, ...}
  ... - _L. Edson Jeffery_, Dec 26 2013
As a triangle:
  {1},
  {1, 1},
  {1, 1, 1},
  {1, 1, 2, 1},
  {1, 1, 2, 3, 1},
  {1, 1, 2, 4, 5, 1},
  {1, 1, 2, 4, 7, 8, 1},
  {1, 1, 2, 4, 8, 13, 13, 1},
  {1, 1, 2, 4, 8, 15, 24, 21, 1},
  {1, 1, 2, 4, 8, 16, 29, 44, 34, 1},
  {1, 1, 2, 4, 8, 16, 31, 56, 81, 55, 1},
  {1, 1, 2, 4, 8, 16, 32, 61, 108, 149, 89, 1},
  {1, 1, 2, 4, 8, 16, 32, 63, 120, 208, 274, 144, 1},
  {1, 1, 2, 4, 8, 16, 32, 64, 125, 236, 401, 504, 233, 1},
  {1, 1, 2, 4, 8, 16, 32, 64, 127, 248, 464, 773, 927, 377, 1}

Cf. A000079, A045623, A092921, A175331.
Same as A048887 but with a column of 1's added on the left (the number of compositions of 0 is defined to be equal to 1).
Array rows (with appropriate offsets) are A000012, A000045, A000073, A000078, A001591, A001592, etc.

g[x_, n_] = x^(n) - (x^n - 1)/(x - 1);
h[x_, n_] = FullSimplify[ExpandAll[x^(n)*g[1/x, n]]];
f[t_, n_] := 1/h[t, n];
a = Table[CoefficientList[Series[f[t, m], {t, 0, 30}], t], {m, 1, 31}];
b = Table[Table[a[[n - m + 1]][[m]], {m, 1, n }], {n, 1, 15}];
Flatten[b] (* Triangle version *)
Grid[Table[CoefficientList[Series[(1 - x)/(1 - 2 x + x^(n + 1)), {x, 0, 10}], x], {n, 1, 10}]] (* Array version - L. Edson Jeffery, Jul 18 2014 *)

t(n,m) = antidiagonal_expansion of p(x,n) where p(x,n) = (x-1)/(x^n*(-x+(2*x-1)/x^n)).

G.f. for array A: (1-x)/(1 - 2*x + x^(n+1)), n>=1. - L. Edson Jeffery, Dec 26 2013

Definition changed by L. Edson Jeffery, Jul 18 2014

A368579 Triangle read by rows. T(n, k) is the number of compositions of n where the first part k is the largest part and the last part is not 1.

Original entry on oeis.org

1, -1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 2, 2, 1, 0, 1, 0, 0, 3, 3, 2, 1, 0, 1, 0, 0, 5, 6, 4, 2, 1, 0, 1, 0, 0, 8, 11, 7, 4, 2, 1, 0, 1, 0, 0, 13, 20, 14, 8, 4, 2, 1, 0, 1, 0, 0, 21, 37, 27, 15, 8, 4, 2, 1, 0, 1

Offset: 0

Peter Luschny, Jan 05 2024

			Triangle T(n, k) starts:
  [0] [ 1]
  [1] [-1, 1]
  [2] [ 0, 0, 1]
  [3] [ 0, 0, 0,  1]
  [4] [ 0, 0, 1,  0, 1]
  [5] [ 0, 0, 1,  1, 0, 1]
  [6] [ 0, 0, 2,  2, 1, 0, 1]
  [7] [ 0, 0, 3,  3, 2, 1, 0, 1]
  [8] [ 0, 0, 5,  6, 4, 2, 1, 0, 1]
  [9] [ 0, 0, 8, 11, 7, 4, 2, 1, 0, 1]
For instance, row 6 lists the compositions below:
  0  .
  1  .
  2 [2, 2, 2], [2, 1, 1, 2];
  3 [3, 3], [3, 1, 2];
  4 [4, 2];
  5  .
  6 [6].

Cf. A368279 (row sums), A092921 (generalized Fibonacci), A000045 (Fibonacci column k=2), A034008 (T(2n, n)).

from functools import cache
@cache
def F(k, n):
    return sum(F(k, n-j) for j in range(1, min(k, n))) if n > 1 else n
def Trow(n):
    return list(F(k+1, n+1-k) - F(k+1, n-k) for k in range(n+1))
print(flatten([Trow(n) for n in range(12)]))

T(n, k) = F(k+1, n+1-k) - F(k+1, n-k) where F(k, n) = Sum_{j=1..min(n, k)} F(k, n-j) if n > 1 and otherwise n. F(n, k) refers to the generalized Fibonacci numbers A092921.

A202805 a(n) is the largest k in an n_nacci(k) sequence (Fibonacci(k) for n=2, tribonacci(k) for n=3, etc.) such that n_nacci(k) >= 2^(k-n-1).

Original entry on oeis.org

6, 12, 25, 48, 94, 184, 363, 719, 1430, 2851, 5691, 11371, 22728, 45443, 90870, 181724, 363429, 726839, 1453658, 2907295, 5814566, 11629107

Offset: 2

Frank M Jackson, Dec 24 2011

From Frank M Jackson, Jul 02 2023: (Start)
Define the n_nacci sequence, basically row n in A092921, with an offset of 0, n_nacci(k) = 0 for 0 <= k <= n-2 and n_nacci(n-1) = 1. Thereafter, n_nacci(k) for k >= n continues as the sum of its previous n terms.
This means that n_nacci(k) = 2^(k-n) for n <= k <= 2n-1. In the limit as n tends to infinity the n_nacci sequence after an initial large set of zeros followed by 1 has successive terms of ascending powers of 2.
As the n-acci constants, (A001622, A058265, A086088, A103814,...) are smaller than 2, for each n_nacci sequence there is a largest k such that n_nacci(k) >= 2^(k-n-1). (End)

			For n=3, the tribonacci sequence is 0,0,1,1,2,4,7,...,149,274,504,... and the 13th term is 504 < 512 so a(n)=12 because 274 is greatest term >= 2^(12-3-1) = 256.

Cf. A000045, A000073, A000078.

nAcci := proc(n,k)
    option remember ;
    if k <= n-2 then
        0;
    elif k = n-1 then
        1;
    else
        add( procname(n,i),i=k-n..k-1) ;
    end if;
end proc:
A202805 := proc(n)
    local k ;
    for k from n do
        if nAcci(n,k) < 2^(k-n-1) then
            return k-1;
        end if;
    end do:
end proc:
for n from 2 do
    print(n,A202805(n)) ;
end do: # R. J. Mathar, Mar 11 2024

fib[n_, m_] := (Block[{nacci}, (Do[nacci[g]=0, {g, 0, m - 2}];
nacci[m-1]=1;nacci[p_] := (nacci[p]=Sum[nacci[h], {h, p-m, p-1}]);nacci[n])]);
crossover[q_] := (Block[{$RecursionLimit=Infinity}, (k=0;While[fib[k+q+1, q]>=2^k, k++];k+q)]);
Table[crossover[j], {j, 2, 12}]

def nacci(n): # generator of n_nacci terms
    window = [0]*(n-1) + [1]
    yield from window
    while True:
        an = sum(window)
        yield an
        window = window[1:] + [an]
def a(n):
    pow2 = 1
    for k, t in enumerate(nacci(n)):
        if k > n + 1: pow2 <<= 1
        if 0 < t < pow2: return k-1
print([a(n) for n in range(2, 12)]) # Michael S. Branicky, Jan 29 2025

Edited by N. J. A. Sloane, May 20 2023
There seems to be an error in the Comment. See "History" tab. - N. J. A. Sloane, Jun 24 2023
Removed musing about what might define "complete" sequences. - R. J. Mathar, Mar 11 2024
a(17)-a(23) from Michael S. Branicky, Jan 29 2025

cp's OEIS Frontend

A007059 Number of balanced ordered trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A048887 Array T read by antidiagonals, where T(m,n) = number of compositions of n into parts <= m.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A126198 Triangle read by rows: T(n,k) (1 <= k <= n) = number of compositions of n into parts of size <= k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A125127 Array L(k,n) read by antidiagonals: k-step Lucas numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Sage

Formula

Extensions

A368279 a(n) is the number of compositions of n where the first part is the largest part and the last part is not 1. Row sums of A368579.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

SageMath

Formula

A247506 Generalized Fibonacci numbers: square array A(n,k) read by ascending antidiagonals, A(n,k) = [x^k]((1-Sum_{j=1..n} x^j)^(-1)), (n>=0, k>=0).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A125129 Partial sums of diagonals of array of k-step Lucas numbers as in A125127, read by antidiagonals.

Views