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

Author

Emeric Deutsch, Apr 07 2005

Keywords

• nonn
• tabl

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

T(n,k) is the number of length n+1 bit strings beginning and ending with 0 having k length 2 substrings 00. This is equivalent to the compositions interpretation because each m part corresponds to a length m+1 bit string beginning with 0 and ending with the next 0 bit. Thus a substring 00 corresponds to a 1 part. Example: T(4,2)=3 because we have 00010 for 112, 00100 for 121 and 01000 for 211. - Michael Somos, Sep 24 2024

In the Baccherini et al. 2008 link on page 81: "Bloom[3] studies the number of singles in all the 2^n n-length bit strings, where a single is any isolated 1 or 0, i.e., any run of length 1. Let R_{n,k} be the number of n-length bit strings beginning with 0 and having k singles." Here T(n,k) = R_{n,k}. This combinatorial interpretation is equivalent to my previous comment since a part of size k corresponds to run of k identical bits and also to a length k+1 bit string with 0s only at the beginning and end. - Michael Somos, Sep 25 2024

Examples

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

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.

Crossrefs

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

T(2n,n) gives A222763.

Programs

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 *)
T[ n_, k_] := Which[k<0 || k>n, 0, n<2, Boole[n==k], True, T[n, k] =  T[n-1, k] + T[n-1, k-1] + T[n-2, k] - T[n-2, k-1] ]; (* Michael Somos, Sep 24 2024 *)

PARI

{T(n, k) = if(k<0 || k>n, 0, n<2, n==k, T(n-1, k) + T(n-1, k-1) + T(n-2, k) - T(n-2, k-1) )}; /* Michael Somos, Sep 24 2024 */

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