A212858 -id:A212858 - 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

A212856 Number of 3 X n arrays with rows being permutations of 0..n-1 and no column j greater than column j-1 in all rows.

Original entry on oeis.org

1, 1, 7, 163, 8983, 966751, 179781181, 53090086057, 23402291822743, 14687940716402023, 12645496977257273257, 14490686095184389113277, 21557960797148733086439949, 40776761007750226749220637461, 96332276574683758035941025907591

Offset: 0

R. H. Hardin, May 28 2012

nonn

			Some solutions for n=3:
  2 1 0   2 0 1   1 2 0   0 2 1   2 0 1   2 1 0   2 1 0
  0 2 1   2 0 1   0 2 1   2 1 0   2 1 0   2 1 0   2 0 1
  0 2 1   2 1 0   2 0 1   2 0 1   0 1 2   1 2 0   2 0 1

Alois P. Heinz, Table of n, a(n) for n = 0..183 (terms n=1..19 from R. H. Hardin)
Morton Abramson and David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250.

Row 3 of A212855.

Cf. A000275, A212857, A212858, A212859, A212860, A336195.

A212856 := proc(n) sum(z^k/k!^3, k = 0..infinity);
series(%^x, z=0, n+1): n!^3*coeff(%,z,n); add(abs(coeff(%,x,k)), k=0..n) end:
seq(A212856(n), n=0..14); # Peter Luschny, May 27 2017
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, -add(
      binomial(n, j)^3*(-1)^j*a(n-j), j=1..n))
    end:
seq(a(n), n=0..15);  # Alois P. Heinz, Apr 26 2020

f[0] = 1; f[n_] := f[n] = Sum[(-1)^(n+k+1)*f[k]*Binomial[n, k]^2/(n-k)!, {k, 0, n-1}]; a[n_] := f[n]*n!; Array[a, 14] (* Jean-François Alcover, Feb 27 2018, after Daniel Suteu *)

a(n) = f(n) * n!, where f(0) = 1, f(n) = Sum_{k=0..n-1} (-1)^(n+k+1) * f(k) * binomial(n, k)^2 / (n-k)!. - Daniel Suteu, Feb 23 2018
a(n) = (n!)^3 * [x^n] 1 / (1 + Sum_{k>=1} (-x)^k / (k!)^3). - Seiichi Manyama, Jul 18 2020
a(n) ~ c * n!^3 / r^n, where r = 1.16151549806386358435938834554462085598002... is the root of the equation HypergeometricPFQ[{}, {1, 1}, -r] = 0 and c = 1.182760720067731330743886867947078139186402925891650811631774628... - Vaclav Kotesovec, Sep 16 2020

a(0)=1 prepended by Alois P. Heinz, Apr 26 2020

A309951 Irregular triangular array, read by rows: T(n,k) is the sum of the products of multinomial coefficients (n_1 + n_2 + n_3 + ...)!/(n_1! * n_2! * n_3! * ...) taken k at a time, where (n_1, n_2, n_3, ...) runs over all integer partitions of n (n >= 0, 0 <= k <= A000041(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 2, 1, 10, 27, 18, 1, 47, 718, 4416, 10656, 6912, 1, 246, 20545, 751800, 12911500, 100380000, 304200000, 216000000, 1, 1602, 929171, 260888070, 39883405500, 3492052425000, 177328940580000, 5153150631600000, 82577533320000000, 669410956800000000, 2224399449600000000, 1632586752000000000, 1, 11481

Offset: 0

Petros Hadjicostas, Aug 25 2019

This array was inspired by R. H. Hardin's recurrences for the columns of array A212855. Rows k=1 to k=5 are due to him, while the remaining rows were computed by Alois P. Heinz.
Row n has length A000041(n) + 1, i.e., one more than the number of partitions of n.
Let R(m,n) := R(m,n,t=0) = A212855(m,n) for m,n >= 1, where R(m,n,t) = LHS of Eq. (6) of Abramson and Promislow (1978, p. 248).
Let P_n be the set of all lists a = (a_1, a_2,..., a_n) of integers a_i >= 0, i = 1,..., n such that 1*a_1 + 2*a_2 + ... + n*a_n = n; i.e., P_n is the set all integer partitions of n. (We use a different notation for partitions than the one in the name of T(n,k).) Then |P_n| = A000041(n) for n >= 0.
We have R(m,n) = A212855(m,n) = Sum_{a in P_n} (-1)^(n - Sum_{j=1..n} a_j) * (a_1 + a_2 + ... + a_n)!/(a_1! * a_2! * ... * a_n!) * (n! / ((1!)^a_1 * (2!)^a_2 * ... * (n!)^a_n))^m.
The recurrence of R. H. Hardin for column n of array A212855 is Sum_{s = 0..|P_n|} (-1)^s * T(n,s) * R(m-s,n) = 0 for n >= 1 and m >= |P_n| + 1.
The above recurrence is correct for all n >= 1, but it is not always a minimal one. For example, it seems to be the minimal one for n = 1,...,6, but not for n = 7 (see A212854). It seems to be minimal whenever every two different partitions of n give different multinomial coefficients.
For n = 7, the partitions (a_1, a_2, a_3, a_4, a_5, a_6, a_7) = (0, 2, 1, 0, 0, 0, 0) (i.e., 2 + 2 + 3) and  (a_1, a_2, a_3, a_4, a_5, a_6, a_7) = (3, 0, 0, 1, 0, 0, 0) (i.e., 1 + 1 + 1 + 4) give the same multinomial coefficient: 210 = 7!/(2!2!3!) = 7!/(1!1!1!4!). Hence, to find the minimal recurrence for n = 7, we count 210 only once in the set of multinomial coefficients: 1, 7, 21, 35, 42, 105, 140, 210, 420, 630, 840, 1260, 2520, 5040. Then the absolute value of the coefficient of a(n-1) in the minimal recurrence is the sum of these multinomial coefficients (i.e., 11271); the absolute value of the coefficient of a(n-2) in the minimal recurrence is the sum of products of every two of them (i.e., 46169368), and so on.
Looking at the multinomial coefficients of the integer partitions of n = 8, 9, 10 on pp. 831-832 of Abramowitz and Stegun (1964), we see that, even in these cases, the above recurrence is not the minimal one. The number of distinct multinomial coefficients among the integer partitions of n is given by A070289.

			Triangle begins as follows:
  [n=0]: 1,   1;
  [n=1]: 1,   1;
  [n=2]: 1,   3,     2;
  [n=3]: 1,  10,    27,     18;
  [n=4]: 1,  47,   718,   4416,    10656,      6912;
  [n=5]: 1, 246, 20545, 751800, 12911500, 100380000, 304200000, 216000000;
  ...
For example, when n = 3, the integer partitions of 3 are 3, 1+2, 1+1+1, and the corresponding multinomial coefficients are 3!/3! = 1, 3!/(1!2!) = 3, and 3!/(1!1!1!) = 6. Then T(n=3, k=0) = 1, T(n=3, k=1) = 1 + 3 + 6 = 10, T(n=3, k=2) = 1*3 + 1*6 + 3*6 = 27, and T(n=3, k=3) = 1*3*6 = 18.
Since |P_3| = A000041(3) = 3, the recurrence of _R. H. Hardin_ for column n = 3 of array A212855 is T(3,0)*R(m,3) - T(3,1)*R(m-1,3) + T(3,2)*R(m-2,3) - T(3,3)*R(m-3,3) = 0; i.e., R(m,3) - 10*R(m-1,3) + 27*R(m-2,3) - 18*R(m-3,3) = 0 for m >= 4. We have the initial conditions R(m=1,3) = 1, R(m=2,3) = 19, and R(m=3,3) = 163. Thus, R(m,3) = 6^m - 2*3^m + 1 = A212850(m) for m >= 1. See the documentation of array A212855.

Alois P. Heinz, Rows n = 0..14, flattened
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; see Eq. (6), p. 248, and the comments above.
Wikipedia, Partition (number theory).

Cf. A000012 (column k=0), A000041, A005651 (column k=1), A070289, A212850, A212851, A212852, A212853, A212854, A212855, A212856, A212857, A212858, A212859, A212860.

Rightmost terms in rows give A309972.

g:= proc(n, i) option remember; `if`(n=0 or i=1, [n!], [map(x->
      binomial(n, i)*x, g(n-i, min(n-i, i)))[], g(n, i-1)[]])
    end:
b:= proc(n, m) option remember; `if`(n=0, 1,
      expand(b(n-1, m)*(g(m$2)[n]*x+1)))
    end:
T:= n->(p->seq(coeff(p, x, i), i=0..degree(p)))(b(nops(g(n$2)), n)):
seq(T(n), n=0..7);  # Alois P. Heinz, Aug 25 2019

g[n_, i_] := g[n, i] = If[n==0 || i==1, {n!}, Join[Binomial[n, i]*#& /@ g[n - i, Min[n - i, i]], g[n, i - 1]]];
b[n_, m_] := b[n, m] = If[n==0, 1, Expand[b[n-1, m]*(g[m, m][[n]]*x+1)]];
T[n_] := CoefficientList[b[Length[g[n, n]], n], x];
T /@ Range[0, 7] // Flatten (* Jean-François Alcover, Feb 18 2021, after Alois P. Heinz *)

Sum_{k=0..A000041(n)} (-1)^k * T(n,k) = 0.

A212857 Number of 4 X n arrays with rows being permutations of 0..n-1 and no column j greater than column j-1 in all rows.

Original entry on oeis.org

1, 1, 15, 1135, 271375, 158408751, 191740223841, 429966316953825, 1644839120884915215, 10079117505143103766735, 94135092186827772028779265, 1287215725538576868883610346465, 24929029117106417518788960414909025, 664978827664071363541997348802227351425

Offset: 0

R. H. Hardin, May 28 2012

nonn

From Petros Hadjicostas, Sep 08 2019: (Start)
We generalize Daniel Suteu's recurrence from A212856. Notice first that, in the notation of Abramson and Promislow (1978), we have a(n) = R(m=4, n, t=0).
Letting y=0 in Eq. (8), p. 249, of Abramson and Promislow (1978), we get 1 + Sum_{n >= 1} R(m,n,t=0)*x^n/(n!)^m = 1/f(-x), where f(x) = Sum_{i >= 0} (x^i/(i!)^m). Matching coefficients, we get Sum_{s = 1..n} R(m, s, t=0) * (-1)^(s-1) * binomial(n,s)^m = 1, from which the recurrence in the Formula section follows.
(End)

			Some solutions for n=3:
  1 2 0   1 0 2   1 0 2   2 1 0   2 0 1   2 1 0   1 0 2
  2 1 0   1 0 2   0 2 1   0 2 1   2 1 0   1 0 2   2 1 0
  1 2 0   2 1 0   1 0 2   0 1 2   2 1 0   2 1 0   1 2 0
  2 1 0   0 1 2   2 1 0   2 1 0   1 0 2   2 1 0   2 1 0

Seiichi Manyama, Table of n, a(n) for n = 0..144 (terms n=1..19 from R. H. Hardin)
Morton Abramson and David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250; see Eq. (8) on p. 249.

Row 4 of A212855.

Cf. A000012, A000225, A000275, A212850, A212851, A212852, A212853, A212854, A212856, A212858, A212859, A212860, A336196.

A212857 := proc(n) sum(z^k/k!^4, k = 0..infinity);
series(%^x, z=0, n+1): n!^4*coeff(%,z,n); add(abs(coeff(%,x,k)), k=0..n) end:
seq(A212857(n), n=1..13); # Peter Luschny, May 27 2017

T[n_, k_] := T[n, k] = If[k == 0, 1, -Sum[Binomial[k, j]^n*(-1)^j*T[n, k - j], {j, 1, k}]];
a[n_] := T[4, n];
Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A212855 *)

a(n) = (-1)^(n-1) + Sum_{s = 1..n-1} a(s) * (-1)^(n-s-1) * binomial(n,s)^m for n >= 2 with a(1) = 1. Here m = 4. - Petros Hadjicostas, Sep 08 2019

a(n) = (n!)^4 * [x^n] 1 / (1 + Sum_{k>=1} (-x)^k / (k!)^4). (see Petros Hadjicostas's comment on Sep 08 2019) - Seiichi Manyama, Jul 18 2020

a(0)=1 prepended by Seiichi Manyama, Jul 18 2020

A212859 Number of 6 X n arrays with rows being permutations of 0..n-1 and no column j greater than column j-1 in all rows.

Original entry on oeis.org

1, 1, 63, 45199, 182199871, 2801736968751, 128645361626874561, 14895038886845467640193, 3842738508408709445398181439, 2009810719756197663340563540778591, 1977945985139308994141721986912910579313, 3448496643225334129810790241492300508936547073

Offset: 0

R. H. Hardin, May 28 2012

nonn

From Petros Hadjicostas, Sep 08 2019: (Start)
We generalize Daniel Suteu's recurrence from A212856. Notice first that, in the notation of Abramson and Promislow (1978), we have a(n) = R(m=6, n, t=0).
Letting y=0 in Eq. (8), p. 249, of Abramson and Promislow (1978), we get 1 + Sum_{n >= 1} R(m,n,t=0)*x^n/(n!)^m = 1/f(-x), where f(x) = Sum_{i >= 0} (x^i/(i!)^m). Matching coefficients, we get Sum_{s = 1..n} R(m, s, t=0) * (-1)^(s-1) * binomial(n,s)^m = 1, from which the recurrence in the Formula section follows.
(End)

			Some solutions for n=3:
  2 0 1   1 0 2   2 0 1   0 1 2   2 1 0   0 1 2   0 1 2
  0 1 2   0 2 1   1 2 0   0 1 2   1 2 0   0 1 2   0 1 2
  1 0 2   2 0 1   2 0 1   2 0 1   1 0 2   1 0 2   2 0 1
  0 2 1   0 1 2   2 0 1   2 0 1   0 1 2   1 2 0   0 1 2
  1 2 0   2 0 1   0 1 2   1 2 0   1 0 2   0 1 2   1 2 0
  2 1 0   1 0 2   0 2 1   0 2 1   0 1 2   2 0 1   1 2 0

Seiichi Manyama, Table of n, a(n) for n = 0..104 (terms n=1..19 from R. H. Hardin)
Morton Abramson and David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250; see Eq. (8) on p. 249.

Row 6 of A212855.

Cf. A000012, A000225, A000275, A212850, A212851, A212852, A212853, A212854, A212856, A212857, A212858, A212860.

A212859 := proc(n) sum(z^k/k!^6, k = 0..infinity);
series(%^x, z=0, n+1): n!^6*coeff(%,z,n); add(abs(coeff(%,x,k)), k=0..n) end:
seq(A212859(n), n=1..11); # Peter Luschny, May 27 2017

T[n_, k_] := T[n, k] = If[k == 0, 1, -Sum[Binomial[k, j]^n*(-1)^j*T[n, k - j], {j, 1, k}]];
a[n_] := T[6, n];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A212855 *)

a(n) = (-1)^(n-1) + Sum_{s = 1..n-1} a(s) * (-1)^(n-s-1) * binomial(n,s)^m for n >= 2 with a(1) = 1. Here m = 6. - Petros Hadjicostas, Sep 08 2019

a(n) = (n!)^6 * [x^n] 1 / (1 + Sum_{k>=1} (-x)^k / (k!)^6). (see Petros Hadjicostas's comment on Sep 08 2019) - Seiichi Manyama, Jul 18 2020

a(0)=1 prepended by Seiichi Manyama, Jul 18 2020

A212860 Number of 7 X n arrays with rows being permutations of 0..n-1 and no column j greater than column j-1 in all rows.

Original entry on oeis.org

1, 1, 127, 275563, 4479288703, 347190069843751, 96426023622482278621, 78785944892341703819175577, 163925632052722656731213188429183, 777880066963402408939826643081996101263, 7717574897043522397037273525233635595811018377

Offset: 0

R. H. Hardin, May 28 2012

nonn

From Petros Hadjicostas, Sep 08 2019: (Start)
We generalize Daniel Suteu's recurrence from A212856. Notice first that, in the notation of Abramson and Promislow (1978), we have a(n) = R(m=7, n, t=0).
Letting y=0 in Eq. (8), p. 249, of Abramson and Promislow (1978), we get 1 + Sum_{n >= 1} R(m,n,t=0)*x^n/(n!)^m = 1/f(-x), where f(x) = Sum_{i >= 0} (x^i/(i!)^m). Matching coefficients, we get Sum_{s = 1..n} R(m, s, t=0) * (-1)^(s-1) * binomial(n,s)^m = 1, from which the recurrence in the Formula section follows.
(End)

			Some solutions for n=3:
  0 1 2   0 1 2   0 2 1   0 1 2   0 2 1   0 2 1   0 2 1
  1 2 0   0 2 1   0 2 1   1 0 2   0 2 1   1 0 2   2 1 0
  1 0 2   2 1 0   2 0 1   0 1 2   2 0 1   1 0 2   1 2 0
  0 2 1   1 0 2   0 2 1   1 0 2   0 1 2   2 0 1   0 1 2
  2 0 1   2 1 0   1 0 2   2 1 0   1 2 0   0 1 2   1 2 0
  2 1 0   0 1 2   1 0 2   0 1 2   2 0 1   1 0 2   2 1 0
  1 2 0   2 1 0   0 1 2   0 2 1   2 1 0   2 0 1   2 0 1

Seiichi Manyama, Table of n, a(n) for n = 0..92 (terms n=1..19 from R. H. Hardin)
Morton Abramson and David Promislow, Enumeration of arrays by column rises, J. Combinatorial Theory Ser. A 24(2) (1978), 247-250; see Eq. (8) on p. 249.

Row 7 of A212855.

Cf. A000012, A000225, A000275, A212850, A212851, A212852, A212853, A212854, A212856, A212857, A212858, A212859.

A212860 := proc(n) sum(z^k/k!^7, k = 0..infinity);
series(%^x, z=0, n+1): n!^7*coeff(%,z,n); add(abs(coeff(%,x,k)), k=0..n) end:
seq(A212860(n), n=1..10); # Peter Luschny, May 27 2017

T[n_, k_] := T[n, k] = If[k == 0, 1, -Sum[Binomial[k, j]^n*(-1)^j*T[n, k - j], {j, 1, k}]];
a[n_] := T[7, n];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A212855 *)

a(n) = (-1)^(n-1) + Sum_{s = 1..n-1} a(s) * (-1)^(n-s-1) * binomial(n,s)^m for n >= 2 with a(1) = 1. Here m = 7. - Petros Hadjicostas, Sep 08 2019

a(n) = (n!)^7 * [x^n] 1 / (1 + Sum_{k>=1} (-x)^k / (k!)^7). (see Petros Hadjicostas's comment on Sep 08 2019) - Seiichi Manyama, Jul 18 2020

a(0)=1 prepended by Seiichi Manyama, Jul 18 2020

A212806 Number of n X n matrices in which each row is a permutation of [1..n] and which contain no column rises.

Original entry on oeis.org

1, 3, 163, 271375, 21855093751, 128645361626874561, 78785944892341703819175577, 6795588328283070704898044776213094655, 107414633522643325764587104395687638119674465944431, 392471529081605251407320880492124164530148025908765037878553312273, 407934916447631403509359040563002566177814886353044858592046202746464825839911293037

Offset: 1

N. J. A. Sloane, May 27 2012

nonn

A column rise in a matrix M = (m_{i,j}) is a value of j such that m_{i,j} < m_{i,j+1} for all i = 1..n.
From Petros Hadjicostas, Aug 26 2019: (Start)
Let R(m,n) := R(m,n,t=0) = A212855(m,n) for m,n >= 1, where R(m,n,t) = LHS of Eq. (6) of Abramson and Promislow (1978, p. 248).
Let P_n be the set of all lists b = (b_1, b_2,..., b_n) of integers b_i >= 0, i = 1,..., n, such that 1*b_1 + 2*b_2 + ... + n*b_n = n; i.e., P_n is the set all integer partitions of n. Then |P_n| = A000041(n) for n >= 0.
We have a(n) = R(n,n) = A212855(n,n) = Sum_{b in P_n} (-1)^(n - Sum_{j=1..n} b_j) * (b_1 + b_2 + ... + b_n)!/(b_1! * b_2! * ... * b_n!) * (n! / ((1!)^b_1 * (2!)^b_2 * ... * (n!)^b_n)^n.
(End)

			For n=2 the three matrices are [12/21], [21/12], [21/21] (but not [12/12]).
From _Petros Hadjicostas_, Aug 26 2019: (Start)
For example, when n = 3, the integer partitions of 3 are 3, 1+2, and 1+1+1, with corresponding (b_1, b_2, b_3) notation (0,0,1), (1,1,0), and (3,0,0). The corresponding multinomial coefficients are 3!/3! = 1, 3!/(1!*2!) = 3, and 3!/(1!*1!*1!) = 6, while the corresponding quantities (b_1 + b_2 + b_3)!/(b_1!*b_2!*b_3!) are 1, 2, and 1. The corresponding exponents of -1 (i.e., n - Sum_{j=1..n} b_j) are 3 - (0+0+1) = 2, 3 - (1+1+0) = 1, and 3 - (3+0+0) = 0.
It follows that a(n) = (-1)^2 * 1 * 1^3 + (-1)^1 * 2 * 3^3 + (-1)^0 * 1 * 6^3 = 163.
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..30 (first 18 terms 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). [Their a(5) on p. 250 is wrong; see A212845.]
Wikipedia, Partition (number theory).

A212805 is a lower bound.
Main diagonal of A212855.
Cf. A000041, A070289, A212850, A212851, A212852, A212853, A212854, A212856, A212857, A212858, A212859, A212860, A309951, A325305.

A212806 := proc(n) sum(z^k/k!^n, k=0..infinity);
series(%^x, z=0, n+1): n!^n*coeff(%,z,n); add(abs(coeff(%,x,k)),k=0..n) end:
seq(A212806(n), n=1..11); # Peter Luschny, May 27 2017

a[n_] := Module[{s0, s1, s2}, s0 = Sum[z^k/k!^n, {k, 0, n}]; s1 =  Series[s0^x, {z, 0, n + 1}] // Normal; s2 = n!^n*Coefficient[s1, z, n]; Sum[Abs[Coefficient[s2, x, k]], {k, 0, n}]]; Array[a, 11] (* Jean-François Alcover, Feb 27 2018, after Peter Luschny *)
T[n_, k_] := T[n, k] = If[k == 0, 1, -Sum[Binomial[k, j]^n*(-1)^j*T[n, k-j], {j, 1, k}]];
a[n_] := T[n, n];
Table[a[n], {n, 1, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A212855 *)

Abramson and Promislow give a g.f. for R(m,n,t), the number of m X n matrices in which each row is a permutation of [1..n] and which contain exactly t column rises:

1 + Sum_{n>=1} Sum_{t=0..n-1} R(m,n,t) y^t x^n/(n!)^m = (y-1)/(y-f(x(y-1))) where f(x) = Sum_{i>=0} x^i/(i!)^m.

Corrected by R. H. Hardin, May 28 2012

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A212856 Number of 3 X n arrays with rows being permutations of 0..n-1 and no column j greater than column j-1 in all rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A309951 Irregular triangular array, read by rows: T(n,k) is the sum of the products of multinomial coefficients (n_1 + n_2 + n_3 + ...)!/(n_1! * n_2! * n_3! * ...) taken k at a time, where (n_1, n_2, n_3, ...) runs over all integer partitions of n (n >= 0, 0 <= k <= A000041(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A212857 Number of 4 X n arrays with rows being permutations of 0..n-1 and no column j greater than column j-1 in all rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A212859 Number of 6 X n arrays with rows being permutations of 0..n-1 and no column j greater than column j-1 in all rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A212860 Number of 7 X n arrays with rows being permutations of 0..n-1 and no column j greater than column j-1 in all rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A212806 Number of n X n matrices in which each row is a permutation of [1..n] and which contain no column rises.

Views

Author

Keywords