

A180184


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


1



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, 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, 78, 120, 35, 1, 17, 91, 165, 70, 1, 1, 18, 105, 220, 126, 6, 1, 19, 120, 286, 210, 21, 1, 20
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

4,8


COMMENTS

Sum of the entries in row n is A003269(n3).
Row n contains floor(n/4) entries.
From Petros Hadjicostas, Apr 15 2020: (Start)
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 nonoverlapping squares of shape 4 x 4 and with 4*m  16*k unit squares (see Definition 1 in his paper for more details).
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)).
Indeed, we have a bijection between the above tilings of the 4 x m rectangle with k nonoverlapping 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.
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.
The above process can be reversed to complete the bijection, but we omit the details. (End)


LINKS

Table of n, a(n) for n=4..83.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO] (2016), Section 4.3.


FORMULA

T(n, k) = binomial(n3*k1, k1).
T(n, k) = A228572(2*n4, 2*k1) + A228572(2*n7, 2*k2)  A228572(2*n3, 2*k1) 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]
G.f.: Sum_{n,k} T(n,k)*z^n*t^k = z^4*t/(1zt*z^4).  R. J. Mathar, Aug 24 2016 [Adjusted by Petros Hadjicostas, Apr 14 2020 to agree with the offset]


EXAMPLE

Triangle T(n,k) (with n >= 4 and 1 <= k <= floor(n/4)) starts as follows:
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;
1, 11, 28, 10;
1, 12, 36, 20;
...
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].


MAPLE

for n from 4 to 27 do seq(binomial(n3*k1, k1), k = 1 .. floor((1/4)*n)) end do;
T := (n, k) > binomial(n3*k1, k1): seq(seq(T(n, k), k=1..floor(n/4)), n=4..26); # Johannes W. Meijer, Aug 26 2013


MATHEMATICA

Flatten[Table[Binomial[n3k1, k1], {n, 4, 30}, {k, Floor[n/4]}]] (* Harvey P. Dale, Feb 05 2013 *)


CROSSREFS

Cf. A003269, A102547, A228572.
Sequence in context: A324933 A085343 A049077 * A330752 A222266 A077609
Adjacent sequences: A180181 A180182 A180183 * A180185 A180186 A180187


KEYWORD

nonn,tabf,easy


AUTHOR

Emeric Deutsch, Aug 15 2010


STATUS

approved



