login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 13
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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

REFERENCES

J. Kappraff, Beyond Measure, World Scientific, 2002; see pp. 471-472.

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

LINKS

Alois P. Heinz, Rows n = 0..140, flattened

FORMULA

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

EXAMPLE

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.

MAPLE

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

MATHEMATICA

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 *)

PROG

(Sage)

# 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 q 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

CROSSREFS

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.

Sequence in context: A106396 A282869 A140998 * A114394 A059623 A140997

Adjacent sequences:  A048001 A048002 A048003 * A048005 A048006 A048007

KEYWORD

nonn,tabl,nice

AUTHOR

Clark Kimberling

EXTENSIONS

More terms from Emeric Deutsch, Apr 01 2005

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified April 24 00:59 EDT 2017. Contains 285338 sequences.