login
A218796
Triangular array read by rows: T(n,k) is the number of compositions of n that have exactly k 3's; n>=0, 0<=k<=floor(n/3).
2
1, 1, 2, 3, 1, 6, 2, 11, 5, 21, 10, 1, 39, 22, 3, 73, 46, 9, 136, 97, 22, 1, 254, 200, 54, 4, 474, 410, 126, 14, 885, 832, 290, 40, 1, 1652, 1679, 651, 109, 5, 3084, 3368, 1440, 280, 20, 5757, 6725, 3138, 698, 65, 1, 10747, 13370, 6762, 1688, 195, 6, 20062, 26483, 14424, 3994, 546, 27
OFFSET
0,3
COMMENTS
Row Sums = 2^(n-1) for n>0.
LINKS
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 168.
FORMULA
O.g.f.: 1/(1-(x/(1-x)-x^3+y*x^3)) and generally for the number of compositions with k parts of size r we have: 1/(1-(x/(1-x)-x^r+y*x^r)).
EXAMPLE
1;
1;
2;
3, 1;
6, 2;
11, 5;
21, 10, 1;
39, 22, 3;
73, 46, 9;
136, 97, 22, 1;
254, 200, 54, 4;
474, 410, 126, 14;
885, 832, 290, 40, 1;
1652, 1679, 651, 109, 5;
3084, 3368, 1440, 280, 20;
5757, 6725, 3138, 698, 65, 1;
MAPLE
T:= proc(n) option remember; local j; if n=0 then 1
else []; for j to n do zip((x, y)-> x+y, %,
[`if`(j=3, 0, [][]), T(n-j)], 0) od; %[] fi
end:
seq (T(n), n=0..25); # Alois P. Heinz, Nov 05 2012
MATHEMATICA
nn=15; f[list_]:=Select[list, #>0&]; Map[f, CoefficientList[Series[1/(1-(x/(1-x)-x^3+y x^3)), {x, 0, nn}], {x, y}]]//Grid
CROSSREFS
Column k=0 gives: A049856(n+2).
Sequence in context: A062565 A175137 A156344 * A119440 A165742 A162984
KEYWORD
nonn,tabf
AUTHOR
Geoffrey Critzer, Nov 05 2012
STATUS
approved