login
The OEIS is supported by the many generous donors 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. 26

%I #117 Apr 07 2020 11:37:22

%S 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,

%T 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,

%U 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

%N 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.

%C 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

%C 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

%C 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

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

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

%H Alois P. Heinz, <a href="/A048004/b048004.txt">Rows n = 0..140, flattened</a>

%H Richard Southern, <a href="/A048004/a048004.py.txt">Python program</a>

%H J. L. Yucas, <a href="/A006980/a006980.pdf">Counting special sets of binary Lyndon words</a>, Ars Combin., 31 (1991), 21-29. (Annotated scanned copy)

%F 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_

%F T(n, k) = A048887(n+1, k+1) - A048887(n+1, k). - _Henry Bottomley_, Oct 29 2002

%F 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

%F From _Gary W. Adamson_, Jun 23 2012: (Start)

%F 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:

%F 1, 1, 1, 1, 1, 1, ...

%F 1, 2, 3, 5, 8, 13, ...

%F 1, 2, 4, 7, 13, 24, ...

%F 1, 2, 4, 8, 15, 29, ...

%F ... Then, take finite differences of column terms from the top -> down. Row terms of the triangle are finite differences of the array columns. (End)

%F T(n,k) = A126198(n+1,k+1) - A126198(n+1,k). - _L. Edson Jeffery_, May 21 2013

%F 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

%F 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

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 1, 4, 2, 1;

%e 1, 7, 5, 2, 1;

%e 1, 12, 11, 5, 2, 1;

%e 1, 20, 23, 12, 5, 2, 1;

%e 1, 33, 47, 27, 12, 5, 2, 1;

%e 1, 54, 94, 59, 28, 12, 5, 2, 1;

%e 1, 88, 185, 127, 63, 28, 12, 5, 2, 1;

%e ...

%e Example: T(4,2) = 5 because we have 1100, 1101, 0110, 0011, 1011.

%p 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

%p # second Maple program:

%p B:= proc(n, k) option remember; `if`(n=0 or k=1, 1,

%p add (B(n-j, k), j=1..min(n, k)))

%p end:

%p T:= (n, k)-> B(n+1, k+1)-B(n+1, k):

%p seq(seq(T(n, k), k=0..n), n=0..14); # _Alois P. Heinz_, May 21 2013

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

%t 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_ *)

%o (Sage)

%o # Computes the triangle obtained by augmenting T(n,k) by appending the column

%o # 1,0,0,0,... on the left. Illustrates a basic partition formula, is not

%o # efficient as a program for large n.

%o def A048004_row(n):

%o r = []

%o for k in (0..n):

%o s = 0

%o for p in Partitions(n, max_part=k, inner=[k]):

%o q = p.conjugate()

%o s += mul(binomial(q[j],q[j+1]) for j in range(len(q)-1))

%o r.append(s)

%o return r

%o [A048004_row(n) for n in (0..9)] # _Peter Luschny_, Jul 13 2015

%o (Python) # See Richard Southern link.

%o (Haskell)

%o tri n k | (k < 0) || (k > n) = 0

%o | (k == 0) || (k == n) = 1

%o | otherwise = 2*tri (n-1) k + tri (n-1) (k-1) - 2*tri (n-2) (k-1)

%o + tri (n-k-1) (k-1) - tri (n-k-2) k

%o -- _Valentin Hübner_, Jul 20 2017, after _David W. Wilson_

%Y See A126198 and A048887 for closely related arrays.

%Y 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.

%Y Nonnegative elements of columns approach A045623.

%Y Cf. A048003, A097805.

%K nonn,tabl,nice

%O 0,5

%A _Clark Kimberling_

%E More terms from _Emeric Deutsch_, Apr 01 2005

%E Edited by _N. J. A. Sloane_, Apr 03 2011

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)