

A105422


Triangle read by rows: T(n,k) is the number of compositions of n having exactly k parts equal to 1.


8



1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 2, 2, 3, 0, 1, 3, 5, 3, 4, 0, 1, 5, 8, 9, 4, 5, 0, 1, 8, 15, 15, 14, 5, 6, 0, 1, 13, 26, 31, 24, 20, 6, 7, 0, 1, 21, 46, 57, 54, 35, 27, 7, 8, 0, 1, 34, 80, 108, 104, 85, 48, 35, 8, 9, 0, 1, 55, 139, 199, 209, 170, 125, 63, 44, 9, 10, 0, 1, 89, 240, 366, 404, 360
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,8


COMMENTS

T(n,k) is also the number of length n bit strings beginning with 0 having k singletons. Example: T(4,2)=3 because we have 0010, 0100 and 0110.  Emeric Deutsch, Sep 21 2008
The cyclic version of this array is A320341(n,k), which counts the (unmarked) cyclic compositions of n with exactly k parts equal to 1, with a minor exception for k=0. The sequence (A320341(n, k=0)  1: n >= 1) counts the (unmarked) cyclic compositions of n with no parts equal to 1.  Petros Hadjicostas, Jan 08 2019
Also the convolution triangle of Fibonacci(n2). # Peter Luschny, Oct 07 2022


LINKS



FORMULA

G.f.: (1z)/(1  z  z^2  tz + tz^2).
T(n,k) = T(n1,k) + T(n2,k) + T(n1,k1)  T(n2,k1), T(0,0)=1, T(1,0)=0.  Philippe Deléham, Nov 18 2009
If the triangle's columns are transposed into rows, then T(n,k) can be interpreted as the number of compositions of n+k having exactly k 1's. Then g.f.: ((1x)/(1xx^2))^(k1) and T(n,k) = T(n2,k) + T(n1,k)  T(n1, k1) + T(n, k1). Also, Sum_{j=1..n} T(nj, j) = 2^(n1), the number of compositions of n.  Gregory L. Simay, Jun 28 2019


EXAMPLE

T(6,2) = 9 because we have (1,1,4), (1,4,1), (4,1,1), (1,1,2,2), (1,2,1,2), (1,2,2,1), (2,1,1,2), (2,1,2,1) and (2,2,1,1).
Triangle begins:
00: 1;
01: 0, 1;
02: 1, 0, 1;
03: 1, 2, 0, 1;
04: 2, 2, 3, 0, 1;
05: 3, 5, 3, 4, 0, 1;
06: 5, 8, 9, 4, 5, 0, 1;
07: 8, 15, 15, 14, 5, 6, 0, 1;
08: 13, 26, 31, 24, 20, 6, 7, 0, 1;
09: 21, 46, 57, 54, 35, 27, 7, 8, 0, 1;
10: 34, 80, 108, 104, 85, 48, 35, 8, 9, 0, 1;
11: 55, 139, 199, 209, 170, 125, 63, 44, 9, 10, 0, 1;
12: 89, 240, 366, 404, 360, 258, 175, 80, 54, 10, 11, 0, 1;
13: 144, 413, 666, 780, 725, 573, 371, 236, 99, 65, 11, 12, 0, 1;
...


MAPLE

G:=(1z)/(1zz^2t*z+t*z^2): Gser:=simplify(series(G, z=0, 15)): P[0]:=1: for n from 1 to 14 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 13 do seq(coeff(t*P[n], t^k), k=1..n+1) od; # yields sequence in triangular form
# second Maple program:
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=1, 0, [][]), T(nj)], 0) od; %[] fi
end:
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, n > combinat:fibonacci(n2)); # Peter Luschny, Oct 07 2022


MATHEMATICA

nn = 10; a = x/(1  x)  x + y x;
CoefficientList[CoefficientList[Series[1/(1  a), {x, 0, nn}], x], y] // Flatten (* Geoffrey Critzer, Dec 23 2011 *)


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



