|
|
A192933
|
|
Triangle read by rows: T(n,k) = Sum_{i <= n, j <= k, (i,j) <> (n,k)} T(i,j), starting with T(1,1) = 1, for n >= 1 and 1 <= k <= n.
|
|
3
|
|
|
1, 1, 2, 2, 6, 12, 4, 16, 44, 88, 8, 40, 136, 360, 720, 16, 96, 384, 1216, 3152, 6304, 32, 224, 1024, 3712, 11296, 28896, 57792, 64, 512, 2624, 10624, 36416, 108032, 273856, 547712, 128, 1152, 6528, 29056, 109696, 362624, 1056896, 2661504, 5323008, 256, 2560, 15872, 76800, 314880, 1135616, 3659776, 10528768, 26380544, 52761088
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
The second outer diagonal is A090442.
The third outer diagonal is essentially 2*A068766.
The second column is essentially A057711 (not considering its first two terms).
The second column is essentially A129952 (not considering its first two terms).
The second column is essentially 2*A001792.
The differences between the terms of the second column is essentially 2*A045623.
The third column is essentially 4*A084266.
The cumulative sums of the third column are essentially 4*A176027.
For n >= 2 and 1 <= k <= n, T(n,k) is the number of bimonotone subdivisions of a 2-row grid with n points on the first row and k points on the second row (with the lower left point of the grid being the origin). A bimonotone subdivision of a convex polygon (the convex hull of the grid) is one where the internal dividing lines have nonnegative (including infinite) slopes. See Robeva and Sun (2020). - Petros Hadjicostas and Michel Marcus, Jul 15 2020
|
|
LINKS
|
|
|
FORMULA
|
T(n,1) = 2^(n-2) for n >= 2.
T(n,2) = n*2^(n-2) for n >= 2.
T(n,3) = 2^(n-2)*((n-k+1)^2 + 7*(n-k+1) + 4)/2 = 2^(n-3)*(n^2 + 3*n - 6) for k = 3 and n >= 3.
In general: For 1 <= k <= n with (n,k) <> 1,
T(n,k) = 2^(n-2)*Sum_{i=0..k-1} c(k,i)*(n-k+1)^(k-1-i)/(k-1)! and
T(n,k) = 2^(n-2)*Sum_{j=0..k-1} c(k,k-1-j)*(n-k+1)^j/(k-1)!
with c(k,i) being specific coefficients. Below are the first values for c(k,i):
1;
1, 1;
1, 7, 4;
1, 18, 77, 36;
1, 34, 359, 1238, 528,
1, 55, 1065, 8705, 26654, 10800;
The diagonal of this triangle for c(k,i) divided by (k-1)! (except for the first term) is equal to the Shroeder number sequence A006318(k-1).
T(n,1) = 2^(n-2) for n >= 2; T(n,k) = 2*(T(n,k-1) + T(n-1,k) - T(n-1,k-1)) for n > k >= 2; T(n,n) = 2*T(n,n-1) for n = k >= 2; and T(n,k) = 0 for 1 <= n < k. [Robeva and Sun (2020)] (They do not specify T(1,1) explicitly since they do not care about subdivisions of a degenerate polygon with only one side.)
T(n,k) = (2^(n-2)/(k-1)!) * P_k(n) = (2^(n-2)/(k-1)!) * Sum_{j=1..k} A336245(k,j)*n^(k-j) for n >= k >= 1 with (n,k) <> (1,1), where P_k(n) is some polynomial with integer coefficients of degree k-1. [Robeva and Sun (2020)]
A336245(k,j) = Sum_{s=0..j-1} c(k,s) * binomial(k-1-s, k-j) * (1-k)^(j-1-s) for 1 <= j <= k, in terms of the above coefficients c(k,i).
So c(k,s) = Sum_{j=1..s+1} A336245(k,j) * binomial(k-j, k-s-1) * (k-1)^(s+1-j) for k >= 1 and 0 <= s <= k-1, obtained by inverting the binomial transform.
Bivariate o.g.f.: x*y*(1 - x)*(1 - 2*y*g(2*x*y))/(1 - 2*x - 2*y + 2*x*y), where g(w) = 2/(1 + w + sqrt(1 - 6*w + w^2)) = g.f. of A001003.
Letting y = 1 in the above joint o.g.f., we get the o.g.f. of the row sums: x*(1-x)*(2*g(2*x) - 1). It can then be easily proved that
Sum_{k=1..n} T(n,k) = 2^n*A001003(n-1) - 2^(n-1)*A001003(n-2) for n >= 3. (End)
|
|
EXAMPLE
|
Triangle (with rows n >= 1 and columns k = 1..n) begins:
1;
1, 2;
2, 6, 12;
4, 16, 44, 88;
8, 40, 136, 360, 720;
16, 96, 384, 1216, 3152, 6304;
32, 224, 1024, 3712, 11296, 28896, 57792;
64, 512, 2624, 10624, 36416, 108032, 273856, 547712;
...
Example: T(4,3) = 44 = 1 + 1 + 2 + 2 + 6 + 12 + 4 + 16.
Consider the following 2-row grid with n = 3 points at the top and k = 2 points at the bottom:
A B C
*--*--*
| /
| /
*--*
D E
The sets of the dividing internal lines of the T(3,2) = 6 bimonotone subdivisions of the above 2-row grid are as follows: { }, {DC}, {DB}, {EB}, {DB, DC}, and {DB, EB}. We exclude subdivisions {EA} and {EA, EB} because they have at least one dividing line with a negative slope. (End)
|
|
PROG
|
(PARI) lista(nn) = {my(T=matrix(nn, nn)); T[1, 1] = 1; for (n=2, nn, for (k=1, n, T[n, k] = sum(i=1, n, sum(j=1, k, if ((i!=n) || (j!=k), T[i, j]))); ); ); vector(nn, k, vector(k, i, T[k, i])); } \\ Michel Marcus, Mar 18 2020
|
|
CROSSREFS
|
Cf. A001003, A001792, A006318, A011782, A045623, A057711, A059435, A059576, A068766, A084266, A090442, A129952, A166444, A176027, A336245.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|