A180184 - OEIS

%I #62 Feb 19 2022 14:24:32

%S 1,1,1,1,1,1,1,2,1,3,1,4,1,5,1,1,6,3,1,7,6,1,8,10,1,9,15,1,1,10,21,4,

%T 1,11,28,10,1,12,36,20,1,13,45,35,1,1,14,55,56,5,1,15,66,84,15,1,16,

%U 78,120,35,1,17,91,165,70,1,1,18,105,220,126,6,1,19,120,286,210,21,1,20

%N Irregular triangle read by rows: T(n,k) is the number of compositions of n with k parts, all >= 4, for n >= 4 and 1 <= k <= floor(n/4).

%C Sum of the entries in row n is A003269(n-3).

%C Row n contains floor(n/4) entries.

%C From _Petros Hadjicostas_, Apr 15 2020: (Start)

%C From equations (3) and (23) in Mathar (2016), we have Sum_{m,k >= 0} T_{4 x m}(4,k)*z^m*t^k = 1/(1 - z - z^4*t), where T_{4xm}(4,k) counts the ways of tiling the 4 x m rectangle with k non-overlapping squares of shape 4 x 4 and with 4*m - 16*k unit squares (see Definition 1 in his paper for more details).

%C By expanding 1/(1 - (z + z^4*t)) as an infinite geometric series, using the binomial theorem, and changing indices of summation, we may show that T_{4xm}(4,k) = binomial(m - 3*k, k) = T(m+4, k+1) for m >= 0 and 0 <= k <= floor(m/4) (where the current array T(n,k) should be distinguished from Mathar's T_{4 x m}(4,k)).

%C Indeed, we have a bijection between the above tilings of the 4 x m rectangle with k non-overlapping squares of shape 4 x 4 and 4*m - 16*k unit squares and the compositions of m+4 with k+1 parts, all >= 4. To construct the bijection, let us agree that an a x b rectangle has height a and base b.

%C Given such a composition, a_1 + a_2 + ... + a_{k+1} = m + 4 (with a_i >= 4), paste together a 4 x 4 square followed by a_1 - 4 columns of 4 unit squares, another 4 x 4 square followed by a_2 - 4 columns of 4 units squares, and so on, and finally a 4 x 4 square followed by a_{k+1} - 4 columns of 4 unit squares. Remove the first 4 x 4 square, and we get a tiling of the 4 x m rectangle with k 4 x 4 squares and 4*Sum_{i=1..(k+1)} (a_i - 4) = 4*(m+4) - 16*(k+1) = 4*m - 16*k unit squares.

%C The above process can be reversed to complete the bijection, but we omit the details. (End)

%C T(n+7,k+1) is the number of k-subsets of {1..n} with values at least 4 apart. For example, T(17,4) = 4 corresponds to the subsets {1,5,9},{1,5,10},{1,6,10},{2,6,10} of {1..10} (A102547 gives the number of k-subsets of {1..n} with values at least 3 apart and A011973 with values at least 2 apart). - _Enrique Navarrete_, Jan 29 2022

%H R. J. Mathar, <a href="http://arxiv.org/abs/1609.03964">Tiling n x m rectangles with 1 x 1 and s x s squares</a>, arXiv:1609.03964 [math.CO] (2016), Section 4.3.

%F T(n, k) = binomial(n-3*k-1, k-1).

%F T(n, k) = A228572(2*n-4, 2*k-1) + A228572(2*n-7, 2*k-2) - A228572(2*n-3, 2*k-1) for n >= 4 and 1 <= k <= floor(n/4). - _Johannes W. Meijer_, Aug 26 2013 [Range of k adjusted by _Petros Hadjicostas_, Apr 15 2020 to start at 1 rather than 0]

%F G.f.: Sum_{n,k} T(n,k)*z^n*t^k = z^4*t/(1-z-t*z^4). - _R. J. Mathar_, Aug 24 2016 [Adjusted by _Petros Hadjicostas_, Apr 14 2020 to agree with the offset]

%e Triangle T(n,k) (with n >= 4 and 1 <= k <= floor(n/4)) starts as follows:

%e   1;

%e   1;

%e   1;

%e   1;

%e   1,  1;

%e   1,  2;

%e   1,  3;

%e   1,  4;

%e   1,  5,  1;

%e   1,  6,  3;

%e   1,  7,  6;

%e   1,  8, 10;

%e   1,  9, 15,  1;

%e   1, 10, 21,  4;

%e   1, 11, 28, 10;

%e   1, 12, 36, 20;

%e   ...

%e T(14,3) = 6 because we have the following compositions (ordered partitions) of 14 with 3 parts, all >= 4: [5,5,4], [4,6,4], [5,4,5], [6,4,4], [4,5,5], [4,4,6].

%p for n from 4 to 27 do seq(binomial(n-3*k-1, k-1), k = 1 .. floor((1/4)*n)) end do;

%p T := (n,k) -> binomial(n-3*k-1, k-1): seq(seq(T(n,k), k=1..floor(n/4)), n=4..26); # _Johannes W. Meijer_, Aug 26 2013

%t Flatten[Table[Binomial[n-3k-1,k-1],{n,4,30},{k,Floor[n/4]}]] (* _Harvey P. Dale_, Feb 05 2013 *)

%Y Cf. A003269, A102547, A228572.

%K nonn,tabf,easy

%O 4,8

%A _Emeric Deutsch_, Aug 15 2010