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

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

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(n-2). # Peter Luschny, Oct 07 2022

Links

Alois P. Heinz, Rows n = 0..140, flattened

D. Baccherini, D. Merlini and R. Sprugnoli, Level generating trees and proper Riordan arrays, Applicable Analysis and Discrete Mathematics, 2, 2008, 69-91 (see p. 83). [Emeric Deutsch, Sep 21 2008]

Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 10-11.

Milan Janjić, Words and Linear Recurrences, J. Int. Seq. 21 (2018), #18.1.4.

Formula

G.f.: (1-z)/(1 - z - z^2 - tz + tz^2).

T(n,k) = T(n-1,k) + T(n-2,k) + T(n-1,k-1) - T(n-2,k-1), 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.: ((1-x)/(1-x-x^2))^(k-1) and T(n,k) = T(n-2,k) + T(n-1,k) - T(n-1, k-1) + T(n, k-1). Also, Sum_{j=1..n} T(n-j, j) = 2^(n-1), 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:=(1-z)/(1-z-z^2-t*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(n-j)], 0) od; %[] fi
    end:
seq(T(n), n=0..20);  # Alois P. Heinz, Nov 05 2012
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, n -> combinat:-fibonacci(n-2)); # 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

Column 0 yields A000045 (the Fibonacci numbers). Column 1 yields A006367. Column 2 yields A105423. Row sums yield A011782. Cyclic version is A320341.

Sequence in context: A029275 A058739 A128627 * A166291 A162986 A319203

Adjacent sequences: A105419 A105420 A105421 * A105423 A105424 A105425

Keyword

nonn,tabl

Author

Emeric Deutsch, Apr 07 2005

Status

approved