A000100 -id:A000100 - 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

A006980 Compositions: 6th column of A048004.

Original entry on oeis.org

1, 2, 5, 12, 28, 64, 143, 315, 687, 1485, 3186, 6792, 14401, 30391, 63872, 133751, 279177, 581040, 1206151, 2497895, 5161982, 10646564, 21919161, 45052841, 92461171, 189489255, 387830160, 792810956, 1618840800, 3301999647

Offset: 6

Simon Plouffe

a(n) is the number of binary strings of length n-1 whose longest run of 1s has length 5. - Félix Balado, May 20 2025

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29.

Alois P. Heinz, Table of n, a(n) for n = 6..1000
J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29. (Annotated scanned copy)
Index entries for linear recurrences with constant coefficients, signature (2,1,0,-1,-2,-4,-5,-4,-3,-2,-1).

Cf. A048004, A006979, A000102, A000100, A000071.

a:= n-> (Matrix(11, (i,j)-> if i=j-1 then 1 elif j=1 then [2, 1, 0, -1, -2, -4, -5, -4, -3, -2, -1][i] else 0 fi)^n) [1,7]: seq(a(n), n=6..40); # Alois P. Heinz, Oct 29 2008

Vec(1/(1-x-x^2-x^3-x^4-x^5)/(1-x-x^2-x^3-x^4-x^5-x^6)+O(x^99)) \\ Charles R Greathouse IV, Jan 10 2013

G.f.: x^6 / ((1-x-x^2-x^3-x^4-x^5) * (1-x-x^2-x^3-x^4-x^5-x^6)). - Alois P. Heinz, Oct 29 2008

G.f.: x^6 * (1-x)^2 / ((1-2*x+x^6) * (1-2*x+x^7)). - Félix Balado, May 20 2025

Corrected definition: 6th column of A048004. - Geoffrey Critzer, Nov 09 2008

A048003 Triangular array T read by rows: T(h,k) = number of binary words of length h and maximal runlength k.

Original entry on oeis.org

2, 2, 2, 2, 4, 2, 2, 8, 4, 2, 2, 14, 10, 4, 2, 2, 24, 22, 10, 4, 2, 2, 40, 46, 24, 10, 4, 2, 2, 66, 94, 54, 24, 10, 4, 2, 2, 108, 188, 118, 56, 24, 10, 4, 2, 2, 176, 370, 254, 126, 56, 24, 10, 4, 2, 2, 286, 720, 538, 278, 128, 56, 24, 10, 4, 2, 2, 464, 1388, 1126, 606, 286, 128, 56, 24, 10, 4, 2

Offset: 1

Clark Kimberling

			Rows: {2}; {2,2}; {2,4,2}; {2,8,4,2}; ...
T(3,2) = 4, because there are 4 binary words of length 3 and maximal runlength 2: 001, 011, 100, 110. - _Alois P. Heinz_, Oct 29 2008

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

T(h,2) = 2*a(h+1) for h=2, 3, ..., where a=A000071.
T(h,3) = 2*b(h) for h=3, 4, ..., where b=A000100.
T(h,4) = 2*c(h) for h=4, 5, ..., where c=A000102.
Cf. A048004.
Columns 5, 6 give: 2*A006979, 2*A006980. Row sums give: A000079.
Cf. A229756.

gf:= proc(n) 2*x^n/ (1-add(x^i, i=1..n-1))/ (1-add(x^j, j=1..n)) end:
T:= (h,k)-> coeff(series(gf(k), x, h+1), x, h):
seq(seq(T(h,k), k=1..h), h=1..13);  # Alois P. Heinz, Oct 29 2008

gf[n_] := 2*x^n*(x^2-2*x+1) / (x^(2*n+1)-2*x^(n+2)-x^(n+1)+x^n+4*x^2-4*x+1); t[h_, k_] := Coefficient[ Series[ gf[k], {x, 0, h+1}], x, h]; Table[ Table[ t[h, k], {k, 1, h}], {h, 1, 13}] // Flatten (* Jean-François Alcover, Oct 07 2013, after Alois P. Heinz *)

G.f. of column k: 2*x^k / ((1-Sum_{i=1..k-1} x^i) * (1-Sum_{j=1..k} x^j)). - Alois P. Heinz, Oct 29 2008
T(n, k) = 0 if k < 1 or k > n, 2 if k = 1 or k = n, 2T(n-1, k) + T(n-1, k-1) - 2T(n-2, k-1) + T(n-k, k-1) - T(n-k-1, k) otherwise (cf. similar formula for A048004). This is a simplification of the L-shaped sum T(n-1, k) + ... + T(n-k, k) + ... + T(n-k,1). - Andrew Woods, Oct 11 2013
For n > 2k, T(n, n-k) = 2*A045623(k). - Andrew Woods, Oct 11 2013

More terms from Alois P. Heinz, Oct 29 2008

A384154 a(n) is the number of binary strings of length n whose shortest run of 1s is of length 2.

Original entry on oeis.org

0, 0, 1, 2, 3, 5, 10, 20, 38, 70, 128, 234, 427, 776, 1404, 2531, 4550, 8161, 14608, 26099, 46550, 82901, 147441, 261913, 464759, 823902, 1459287, 2582615, 4567357, 8072082, 14257631, 25169443, 44410452, 78325112, 138082349, 243339192, 428683436, 754961473

Offset: 0

Félix Balado, May 20 2025

Index entries for linear recurrences with constant coefficients, signature (4,-6,5,-2,-1,1,-1).

Cf. A000100, A384153.

LinearRecurrence[{4,-6,5,-2,-1,1,-1},{0,0,1,2,3,5,10},40] (* Harvey P. Dale, Jun 24 2025 *)

G.f.: x^2 * (1 - x)^2/(((1 - x)^2 - x^3) * ((1 - x)^2 - x^4)).

A112690 Expansion of 1/(1 + x^2 - x^3 - x^5).

Original entry on oeis.org

0, 1, 0, -1, 1, 1, -1, 0, 1, 0, 0, 0, 0, 1, 0, -1, 1, 1, -1, 0, 1, 0, 0, 0, 0, 1, 0, -1, 1, 1, -1, 0, 1, 0, 0, 0, 0, 1, 0, -1, 1, 1, -1, 0, 1, 0, 0, 0, 0, 1, 0, -1, 1, 1, -1, 0, 1, 0, 0, 0, 0, 1, 0, -1, 1, 1, -1, 0, 1, 0, 0, 0, 0, 1, 0, -1, 1, 1, -1, 0, 1, 0, 0, 0, 0, 1, 0, -1, 1, 1, -1, 0, 1, 0, 0, 0, 0, 1, 0, -1

Offset: 0

Paul Barry, Sep 15 2005

Partial sums are A112689.

Index entries for linear recurrences with constant coefficients, signature (0,-1,1,0,1).

Cf. A000100, A057077, A061347, A112689.

LinearRecurrence[{0, -1, 1, 0, 1}, {0, 1, 0, -1, 1}, 100] (* Vincenzo Librandi, Jul 07 2016 *)
Join[{0},CoefficientList[Series[1/(1+x^2-x^3-x^5),{x,0,100}],x]] (* Harvey P. Dale, Jul 30 2024 *)

concat(0, Vec(1/(1+x^2-x^3-x^5) + O(x^80))) \\ Michel Marcus, Jul 07 2016

a(n) = round(real((exp(-2/3*I*n*Pi)*(-4+(3+3*I)*exp((I*n*Pi)/6) + 2*exp((2*I*n*Pi)/3) + (3-3*I)*exp((7*I*n*Pi)/6) - 4*exp((4*I*n*Pi)/3)))/12)) \\ Colin Barker, Jul 07 2016

G.f.: 1/((1+x^2)*(1-x^3)).
a(n) = Sum_{k=0..n} Sum_{j=0..floor((k+1)/2)} (-1)^(k-j)*C(k-j+1, j-1).
a(n+12) = a(n) = 1/6 + A057077(n+1)/2 + A061347(n+1)/3. - R. J. Mathar, Feb 23 2009
a(n+10) = (A000100(n) mod 2)*(-1)^(1 + floor(n/2)). - John M. Campbell, Jul 07 2016
From Ilya Gutkovskiy, Jul 07 2016: (Start)
E.g.f.: (3*sin(x) + 3*cos(x) + exp(x) - 4*exp(-x/2)*cos(sqrt(3)*x/2))/6.
a(n) = (3*sin(Pi*n/2) + 3*cos(Pi*n/2) - 4*cos(2*Pi*n/3) + 1)/6. (End)
a(n) = 2*floor(n/4) + floor((n+2)/3) - floor(n/3) - floor(n/2). - Ridouane Oudra, Mar 11 2023

A182309 Triangle T(n,k) with 2 <= k <= floor(2(n+1)/3) gives the number of length-n binary sequences with exactly k zeros and with length two for the longest run of zeros.

Original entry on oeis.org

1, 2, 3, 2, 4, 6, 1, 5, 12, 6, 6, 20, 18, 3, 7, 30, 40, 16, 1, 8, 42, 75, 50, 10, 9, 56, 126, 120, 45, 4, 10, 72, 196, 245, 140, 30, 1, 11, 90, 288, 448, 350, 126, 15, 12, 110, 405, 756, 756, 392, 90, 5, 13, 132, 550, 1200, 1470, 1008, 357, 50, 1, 14, 156, 726

Offset: 2

Dennis P. Walsh, Apr 23 2012

Triangle T(n,k) captures several well known sequences. In particular, T(n,2)=(n-1), the natural numbers; T(n,3)=(n-2)(n-3)=A002378(n-3), the "oblong" numbers; T(n,4)=(n-3)(n-4)^2/2=A002411(n-4), "pentagonal pyramidal" numbers; and also T(n,5)=(n-4)C(n-4,3)=A004320(n-6). Furthermore, row sums=A000100(n+1).

			For n=6 and k=3, T(6,3)=12 since there are 12 binary sequences of length 6 that contain 3 zeros and that have a maximum run of zeros of length 2, namely, 011100, 101100, 110100, 011001, 101001, 110010, 010011, 100110, 100101, 001110, 001101, and 001011.
Triangle T(n,k) begins
   1,
   2,
   3,   2,
   4,   6,   1,
   5,  12,   6,
   6,  20,  18,    3,
   7,  30,  40,   16,    1,
   8,  42,  75,   50,   10,
   9,  56, 126,  120,   45,    4,
  10,  72, 196,  245,  140,   30,    1,
  11,  90, 288,  448,  350,  126,   15,
  12, 110, 405,  756,  756,  392,   90,    5,
  13, 132, 550, 1200, 1470, 1008,  357,   50,   1,
  14, 156, 726, 1815, 2640, 2268, 1106,  266,  21,
  15, 182, 936, 2640, 4455, 4620, 2898, 1016, 161, 6,

Dennis Walsh, Notes on binary sequences with a maximum run length of two

Row sums of triangle T(n,k)=A000100(n+1);
T(n,3)=A002378(n-3); T(n,4)=A002411(n-4);
T(n,5)=A004320(n-6).

seq(seq(sum(binomial(n-k+1,j)*binomial(n-k+1-j,k-2*j),j=1..floor(k/2)),k=2..floor(2*(n+1)/3)),n=2..20);

t[n_, k_] := Sum[ Binomial[n-k+1, j]*Binomial[n-k-j+1, k-2*j], {j, 1, k/2}]; Table[t[n, k], {n, 2, 15}, {k, 2, 2*(n+1)/3}] // Flatten (* Jean-François Alcover, Jun 06 2013 *)

T(n,k) = Sum_{j=1..k/2} binomial(n-k+1,j)*binomial(n-k-j+1,k-2j) for 2 <= k <= 2(n+1)/3.

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

A006980 Compositions: 6th column of A048004.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A048003 Triangular array T read by rows: T(h,k) = number of binary words of length h and maximal runlength k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A384154 a(n) is the number of binary strings of length n whose shortest run of 1s is of length 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A112690 Expansion of 1/(1 + x^2 - x^3 - x^5).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A182309 Triangle T(n,k) with 2 <= k <= floor(2(n+1)/3) gives the number of length-n binary sequences with exactly k zeros and with length two for the longest run of zeros.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula