A325305 -id:A325305 - cp's OEIS frontend

A070289 Number of distinct values of multinomial coefficients ( n / (p1, p2, p3, ...) ) where (p1, p2, p3, ...) runs over all partitions of n.

1, 1, 2, 3, 5, 7, 11, 14, 20, 27, 36, 47, 64, 79, 102, 125, 157, 193, 243, 296, 366, 441, 538, 639, 773, 911, 1092, 1294, 1532, 1799, 2131, 2475, 2901, 3369, 3935, 4554, 5292, 6084, 7033, 8087, 9292, 10617, 12198, 13880, 15874, 18039, 20541, 23263, 26414, 29838

Offset: 0

Naohiro Nomoto, May 12 2002

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..92
George E. Andrews, Arnold Knopfmacher, and Burkhard Zimmermann, On the number of distinct multinomial coefficients, Journal of Number Theory 118 (2006), 15-30; arXiv preprint, arXiv:math/0509470 [math.CO], 2005.
Sergei Viznyuk, C-Program, C-Program, local copy.

Cf. A000041, A036038, A212855, A215520, A215521, A309951, A309999, A325305, A376661.

b:= proc(n,i) option remember;
      if n=0 then {1} elif i<1 then {} else {b(n, i-1)[],
         seq(map(x-> x*i!^j, b(n-i*j, i-1))[], j=1..n/i)} fi
    end:
a:= n-> nops(b(n, n)):
seq(a(n), n=0..50);  # Alois P. Heinz, Aug 14 2012

b[n_, i_] := b[n, i] = If[n == 0, {1}, If[i<1, {}, Union[Join[b[n, i-1], Flatten[ Table[Function[{x}, x*i!^j] /@ b[n-i*j, i-1], {j, 1, n/i}]]]]]]; a[n_] := Length[b[n, n]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 23 2015, after Alois P. Heinz *)

def A070289(n):
    P = Partitions(n)
    M = set(multinomial(list(x)) for x in P)
    return len(M)
[A070289(n) for n in range(20)]
# Joerg Arndt, Aug 14 2012

a(n) = A215520(n,n) = A215521(2*n,n). - Alois P. Heinz, Nov 08 2012

Terms a(n) for n >= 45 corrected by Joerg Arndt and Alois P. Heinz, Aug 14 2012

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

Original entry on oeis.org

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

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

Original entry on oeis.org

1, 3651, 966751, 158408751, 21855093751, 2801736968751, 347190069843751, 42328368099218751, 5119530150996093751, 616756797369980468751, 74155772004699902343751, 8907394925520999511718751

Offset: 1

R. H. Hardin, May 28 2012

nonn

Column 5 of A212855.
From Petros Hadjicostas, Sep 06 2019: (Start)
Let P_5 be the set of all lists b = (b_1, b_2, b_3, b_4, b_5) of integers b_i >= 0, i = 1, ..., 5, such that 1*b_1 + 2*b_2 + 3*b_3 + 4*b_4 + 5*b_5 = 5; i.e., P_5 is the set all integer partitions of 5. Then |P_5| = A000041(5) = 7.
From Eq. (6), p. 248, in Abramson and Promislow (1978), we get a(n) = A212855(n,5) = Sum_{b in P_5} (-1)^(5 - Sum_{j=1..5} b_j) * (b_1 + b_2 + b_3 + b_4 + b_5)!/(b_1! * b_2! * b_3! * b_4! * b_5!) * (5! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5))^n.
The integer partitions of 5 are listed on p. 831 of Abramowitz and Stegun (1964). We see that the corresponding multinomial coefficients 5! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5) are all distinct; that is, A070289(5) = A000041(5) = 7.
Using the integer partitions of 5 and the above formula for a(n), we may derive  R. J. Mathar's formula below.
(End)

			Some solutions for n=3
..0..3..1..2..4....0..2..4..1..3....0..1..4..3..2....0..2..3..4..1
..1..0..4..3..2....1..0..3..2..4....1..3..0..4..2....0..4..3..1..2
..2..4..1..3..0....1..2..0..4..3....3..1..4..0..2....4..0..1..3..2

R. H. Hardin, Table of n, a(n) for n = 1..210
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 (with t=0).
Wikipedia, Multinomial coefficients.
Wikipedia, Partition (number theory).

Cf. A000041, A070289, A212850, A212851, A212853, A212854, A212855, A212856, A309951, A325305.

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, 5];
Table[a[n], {n, 1, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A212855 *)

Empirical: 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).
Empirical: a(n) = -2*5^n + 3*20^n - 4*60^n + 120^n + 3*30^n - 2*10^n + 1. R. J. Mathar, Jun 25 2012
Sum_{s = 0..7} (-1)^s * A325305(5, s) * a(n-s) = 0 for n >= 8. (This is the same as R. H. Hardin's recurrence above, and it follows from Eq. (6) (with t=0), p. 248, in Abramson and Promislow (1978).) - Petros Hadjicostas, Sep 06 2019

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

Original entry on oeis.org

1, 90921, 179781181, 191740223841, 164481310134301, 128645361626874561, 96426023622482278621, 70816637331790329140481, 51492108377805402906874141, 37256471170472317193421713601, 26890352949868734582700237312861

Offset: 1

R. H. Hardin, May 28 2012

nonn

Column 6 of A212855.
From Petros Hadjicostas, Sep 08 2019: (Start)
Let P_6 be the set of all lists b = (b_1, b_2, b_3, b_4, b_5, b_6) of integers b_i >= 0, i = 1, ..., 6, such that 1*b_1 + 2*b_2 + 3*b_3 + 4*b_4 + 5*b_5 + 6*b_6 = 6; i.e., P_6 is the set all integer partitions of 6. Then |P_6| = A000041(6) = 11.
From Eq. (6), p. 248, in Abramson and Promislow (1978), with t=0, we get a(n) = A212855(n,6) = Sum_{b in P_6} (-1)^(6-Sum_{j=1..6} b_j) * (b_1 + b_2 + b_3 + b_4 + b_5 + b_6)!/(b_1! * b_2! * b_3! * b_4! * b_5! * b_6!) * (6! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5 * (6!)^b_6))^n.
The integer partitions of 6 are listed on p. 831 of Abramowitz and Stegun (1964). We see that the corresponding multinomial coefficients 6! / ((1!)^b_1 * (2!)^b_2 * (3!)^b_3 * (4!)^b_4 * (5!)^b_5 * (6!)^b_6) are all distinct; that is, A070289(6) = A000041(6) = 11 and A309951(6,s) = A325305(6,s) for s = 0..11. (Compare with the comments for A212854.)
Using the information about partitions of 6 in Eq. (6) (with t=0), p. 248, of Abramson and Promislow (1978), we may derive the explicit equation for a(n) shown below.
Using standard results from the theory of difference equations (since the solution is known explicitly), we may derive R. H. Hardin's empirical recurrence. The recurrence is equivalent to Sum_{s = 0..11} (-1)^s * A325305(6,s) * a(n-s) = 0 for n >= 12.
(End)

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

R. H. Hardin, Table of n, a(n) for n = 1..210
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) (with t=0), p. 248, and the comments above.
Wikipedia, Partition (number theory).
Wikipedia, Multinomial theorem.

Cf. A000041, A070289, A212850, A212851, A212852, A212854, A212855, A212856, A212857, A309951, A325305.

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, 6];
Table[a[n], {n, 1, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A212855 *)

Empirical: a(n) = 1602*a(n-1) - 929171*a(n-2) + 260888070*a(n-3) - 39883405500*a(n-4) + 3492052425000*a(n-5) - 177328940580000*a(n-6) + 5153150631600000*a(n-7) - 82577533320000000*a(n-8) + 669410956800000000*a(n-9) - 2224399449600000000*a(n-10) + 1632586752000000000*a(n-11) for n >= 12. [It is correct; see the comments above.]

a(n) = -1 + 2*6^n + 2*15^n + 20^n - 3*30^n - 6*60^n - 90^n + 4*120^n + 6*180^n - 5*360^n + 720^n for n >= 1. - Petros Hadjicostas, Sep 08 2019

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

Original entry on oeis.org

1, 3081513, 53090086057, 429966316953825, 2675558106868421881, 14895038886845467640193, 78785944892341703819175577, 406643086764765052892275303425, 2073826171428339544452057104498041

Offset: 1

R. H. Hardin, May 28 2012

nonn

From Petros Hadjicostas, Aug 25 2019: (Start)
We have a(m) = R(m,n=7,t=0) = A212855(m,7) for m >= 1, where R(m,n,t) = LHS of Eq. (6) of Abramson and Promislow (1978, p. 248).
Let P_7 be the set of all lists b = (b_1, b_2,..., b_7) of integers b_i >= 0, i = 1, ..., 7 such that 1*b_1 + 2*b_2 + ... + 7*b_7 = 7; i.e., P_7 is the set all integer partitions of 7. Then |P_7| = A000041(7) = 15.
We have a(m) = A212855(m,7) = Sum_{b in P_7} (-1)^(7 - Sum_{j=1..7} b_j) * (b_1 + b_2 + ... + b_7)!/(b_1! * b_2! * ... * b_7!) * (7! / ((1!)^b_1 * (2!)^b_2 * ... * (7!)^b_7))^m.
The integer partitions of 7 are listed on p. 831 of Abramowitz and Stegun (1964). We see that, when (b_1, b_2, ..., b_7) = (0, 2, 1, 0, 0, 0, 0) or (3, 0, 0, 1, 0, 0, 0) (i.e., we have the partitions 2+2+3 and 1+1+1+4), the corresponding multinomial coefficients are 210 = 7!/(2!2!3!) = 7!/(1!1!1!4!), so the number of terms in the expression for a(m) is |P_7| - 1 = 15 - 1 = 14 (see below in the Formula section).
Let M_7 := [1, 7, 21, 35, 42, 105, 140, 210, 420, 630, 840, 1260, 2520, 5040] be the A070289(7) = 15 - 1 = 14 distinct multinomial coefficients corresponding to the 15 integer partitions of 7 in P_7. The characteristic equation of the recurrence for a(m) is f(x) := Product_{r in M_7} (x-r) = Sum_{i = 0..14} (-1)^{14-i} * c_i * x^i. It turns out that c_{14} = 1, c_{13} = 11271, c_{12} = 46169368, c_{11} = 92088653622, and so on (see R. H. Hardin's recurrence below), and c_0 = 2372695722072874920960000000000 = product of elements in M_7.
It follows that a(m) satisfies the recurrence Sum_{i = 0..14} (-1)^{14-i} * c_i * a(m-i) = 0, which is equivalent to  R. H. Hardin's empirical recurrence below.
If we count the multinomial coefficient 210 twice in the characteristic equation (since it corresponds to two different integer partitions of 7) then we get (x-210)*f(x) = Sum_{i = 0..15} (-1)^{15-i} * d_i * x^i, where (d_0, d_1, ..., d_15) is row k = 7 in irregular triangular array A309951. We have d_{15} = 1, d_{14} = 11481, ..., d_0 = 498266101635303733401600000000000 (see Alois P. Heinz's b-file for A309951 with entries 37 to 52). Note that d_0 = 210 * c_0.
We then have Sum_{s = 0..15} (-1)^s * A309951(7, s) * a(m-s) = 0 for m >= 16. The latter recurrence is of order 15, and it is not minimal (as opposed to the one below by R. H. Hardin, which is of order 14 and minimal).
(End)

			Some solutions for n=3
..0..3..4..1..5..2..6....0..3..4..1..5..2..6....0..3..4..1..5..2..6
..1..0..3..5..2..6..4....1..0..3..2..4..5..6....1..0..4..2..5..6..3
..5..2..1..0..6..3..4....4..6..5..1..0..3..2....2..4..0..6..3..5..1

R. H. Hardin, Table of n, a(n) for n = 1..210
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) (with t=0), p. 248, and the comments above.
Wikipedia, Partition (number theory).

Column 7 of A212855.

Cf. A000041, A070289, A212850, A212851, A212852, A212853, A212856, A309951, A325305.

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, 7];
Table[a[n], {n, 1, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A212855 *)

Empirical: a(n) = 11271*a(n-1) -46169368*a(n-2) +92088653622*a(n-3) -100896701243149*a(n-4) +64220064122517975*a(n-5) -24283767237355832850*a(n-6) +5479502670227877007500*a(n-7) -734487423806273666445000*a(n-8) +57519812656973505919500000*a(n-9) -2547756421856270328438000000*a(n-10) +60760702040873540340600000000*a(n-11) -700874827794270417254400000000*a(n-12) +3015300813467611878720000000000*a(n-13) -2372695722072874920960000000000*a(n-14). [It is correct; see the comments above and one of the formulas below.]
a(n) = 1 - 2*7^n - 2*21^n - 2*35^n + 3*42^n + 6*105^n + 3*140^n - 210^n - 12*420^n - 4*630^n + 5*840^n + 10*1260^n - 6*2520^n + 5040^n. - Petros Hadjicostas, Aug 25 2019
Sum_{s = 0..14} (-1)^s * A325305(7, s) * a(n-s) = 0 for n >= 15. (This is the same as R. H. Hardin's recurrence above, and it follows from Eq. (6), p. 248, in Abramson and Promislow (1978) with t=0.) - Petros Hadjicostas, Sep 06 2019

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

A325308 Sum of all distinct multinomial coefficients M(n;lambda), where lambda ranges over the partitions of n.

Original entry on oeis.org

1, 1, 3, 10, 47, 246, 1602, 11271, 93767, 847846, 8618738, 94966191, 1149277802, 14946737339, 210112991441, 3152429219400, 50538450211103, 859238687076542, 15481605986593038, 294161321911723167, 5886118362589143742, 123610854463260840735, 2720101086040978435931

Offset: 0

Alois P. Heinz, Sep 05 2019

nonn

Differs from A005651 first at n = 7: a(n) = 11271 < 11481 = A005651(7).

Alois P. Heinz, Table of n, a(n) for n = 0..90
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.
Wikipedia, Multinomial coefficients.
Wikipedia, Partition (number theory).

Column k=1 of A325305.

Cf. A005651.

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:
a:= n-> add(i, i=g(n$2)):
seq(a(n), n=0..23);

g[n_, i_] := g[n, i] = If[n == 0 || i == 1, {n!}, Union[Map[Function[x, Binomial[n, i] x], g[n - i, Min[n - i, i]]], g[n, i - 1]]];
a[n_] := Total[g[n, n]];
a /@ Range[0, 23] (* Jean-François Alcover, May 06 2020, after Maple *)

cp's OEIS Frontend

A070289 Number of distinct values of multinomial coefficients ( n / (p1, p2, p3, ...) ) where (p1, p2, p3, ...) runs over all partitions of n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A325308 Sum of all distinct multinomial coefficients M(n;lambda), where lambda ranges over the partitions of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple