A126198 -id:A126198 - cp's OEIS frontend

A048004 Triangular array read by rows: T(n,k) = number of binary vectors of length n whose longest run of consecutive 1's has length k, for n >= 0, 0 <= k <= n.

1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 7, 5, 2, 1, 1, 12, 11, 5, 2, 1, 1, 20, 23, 12, 5, 2, 1, 1, 33, 47, 27, 12, 5, 2, 1, 1, 54, 94, 59, 28, 12, 5, 2, 1, 1, 88, 185, 127, 63, 28, 12, 5, 2, 1, 1, 143, 360, 269, 139, 64, 28, 12, 5, 2, 1, 1, 232, 694, 563, 303, 143, 64, 28, 12, 5, 2, 1, 1, 376, 1328, 1167, 653, 315, 144, 64, 28, 12, 5, 2, 1

Offset: 0

Clark Kimberling

Equivalently, number of compositions of n+1 having largest part (exactly) k+1. Example: T(4,2)=5 because we have 3+2, 2+3, 3+1+1, 1+3+1 and 1+1+3. - Emeric Deutsch, Apr 01 2005
Here is a bijection between the binary words and the compositions: prefix the vector with a 0, place a comma before each 0, then read the lengths of the runs. Example: 1100 -> 01100 -> ,011,0,0 -> 311 -> 3+1+1. - N. J. A. Sloane, Apr 03 2011
A formula based on the conjugates of the partitions of n with largest part k is given as a Sage program below. Note that it gives the compositions in the natural enumeration 'n with largest part k'. The 'conjugate' formula leads to A097805. - Peter Luschny, Jul 13 2015

			Triangle begins:
1;
1,  1;
1,  2,   1;
1,  4,   2,   1;
1,  7,   5,   2,  1;
1, 12,  11,   5,  2,  1;
1, 20,  23,  12,  5,  2,  1;
1, 33,  47,  27, 12,  5,  2, 1;
1, 54,  94,  59, 28, 12,  5, 2, 1;
1, 88, 185, 127, 63, 28, 12, 5, 2, 1;
...
Example: T(4,2) = 5 because we have 1100, 1101, 0110, 0011, 1011.

J. Kappraff, Beyond Measure, World Scientific, 2002; see pp. 471-472.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.

Alois P. Heinz, Rows n = 0..140, flattened
Richard Southern, Python program
J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29. (Annotated scanned copy)

See A126198 and A048887 for closely related arrays.
T(n,2) = Fibonacci(n+2) - 1, A000071, T(n,3) = b(n) for n=3, 4, ..., where b=A000100, T(n,4) = c(n) for n = 4, 5, ..., where c=A000102.
Nonnegative elements of columns approach A045623.
Cf. A048003, A097805.

tri n k | (k < 0) || (k > n) = 0
        | (k == 0) || (k == n) = 1
        | otherwise = 2*tri (n-1) k + tri (n-1) (k-1) - 2*tri (n-2) (k-1)
                            + tri (n-k-1) (k-1) - tri (n-k-2) k
-- Valentin Hübner, Jul 20 2017, after David W. Wilson

G:=k->(1-x)^2*x^k/(1-2*x+x^(k+1))/(1-2*x+x^(k+2)): for k from 0 to 14 do g[k]:=series(G(k),x=0,15) od: 1,seq(seq(coeff(g[k],x^n),k=0..n),n=1..12); # Emeric Deutsch, Apr 01 2005
# second Maple program:
B:= proc(n, k) option remember; `if`(n=0 or k=1, 1,
      add (B(n-j, k), j=1..min(n, k)))
    end:
T:= (n, k)-> B(n+1, k+1)-B(n+1, k):
seq(seq(T(n, k), k=0..n), n=0..14); # Alois P. Heinz, May 21 2013

nn=10;f[list_]:=Select[list,#>0&];Map[f,Transpose[Table[ CoefficientList[ Series[(1-x^k)/(1-2x+x^(k+1))-(1-x^(k-1))/ (1-2x+x^k),{x,0,nn}],x],{k,1,nn}]]]//Grid  (* Geoffrey Critzer, Jan 13 2013 *)
B[n_, k_] := B[n, k] = If[n==0 || k==1, 1, Sum[B[n-j, k], {j, 1, Min[n, k]} ]]; T[n_, k_] := B[n+1, k+1] - B[n+1, k]; Table[T[n, k], {n, 0, 14}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 01 2015, after Alois P. Heinz *)

Python
```
# See Richard Southern link.
```

# Computes the triangle obtained by augmenting T(n,k) by appending the column
# 1,0,0,0,... on the left. Illustrates a basic partition formula, is not
# efficient as a program for large n.
def A048004_row(n):
    r = []
    for k in (0..n):
        s = 0
        for p in Partitions(n, max_part=k, inner=[k]):
            q = p.conjugate()
            s += mul(binomial(q[j],q[j+1]) for j in range(len(q)-1))
        r.append(s)
    return r
[A048004_row(n) for n in (0..9)] # Peter Luschny, Jul 13 2015

T(n, k) = 0 if k < 0 or k > n, 1 if k = 0 or k = n, 2T(n-1, k) + T(n-1, k-1) - 2T(n-2, k-1) + T(n-k-1, k-1) - T(n-k-2, k) otherwise. - David W. Wilson
T(n, k) = A048887(n+1, k+1) - A048887(n+1, k). - Henry Bottomley, Oct 29 2002
G.f. for column k: (1-x)^2*x^k/((1-2*x+x^(k+1))*(1-2*x+x^(k+2))). - Emeric Deutsch, Apr 01 2005
From Gary W. Adamson, Jun 23 2012: (Start)
Create an array of rows such that row 0 is the INVERT transform of (1,0,0,0,...); row 1 is the INVERT transform of (1,1,0,0,0,...); row 2 is the INVERT transform of (1,1,1,0,0,0,...) and so on:
  1, 1, 1, 1,  1,  1, ...
  1, 2, 3, 5,  8, 13, ...
  1, 2, 4, 7, 13, 24, ...
  1, 2, 4, 8, 15, 29, ...
  ... Then, take finite differences of column terms from the top -> down. Row terms of the triangle are finite differences of the array columns. (End)
T(n,k) = A126198(n+1,k+1) - A126198(n+1,k). - L. Edson Jeffery, May 21 2013
Recurrence: T(n+1,k) = Sum_{h=0..k} T(n-k, h) + Sum_{i=n-k+1..n} T(i, k); for example, T(7,3) = Sum_{h=0..3} T(3,h) + Sum_{i=4..6} T(i,3) or T(7,3) = (1+4+2+1) + (2+5+12) = 27. Example: T(4,2) = (1+1) + (1+2) = 5. - Richard Southern, Jul 09 2017
Difference between higher order Fibonacci numbers is equal to recurrence. T(n+1,k) = A126198 (n+1,k) - A126198 (n+1,k-1) = Sum_{i=n-k..n} A126198 (i,k) - Sum_{i=n-k+1..n} A126198 (i,k-1) = A126198 (n-k,k) + Sum_{i=n-k+1..n} (A126198 (i,k) - A126198 (i,k-1)) = Sum_{h=0..k} T(n-k, h) + Sum_{i=n-k+1..n} T(i, k). For example T(7,3) = A126198 (7,3) - A126198 (7,2) = 108 - 81 = (8+15+29+56) - (13+24+44) = 8 + (15-13) + (29-24) + (56-44) = 8 + (2+5+12) = (1+4+2+1) + (2+5+12). - Richard Southern, Aug 04 2017

More terms from Emeric Deutsch, Apr 01 2005

Edited by N. J. A. Sloane, Apr 03 2011

A092921 Array F(k, n) read by descending antidiagonals: k-generalized Fibonacci numbers in row k >= 1, starting (0, 1, 1, ...), for column n >= 0.

Original entry on oeis.org

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

Offset: 0

Ralf Stephan, Apr 17 2004

For all k >= 1, the k-generalized Fibonacci number F(k,n) satisfies the recurrence obtained by adding more terms to the recurrence of the Fibonacci numbers.
The number of tilings of an 1 X n rectangle with tiles of size 1 X 1, 1 X 2, ..., 1 X k is F(k,n).
T(k,n) is the number of 0-balanced ordered trees with n edges and height k (height is the number of edges from root to a leaf). - Emeric Deutsch, Jan 19 2007
Brlek et al. (2006) call this table "number of psp-polyominoes with flat bottom". - N. J. A. Sloane, Oct 30 2018

			From _Peter Luschny_, Apr 03 2021: (Start)
Array begins:
                n = 0  1  2  3  4  5   6   7   8    9   10
  -------------------------------------------------------------
  [k=1, mononacci ] 0, 1, 1, 1, 1, 1,  1,  1,  1,   1,   1, ...
  [k=2, Fibonacci ] 0, 1, 1, 2, 3, 5,  8, 13, 21,  34,  55, ...
  [k=3, tribonacci] 0, 1, 1, 2, 4, 7, 13, 24, 44,  81, 149, ...
  [k=4, tetranacci] 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ...
  [k=5, pentanacci] 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, ...
  [k=6]             0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, ...
  [k=7]             0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, ...
  [k=8]             0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, ...
  [k=9]             0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, ...
Note that the first parameter in F(k, n) refers to rows, and the second parameter refers to columns. This is always the case. Only the usual naming convention for the indices is not adhered to because it is common to call the row sequences k-bonacci numbers. (End)
.
From _Peter Luschny_, Aug 12 2015: (Start)
As a triangle counting compositions of n with largest part k:
  [n\k]| [0][1] [2] [3] [4][5][6][7][8][9]
   [0] | [0]
   [1] | [0, 1]
   [2] | [0, 1,  1]
   [3] | [0, 1,  1,  1]
   [4] | [0, 1,  2,  1,  1]
   [5] | [0, 1,  3,  2,  1, 1]
   [6] | [0, 1,  5,  4,  2, 1, 1]
   [7] | [0, 1,  8,  7,  4, 2, 1, 1]
   [8] | [0, 1, 13, 13,  8, 4, 2, 1, 1]
   [9] | [0, 1, 21, 24, 15, 8, 4, 2, 1, 1]
For example for n=7 and k=3 we have the 7 compositions [3, 3, 1], [3, 2, 2], [3, 2, 1, 1], [3, 1, 3], [3, 1, 2, 1], [3, 1, 1, 2], [3, 1, 1, 1, 1]. (End)

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Srecko Brlek, Andrea Frosini, Simone Rinaldi, and Laurent Vuillon, Tilings by translation: enumeration by a rational language approach, The Electronic Journal of Combinatorics, vol. 13, (2006). Table 1 is essentially this array. - _N. J. A. Sloane_, Jul 20 2014
Eric S. Egge, Restricted permutations related to Fibonacci numbers and k-generalized Fibonacci numbers, arXiv:math/0109219 [math.CO], 2001.
Eric S. Egge, Restricted 3412-Avoiding Involutions, arXiv:math/0307050 [math.CO], 2003.
Eric S. Egge and Toufik Mansour, Restricted permutations, Fibonacci numbers and k-generalized Fibonacci numbers, arXiv:math/0203226 [math.CO], 2002.
Eric S. Egge and Toufik Mansour, 231-avoiding involutions and Fibonacci numbers, arXiv:math/0209255 [math.CO], 2002.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
Abraham Flaxman, Aram W. Harrow, and Gregory B. Sorkin, Strings with Maximally Many Distinct Subsequences and Substrings, Electronic J. Combinatorics 11 (1) (2004), Paper R8.
Ivan Flores, k-Generalized Fibonacci numbers, Fib. Quart., 5 (1967), 258-266.
H. Gabai, Generalized Fibonacci k-sequences, Fib. Quart., 8 (1970), 31-38.
R. Kemp, Balanced ordered trees, Random Structures and Alg., 5 (1994), pp. 99-121.
E. P. Miles jr., Generalized Fibonacci numbers and associated matrices, The Amer. Math. Monthly, 67 (1960) 745-752.
M. D. Miller, On generalized Fibonacci numbers, The Amer. Math. Monthly, 78 (1971) 1108-1109.
Michel Mollard, p-th order generalized Fibonacci cubes and maximal cubes in Fibonacci p-cubes, arXiv:2507.16387 [math.CO], 2025. See p. 3.
Harold R. Parks and Dean C. Wills, Sum of k-bonacci Numbers, arXiv:2208.01224 [math.CO], 2022. See p. 5.
Hsin-Po Wang and Chi-Wei Chin, On Counting Subsequences and Higher-Order Fibonacci Numbers, arXiv:2405.17499 [cs.IT], 2024. See p. 2.

Columns converge to A166444: each column n converges to A166444(n) = 2^(n-2).
Rows 1-8 are (shifted) A057427, A000045, A000073, A000078, A001591, A001592, A066178, A079262.
Essentially a reflected version of A048887.
See A048004 and A126198 for closely related arrays.
Cf. A066099.

F:= proc(k, n) option remember; `if`(n<2, n,
      add(F(k, n-j), j=1..min(k,n)))
    end:
seq(seq(F(k, d+1-k), k=1..d+1), d=0..12);  # Alois P. Heinz, Nov 02 2016
# Based on the above function:
Arow := (k, len) -> seq(F(k, j), j = 0..len):
seq(lprint(Arow(k, 14)), k = 1..10); # Peter Luschny, Apr 03 2021

F[k_, n_] := F[k, n] = If[n<2, n, Sum[F[k, n-j], {j, 1, Min[k, n]}]];
Table[F[k, d+1-k], {d, 0, 12}, {k, 1, d+1}] // Flatten (* Jean-François Alcover, Jan 11 2017, translated from Maple *)

F(k,n)=if(n<2,if(n<1,0,1),sum(i=1,k,F(k,n-i)))

T(m,n)=!!n*(matrix(m,m,i,j,j==i+1||i==m)^(n+m-2))[1,m] \\ M. F. Hasler, Apr 20 2018

F(k,n) = if(n==0,0, polcoeff(lift(Mod('x, Pol(vector(k+1,i, if(i==1,1,-1))))^(n+k-2)), k-1)); \\ Kevin Ryde, Jun 05 2020

# As a triangle of compositions of n with largest part k.
C = lambda n,k: Compositions(n, max_part=k, inner=[k]).cardinality()
for n in (0..9): [C(n,k) for k in (0..n)] # Peter Luschny, Aug 12 2015

F(k,n) = F(k,n-1) + F(k,n-2) + ... + F(k,n-k); F(k,1) = 1 and F(k,n) = 0 for n <= 0.
G.f.: x/(1-Sum_{i=1..k} x^i).
F(k,n) = 2^(n-2) for 1 < n <= k+1. - M. F. Hasler, Apr 20 2018
F(k,n) = Sum_{j=0..floor(n/(k+1))} (-1)^j*((n - j*k) + j + delta(n,0))/(2*(n - j*k) + delta(n,0))*binomial(n - j*k, j)*2^(n-j*(k+1)), where delta denotes the Kronecker delta (see Corollary 3.2 in Parks and Wills). - Stefano Spezia, Aug 06 2022

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

A175331 Array A092921(n,k) without the first two rows, read by antidiagonals.

Original entry on oeis.org

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

Offset: 2

Roger L. Bagula, Dec 03 2010

Antidiagonal sums are A048888. This is a transposed version of A048887, so the bivariate generating function is obtained by swapping the two arguments.

Brlek et al. (2006) call this table "number of psp-polyominoes with flat bottom". - N. J. A. Sloane, Oct 30 2018

			The array starts in row n=2 with columns k >= 1 as:
  1   1   1   1   1   1   1   1   1   1
  1   2   2   2   2   2   2   2   2   2
  1   3   4   4   4   4   4   4   4   4
  1   5   7   8   8   8   8   8   8   8
  1   8  13  15  16  16  16  16  16  16
  1  13  24  29  31  32  32  32  32  32
  1  21  44  56  61  63  64  64  64  64
  1  34  81 108 120 125 127 128 128 128
  1  55 149 208 236 248 253 255 256 256

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

Srecko Brlek, Andrea Frosini, Simone Rinaldi, and Laurent Vuillon, Tilings by translation: enumeration by a rational language approach, The Electronic Journal of Combinatorics, vol.13, (2006). Table 1 is essentially this array. - _N. J. A. Sloane_, Jul 20 2014

Cf. A000045, A048887, A048004, A126198.

A092921 := proc(n,k) if k <= 0 or n <= 0 then 0; elif k = 1 or n = 1 then 1; else add( procname(n-i,k),i=1..k) ; end if; end proc:
A175331 := proc(n,k) A092921(n,k) ; end proc: # R. J. Mathar, Dec 17 2010

f[x_, n_] = (x - x^(m + 1))/(1 - 2*x + x^(m + 1))
a = Table[Table[SeriesCoefficient[
      Series[f[x, m], {x, 0, 10}], n], {n, 0, 10}], {m, 1, 10}];
Table[Table[a[[m, n - m + 1]], {m, 1, n - 1}], {n, 1, 10}];
Flatten[%]

T(n,k) = A092921(n,k), n >= 2.
T(n,2) = A000045(n).
T(n,3) = A000073(n+2).
T(n,4) = A000078(n+2).

A082267 Number of palindromes that use nonzero digits and have a digit sum of n.

Original entry on oeis.org

1, 2, 2, 4, 4, 8, 8, 16, 16, 31, 31, 62, 62, 124, 124, 248, 248, 496, 496, 991, 991, 1980, 1980, 3956, 3956, 7904, 7904, 15792, 15792, 31553, 31553, 63044, 63044, 125964, 125964, 251680, 251680, 502864, 502864, 1004737, 1004737, 2007494, 2007494

Offset: 1

Amarnath Murthy, Apr 12 2003

Consider the array in which the n-th row contains all the palindromes that use nonzero digits and have a digit sum of n:
1
2 11
3 111
4 22 121 1111
5 131 212 11111
6 33 141 222 11211 1221 2112 111111
...
a(n) = number of partitions of n into parts < 10 (single-digit nonzero parts) that can be arranged to form a palindrome.

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A082264, A082265, A082266.

seq(coeff(series(x*(1+2*x-x^9-x^10-x^19)/(1-2*x^2+x^20),x,n+1), x, n), n = 1 .. 42); # Muniru A Asiru, Dec 08 2018

a(1) = 1, a(2) = 2. For 2

Further remarks from Jonathan R. Love (japanada11(AT)yahoo.ca), Mar 08 2007: (Start) For 2

For n=10 or 11: Using the rules for 2

For 12

For 20: Including the terms subtracted in 12

For 21<=n: From this point on, all possible terms are 9(a(n-18))9 + 8(a(n-16))8 + 7(a(n-14))7 + 6(a(n-12))6 + 5(a(n-10))5 + 4(a(n-8))4 + 3(a(n-6))3 + 2(a(n-4))2 + 1(a(n-2))1. If a(n-20) were to be included, it would need to be (10)(a(n-20))(10) and 10s can't be included. So everything must subtract a(n-20) from the total of 2 * a(n-2). For example, a(24) = 3956 = 2 * a(22) - a(4). (End)

Let c(n,k) (1<=k<=n) = number of compositions of n into parts of size <= k (cf. A126198). Then a(n) = Sum_{i=0..floor(n/2)} c(n,9). This follows by consideration of the central term, which may be any of n, n-2, n-4, ..., n-2i, ...; the prefix is then a composition of i into parts of size <= 9. - N. J. A. Sloane Mar 09 2007

From Colin Barker, Feb 14 2013: (Start)

a(n) = 2*a(n-2) - a(n-20) for n > 20.

G.f.: x*(1+2*x-x^9-x^10-x^19) / (1-2*x^2+x^20). (End)

Corrected and extended by Jonathan R. Love, Mar 08 2007

A039671 Row sums up to the main diagonal of the "postage stamp" array (n,m >= 0) defined in A007059.

Original entry on oeis.org

1, 1, 3, 8, 21, 53, 130, 310, 724, 1661, 3757, 8398, 18588, 40800, 88918, 192592, 414907, 889631, 1899554, 4040864, 8567342, 18109698, 38176280, 80278798, 168432854, 352658013, 736977583, 1537420460, 3202035086, 6658948608

Offset: 0

Richard L. Ollerton and Eirwyn L. Ollerton

			a(0)=1, a(1)=0+1=1, a(2)=0+1+2=3, a(3)=0+1+3+4=8.

Cf. A007059.

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[ n, j ], {j, 0, n} ], {n, 0, 30} ]

Conjecture: a(n) = Sum_{k=1..n} A126198(n,k), for n > 0. - L. Edson Jeffery, Nov 29 2013

A181695 Triangle read by rows: T(n,m) = number of solutions x_1 + x_2 + ... + x_k <= n, where 1 <= x_i <= m, and any k >= 1.

Original entry on oeis.org

1, 2, 3, 3, 6, 7, 4, 11, 14, 15, 5, 19, 27, 30, 31, 6, 32, 51, 59, 62, 63, 7, 53, 95, 115, 123, 126, 127, 8, 87, 176, 223, 243, 251, 254, 255, 9, 142, 325, 431, 479, 499, 507, 510, 511, 10, 231, 599, 832, 943, 991, 1011, 1019, 1022, 1023, 11, 375, 1103, 1605

Offset: 1

Max Alekseyev, Nov 17 2010

			Triangle begins:
  1;
  2,   3;
  3,   6,   7;
  4,  11,  14,  15;
  5,  19,  27,  30,  31;
  6,  32,  51,  59,  62,  63;
  7,  53,  95, 115, 123, 126, 127;
  ...
Could also be extended to a square array:
  1,   1,   1,   1,   1,   1,   1, ...
  2,   3,   3,   3,   3,   3,   3, ...
  3,   6,   7,   7,   7,   7,   7, ...
  4,  11,  14,  15,  15,  15,  15, ...
  5,  19,  27,  30,  31,  31,  31, ...
  6,  32,  51,  59,  62,  63,  63, ...
  7,  53,  95, 115, 123, 126, 127, ...

Cf. A001911 (second column), A027084 (third column), A126198.

{ T(n,m) = sum(i=0, n\(m+1), binomial(n-m*i,i) * (-1)^i * 2^(n-(m+1)*i) ) - 1 }

For a fixed m, generating function is 1/(1-2*x+x^(m+1)) - 1/(1-x).
T(n,m) = Sum_{i=0..floor(n/(m+1))} binomial(n-mi, i)*(-1)^i*2^(n-(m+1)i) - 1.
T(n,m) = 2^m - 1 + Sum_{j=m+1..n} A126198(j,m).

A185722 Triangle read by rows: The number of m-path covers of the n-cycle C_n.

Original entry on oeis.org

1, 1, 3, 1, 4, 7, 1, 7, 11, 15, 1, 11, 21, 26, 31, 1, 18, 39, 51, 57, 63, 1, 29, 71, 99, 113, 120, 127, 1, 47, 131, 191, 223, 239, 247, 255, 1, 76, 241, 367, 439, 475, 493, 502, 511, 1, 123, 443, 708, 863, 943, 983, 1003, 1013, 1023

Offset: 1

John P. McSorley, Jul 10 2012

Let c_m(n) be the number of m-path covers of the n-cycle C_n. Then form the triangle where c_m(n) is the (n,m) entry. This sequence is this triangle when read by rows, for n >= 1 and 1 <= m <= n.

			The triangle begins:
  1,
  1,   3;
  1,   4,   7;
  1,   7,  11,  15;
  1,  11,  21,  26,  31;
  1,  18,  39,  51,  57,  63;
  1,  29,  71,  99, 113, 120, 127;
  1,  47, 131, 191, 223, 239, 247,  255;
  1,  76, 241, 367, 439, 475, 493,  502,  511;
  1, 123, 443, 708, 863, 943, 983, 1003, 1013, 1023;
An m-path cover of a graph G is a covering of the vertices of G by paths of length at most m.
The length of a path is the number of vertices in it. Let C_4 have vertices {1, 2, 3, 4} then c_3(4) = 11 because C_4 has 11 3-path covers: 1, 2, 3, 4; 12, 3, 4; 23, 1, 4; 34, 1, 2; 14, 2, 3; 12, 34; 14, 23; 123, 4; 234, 1; 143, 2; 214, 3. Here an m-path and its reverse are considered to be the same m-path.
If we include the starting conditions c_m(i) = 2^i - 1, 1 <= i <= m, we get the following square:
  1,   1,   1,   1,   1,   1,   1,    1,    1,    1 ...
  1,   3,   3,   3,   3,   3,   3,    3,    3,    3 ...
  1,   4,   7,   7,   7,   7,   7,    7,    7,    7 ...
  1,   7,  11,  15,  15,  15,  15,   15,   15,   15 ...
  1,  11,  21,  26,  31,  31,  31,   31,   31,   31 ...
  1,  18,  39,  51,  57,  63,  63,   63,   63,   63 ...
  1,  29,  71,  99, 113, 120, 127,  127,  127,  127 ...
  1,  47, 131, 191, 223, 239, 247,  255,  255,  255 ...
  1,  76, 241, 367, 439, 475, 493,  502,  511,  511 ...
  1, 123, 443, 708, 863, 943, 983, 1003, 1013, 1023 ...
  ...
Column m of the above square is formed from an m-anacci recurrence.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
John P. McSorley and Philip Feinsilver, The m-Path Cover Polynomial of a Graph and a Model for General Coefficient Linear Recurrences, International Journal of Combinatorics, Volume 2014 (2014), Article ID 258017, 13 pages.

The (n, m) entry of the triangle formed from sequence A126198 counts the compositions of the integer n in which each part is at most m. In our terminology this is the number of m-path covers of the path P_n with n vertices. The (m, m) term in the triangle formed from sequence A126198 is 2^(m - 1), in our triangle above the (m, m) term is 2^m - 1. Column m of the corresponding square of sequence A126198 also obeys an m-anacci recurrence, as above. Each of the 10 columns of the above square array appears as a sequence: for example, the second column (m = 2) is sequence A000204, and the third column (m = 3) is sequence A001644, etc.

Cf. A247505.

\\ after Maple in A247505
T(n,m)=(-1)^n * polcoeff(Pol(deriv(log((1+sum(j=1, m, (-1)^(j+1)*x^j + O(x^(n+1))))^(-1)))), n-1);
for(n=1, 10, for(m=1, n, print1(T(n,m), ", ")); print) \\ Andrew Howroyd, Oct 08 2017

T(n,m) = A247505(m, n). - Andrew Howroyd, Oct 08 2017

Terms a(37) and beyond from Andrew Howroyd, Oct 08 2017

Showing 1-8 of 8 results.

cp's OEIS Frontend

A048004 Triangular array read by rows: T(n,k) = number of binary vectors of length n whose longest run of consecutive 1's has length k, for n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Sage

Formula

Extensions

A092921 Array F(k, n) read by descending antidiagonals: k-generalized Fibonacci numbers in row k >= 1, starting (0, 1, 1, ...), for column n >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

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

A175331 Array A092921(n,k) without the first two rows, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A082267 Number of palindromes that use nonzero digits and have a digit sum of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

A039671 Row sums up to the main diagonal of the "postage stamp" array (n,m >= 0) defined in A007059.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula