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

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

Author

Geoffrey Critzer, Nov 05 2012

Keywords

• nonn
• tabf

Comments

Row Sums = 2^(n-1) for n>0.

Examples

			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;
		

Links

• Alois P. Heinz, Rows n = 0..250, flattened
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 168.

Crossrefs

Cf. A105114, A045623, A011782.

Column k=0 gives: A049856(n+2).

Programs

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

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