%I #91 Aug 22 2024 20:34:54

%S 1,1,1,1,3,1,1,19,7,1,1,211,163,15,1,1,3651,8983,1135,31,1,1,90921,

%T 966751,271375,7291,63,1,1,3081513,179781181,158408751,7225951,45199,

%U 127,1,1,136407699,53090086057,191740223841,21855093751,182199871,275563,255,1

%N T(n,k) = number of n X k arrays with rows being permutations of 0..k-1 and no column j greater than column j-1 in all rows (n, k >= 1).

%C In other words, there are no "column rises", where a "column rise" means a pair of adjacent columns where each entry in the left column is strictly less than the adjacent entry in the right column.

%C This is R(n,k,0) in [Abramson-Promislow].

%C From _Petros Hadjicostas_, Sep 09 2019: (Start)

%C As stated above, in the notation of Abramson and Promislow (1978), we have T(n,k) = R(n, k, t=0).

%C Let P_k be the set of all lists a = (a_1, a_2, ..., a_k) of integers a_i >= 0, i = 1, ..., k, such that 1*a_1 + 2*a_2 + ... + k*a_k = k; i.e., P_k is the set all integer partitions of k. Then |P_k| = A000041(k).

%C From Eq. (6), p. 248, in Abramson and Promislow (1978), with t=0, we get T(n,k) = Sum_{a in P_k} (-1)^(k - Sum_{j=1..k} a_j) * (a_1 + a_2 + ... + a_k)!/(a_1! * a_2! * ... * a_k!) * (k! / ((1!)^a_1 * (2!)^a_2 * ... * (k!)^a_k))^n.

%C The integer partitions of k = 1..10 are listed on pp. 831-832 of Abramowitz and Stegun (1964). We see that, for k = 1..6, the corresponding multinomial coefficients k! / ((1!)^a_1 * (2!)^a_2 * ... * (k!)^a_k) are all distinct; that is, A070289(k) = A000041(k) and A309951(k,s) = A325305(k,s) for s = 0..A000041(k). For 7 <= k <= 10, this is not true anymore; i.e., A070289(k) < A000041(k) for 7 <= k <= 10 (and we conjecture that this is the case for all k >= 7).

%C From the theory of difference equations, we see that Abramson and Promislow's Eq. (6) on p. 248 (with t=0) implies that Sum_{s = 0..A070289(k)} (-1)^s * A325305(k,s) * T(n-s,k) = 0 for n >= A070289(k) + 1. For k = 1..5, these recurrences give _R. H. Hardin_'s empirical recurrences shown in the Formula section below.

%C We also have Sum_{s = 0..A000041(k)} (-1)^s * A309951(k,s) * T(n-s,k) = 0 for n >= A000041(k) + 1, but for k >= 7, the recurrence we get (for column k) may not necessarily be minimal.

%C To derive the recurrence for row n, let y=0 in Eq. (8), p. 249, of Abramson and Promislow (1978). We get 1 + Sum_{k >= 1} T(n,k)*x^k/(k!)^n = 1/f_n(-x), where f_n(x) = Sum_{i >= 0} (x^i/(i!)^n). Matching coefficients, we get Sum_{s = 1..k} T(n,s) * (-1)^(s-1) * binomial(k,s)^n = 1, from which the recurrence in the Formula section follows.

%C (End)

%H Alois P. Heinz, <a href="/A212855/b212855.txt">Antidiagonals n = 1..45</a> (first 20 antidiagonals from R. H. Hardin)

%H Milton Abramowitz and Irene A. Stegun, <a href="http://www.cs.bham.ac.uk/~aps/research/projects/as/book.php">Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables</a>, National Bureau of Standards (Applied Mathematics Series, 55), 1964; see pp. 831-832 for the multinomial coefficients of integer partitions of n = 1..10.

%H Morton Abramson and David Promislow, <a href="https://doi.org/10.1016/0097-3165(78)90012-2">Enumeration of arrays by column rises</a>, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250. MR0469773 (57 #9554); see Eqs. (6) on p. 248 and (8) on p. 249 with t=0.

%H Yifei Li and Sheila Sundaram, <a href="https://arxiv.org/abs/2408.08421">Homology of Segre products of Boolean and subspace lattices</a>, arXiv:2408.08421 [math.CO], 2024. See p. 17.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multinomial_theorem">Multinomial theorem</a>.

%F Empirical recurrence for column k:

%F k=1: a(n) = 1*a(n-1).

%F k=2: a(n) = 3*a(n-1) - 2*a(n-2).

%F k=3: a(n) = 10*a(n-1) - 27*a(n-2) + 18*a(n-3).

%F k=4: a(n) = 47*a(n-1) - 718*a(n-2) + 4416*a(n-3) - 10656*a(n-4) + 6912*a(n-5).

%F k=5: a(n) = 246*a(n-1) - 20545*a(n-2) + 751800*a(n-3) - 12911500*a(n-4) + 100380000*a(n-5) - 304200000*a(n-6) + 216000000*a(n-7).

%F [All the "empirical" recurrences above are correct. See the comments above.]

%F From _Benoit Jubin_, May 29 2012: (Start)

%F T(n,1) = T(1,n) = 1.

%F T(n,2) = 2^n - 1 since the only n X 2 matrix with rows permutations of {0,1} which has a column rise is the one where all rows are [0,1].

%F (k!)^n*(1 - (k-1)/2^n) <= T(n,k) <= (k!)^n (the first inequality is (11) in the Abramson-Promislow reference, the second is trivial). (End)

%F For r >= 1, A(n, r) = Sum_{k=0..n} |[x^k] n!^r [z^n] S(r, z)^x| where S(r, z) = Sum_{k>=0} z^k/k!^r. - _Peter Luschny_, Feb 27 2018

%F From _Petros Hadjicostas_, Sep 09 2019: (Start)

%F Recurrence for column k: Sum_{s = 0..A070289(k)} (-1)^s * A325305(k,s) * T(n-s,k) = 0 for n >= A070289(k) + 1.

%F Recurrence for row n: T(n,k) = (-1)^(k-1) + Sum_{s = 1..k-1} T(n,s) * (-1)^(k-s-1) * binomial(k,s)^n for k >= 1.

%F (End)

%F Sum_{k>=1} T(n,k)*z^k/(k!)^n = 1/E_n(-z) -1 where E_n(z) = Sum_{k>=0} z^k/(k!)^n. - _Geoffrey Critzer_, Apr 28 2023

%e Some solutions for n=3 and k=4:

%e 2 1 3 0 1 3 0 2 3 0 2 1 1 3 0 2 1 3 2 0

%e 2 0 1 3 1 3 0 2 3 1 2 0 1 0 3 2 1 3 0 2

%e 2 3 0 1 3 0 2 1 2 3 1 0 2 0 3 1 3 1 0 2

%e Table starts:

%e 1 1 1 1 1 1 1

%e 1 3 19 211 3651 90921 3081513

%e 1 7 163 8983 966751 179781181 53090086057

%e 1 15 1135 271375 158408751 191740223841 429966316953825

%e 1 31 7291 7225951 21855093751 164481310134301 2675558106868421881

%e 1 63 45199 182199871 2801736968751 128645361626874561 14895038886845467640193

%p A212855_row := proc(m,len) proc(n,m) sum(z^k/k!^m, k = 0..infinity);

%p series(%^x, z=0, n+1): n!^m*coeff(%,z,n); [seq(coeff(%,x,k),k=0..n)] end;

%p seq(add(abs(k), k=%(j,m)), j=1..len) end:

%p for n from 1 to 6 do A212855_row(n,7) od; # _Peter Luschny_, May 26 2017

%p # second Maple program:

%p T:= proc(n, k) option remember; `if`(k=0, 1, -add(

%p binomial(k, j)^n*(-1)^j*T(n, k-j), j=1..k))

%p end:

%p seq(seq(T(n, 1+d-n), n=1..d), d=1..10); # _Alois P. Heinz_, Apr 26 2020

%t rows = 9;

%t row[m_, len_] := Module[{p, s0, s1, s2}, p = Function[{n, m0}, s0 = Sum[ z^k/k!^m0, {k, 0, n}]; s1 = Series[s0^x, {z, 0, n+1}] // Normal; s2 = n!^m0*Coefficient[s1, z, n]; Table[Coefficient[s2, x, k], {k, 0, n}]]; Table[Sum[Abs[k], {k, p[j, m]}], {j, 1, len}]];

%t T = Table[row[n, rows+1], {n, 1, rows}];

%t Table[T[[n-k+1, k]], {n, 1, rows}, {k, n, 1, -1}] // Flatten (* _Jean-François Alcover_, Feb 27 2018, after _Peter Luschny_ *)

%Y Cf. A000012 (row 1), A000275 (row 2), A212856 (row 3), A212857 (row 4), A212858 (row 5), A212859 (row 6), A212860 (row 7).

%Y Cf. A000012 (column 1), A000225 (column 2), A212850 (column 3), A212851 (column 4), A212852 (column 5), A212853 (column 6), A212854 (column 7).

%Y Cf. A000041, A070289 (order of minimal recurrence for column k), A192721, A212806 (main diagonal), A309951, A325305.

%K nonn,tabl

%O 1,5

%A _R. H. Hardin_, May 28 2012