A212806 -id:A212806 - cp's OEIS frontend

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

1, 1, 1, 1, 3, 1, 1, 19, 7, 1, 1, 211, 163, 15, 1, 1, 3651, 8983, 1135, 31, 1, 1, 90921, 966751, 271375, 7291, 63, 1, 1, 3081513, 179781181, 158408751, 7225951, 45199, 127, 1, 1, 136407699, 53090086057, 191740223841, 21855093751, 182199871, 275563, 255, 1

Offset: 1

R. H. Hardin, May 28 2012

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.
This is R(n,k,0) in [Abramson-Promislow].
From Petros Hadjicostas, Sep 09 2019: (Start)
As stated above, in the notation of Abramson and Promislow (1978), we have T(n,k) = R(n, k, t=0).
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).
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.
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).
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.
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.
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.
(End)

			Some solutions for n=3 and k=4:
  2 1 3 0    1 3 0 2    3 0 2 1    1 3 0 2    1 3 2 0
  2 0 1 3    1 3 0 2    3 1 2 0    1 0 3 2    1 3 0 2
  2 3 0 1    3 0 2 1    2 3 1 0    2 0 3 1    3 1 0 2
Table starts:
  1  1     1         1             1                  1                       1
  1  3    19       211          3651              90921                 3081513
  1  7   163      8983        966751          179781181             53090086057
  1 15  1135    271375     158408751       191740223841         429966316953825
  1 31  7291   7225951   21855093751    164481310134301     2675558106868421881
  1 63 45199 182199871 2801736968751 128645361626874561 14895038886845467640193

Alois P. Heinz, Antidiagonals n = 1..45 (first 20 antidiagonals from R. H. Hardin)
Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, National Bureau of Standards (Applied Mathematics Series, 55), 1964; see pp. 831-832 for the multinomial coefficients of integer partitions of n = 1..10.
Morton Abramson and David Promislow, Enumeration of arrays by column rises, 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.
Yifei Li and Sheila Sundaram, Homology of Segre products of Boolean and subspace lattices, arXiv:2408.08421 [math.CO], 2024. See p. 17.
Wikipedia, Partition (number theory).
Wikipedia, Multinomial theorem.

Cf. A000012 (row 1), A000275 (row 2), A212856 (row 3), A212857 (row 4), A212858 (row 5), A212859 (row 6), A212860 (row 7).
Cf. A000012 (column 1), A000225 (column 2), A212850 (column 3), A212851 (column 4), A212852 (column 5), A212853 (column 6), A212854 (column 7).
Cf. A000041, A070289 (order of minimal recurrence for column k), A192721, A212806 (main diagonal), A309951, A325305.

A212855_row := proc(m,len) proc(n,m) sum(z^k/k!^m, k = 0..infinity);
series(%^x, z=0, n+1): n!^m*coeff(%,z,n); [seq(coeff(%,x,k),k=0..n)] end;
seq(add(abs(k), k=%(j,m)), j=1..len) end:
for n from 1 to 6 do A212855_row(n,7) od; # Peter Luschny, May 26 2017
# second Maple program:
T:= proc(n, k) option remember; `if`(k=0, 1, -add(
      binomial(k, j)^n*(-1)^j*T(n, k-j), j=1..k))
    end:
seq(seq(T(n, 1+d-n), n=1..d), d=1..10);  # Alois P. Heinz, Apr 26 2020

rows = 9;
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 = Table[row[n, rows+1], {n, 1, rows}];
Table[T[[n-k+1, k]], {n, 1, rows}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Feb 27 2018, after Peter Luschny *)

Empirical recurrence for column k:
k=1: a(n) = 1*a(n-1).
k=2: a(n) = 3*a(n-1) - 2*a(n-2).
k=3: a(n) = 10*a(n-1) - 27*a(n-2) + 18*a(n-3).
k=4: a(n) = 47*a(n-1) - 718*a(n-2) + 4416*a(n-3) - 10656*a(n-4) + 6912*a(n-5).
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).
[All the "empirical" recurrences above are correct. See the comments above.]
From Benoit Jubin, May 29 2012: (Start)
T(n,1) = T(1,n) = 1.
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].
(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)
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
From Petros Hadjicostas, Sep 09 2019: (Start)
Recurrence for column k:  Sum_{s = 0..A070289(k)} (-1)^s * A325305(k,s) * T(n-s,k) = 0 for n >= A070289(k) + 1.
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.
(End)
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

cp's OEIS Frontend

A212845 Erroneous version of A212806.

Views

Author

Keywords

Comments

Links

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A212805 a(n) = (1-(n-1)/2^n)*(n!)^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A336666 a(n) = (n!)^n * [x^n] 1 / (Sum_{k>=0} (-x)^k / (k!)^n)^n.

Views

Author

Keywords

Crossrefs

Programs

Mathematica