|
%I #87 Apr 28 2023 14:45:59
%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 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
|
