A105422 - OEIS

%I #75 Sep 26 2024 09:42:59

%S 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,

%T 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,

%U 85,48,35,8,9,0,1,55,139,199,209,170,125,63,44,9,10,0,1,89,240,366,404,360

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

%C 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

%C 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

%C Also the convolution triangle of Fibonacci(n-2). # _Peter Luschny_, Oct 07 2022

%C 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

%C 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

%H Alois P. Heinz, <a href="/A105422/b105422.txt">Rows n = 0..140, flattened</a>

%H D. Baccherini, D. Merlini and R. Sprugnoli, <a href="http://pefmath.etf.rs/vol2num1/AADM-Vol2-No1-69-91.pdf">Level generating trees and proper Riordan arrays</a>, Applicable Analysis and Discrete Mathematics, 2, 2008, 69-91 (see p. 83). [_Emeric Deutsch_, Sep 21 2008]

%H Jia Huang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Huang/huang8.html">Partially Palindromic Compositions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 10-11.

%H Milan Janjić, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Janjic/janjic93.html">Words and Linear Recurrences</a>, J. Int. Seq. 21 (2018), #18.1.4.

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

%F 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

%F 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

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

%e Triangle begins:

%e 00:    1;

%e 01:    0,   1;

%e 02:    1,   0,   1;

%e 03:    1,   2,   0,   1;

%e 04:    2,   2,   3,   0,   1;

%e 05:    3,   5,   3,   4,   0,   1;

%e 06:    5,   8,   9,   4,   5,   0,   1;

%e 07:    8,  15,  15,  14,   5,   6,   0,   1;

%e 08:   13,  26,  31,  24,  20,   6,   7,   0,  1;

%e 09:   21,  46,  57,  54,  35,  27,   7,   8,  0,  1;

%e 10:   34,  80, 108, 104,  85,  48,  35,   8,  9,  0,  1;

%e 11:   55, 139, 199, 209, 170, 125,  63,  44,  9, 10,  0,  1;

%e 12:   89, 240, 366, 404, 360, 258, 175,  80, 54, 10, 11,  0, 1;

%e 13:  144, 413, 666, 780, 725, 573, 371, 236, 99, 65, 11, 12, 0, 1;

%e ...

%p 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

%p # second Maple program:

%p T:= proc(n) option remember; local j; if n=0 then 1

%p       else []; for j to n do zip((x, y)-> x+y, %,

%p       [`if`(j=1, 0, [][]), T(n-j)], 0) od; %[] fi

%p     end:

%p seq(T(n), n=0..20);  # _Alois P. Heinz_, Nov 05 2012

%p # Uses function PMatrix from A357368. Adds a row above and a column to the left.

%p PMatrix(10, n -> combinat:-fibonacci(n-2)); # _Peter Luschny_, Oct 07 2022

%t nn = 10; a = x/(1 - x) - x + y x;

%t CoefficientList[CoefficientList[Series[1/(1 - a), {x, 0, nn}], x], y] // Flatten (* _Geoffrey Critzer_, Dec 23 2011 *)

%t 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 *)

%o (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 */

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

%Y T(2n,n) gives A222763.

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_, Apr 07 2005