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

A379151 The binary weights of the Catalan numbers (A000108).

Original entry on oeis.org

1, 1, 1, 2, 3, 3, 2, 6, 6, 9, 6, 8, 8, 12, 9, 16, 13, 17, 12, 17, 13, 18, 15, 25, 20, 17, 20, 24, 28, 25, 26, 25, 25, 32, 27, 34, 29, 32, 33, 29, 35, 29, 31, 36, 35, 44, 44, 49, 40, 46, 48, 44, 38, 50, 43, 44, 46, 47, 55, 50, 52, 58, 59, 60, 65, 68, 56, 62, 68

Offset: 0

Amiram Eldar, Dec 16 2024

			a(10) = 6 because Catalan(10) = 16796 = 100000110011100_2, which has 6 one bits. - _Vincenzo Librandi_, Feb 05 2025

Amiram Eldar, Table of n, a(n) for n = 0..10000
Amiram Eldar, Plot of (1/n^2) * Sum_{k=1..n} a(k) for n = 2^(8..23).
Florian Luca and Igor E. Shparlinski, On the g-ary expansions of middle binomial coefficients and Catalan numbers, The Rocky Mountain Journal of Mathematics, Vol. 41, No. 4 (2011), pp. 1291-1301.

Cf. A000102, A000108.

Similar sequences: A011373, A079584, A082481, A379152, A379153.

[&+Intseq(Catalan(n), 2): n in [0..100]]; // Vincenzo Librandi, Feb 05 2025

a[n_] := DigitCount[CatalanNumber[n], 2, 1]; Array[a, 100, 0]

a(n) = hammingweight(binomial(2*n, n)/(n+1));

a(n) = A000120(A000108(n)).
Two formulas from Luca and Shparlinski (2011):
a(n) >= 3 for all but finitely many positive integers n.
a(n) >> eps(n) * sqrt(log(n)), for all n <= X with at most o(X) exceptions as X -> oo, where eps(n) is a function tending to zero as n -> oo.
Conjecture: Sum_{k=1..n} a(k) ~ n^2 / 2 (see the plot in the Links section).

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

A379151 The binary weights of the Catalan numbers (A000108).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula