This site is supported by donations to The OEIS Foundation.

 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 Richard Southern, PythonMatrix J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29. (Annotated scanned copy) 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 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 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 (Python) See Richard Southern link. (Haskell) 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 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 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.

Last modified August 15 07:26 EDT 2018. Contains 313756 sequences. (Running on oeis4.)