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, Python program
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
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)
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 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
(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
KEYWORD
AUTHOR
EXTENSIONS
More terms from Emeric Deutsch, Apr 01 2005
Edited by N. J. A. Sloane, Apr 03 2011
STATUS
approved