|
%I #91 Dec 20 2023 15:08:55
%S 1,1,1,1,1,2,1,1,2,3,1,1,4,5,5,1,1,11,31,15,7,1,1,36,365,379,52,11,1,
%T 1,127,6271,25323,6556,203,15,1,1,463,129130,3086331,3068521,150349,
%U 877,22,1,1,1717,2877421,512251515,3309362716,583027547,4373461,4140,30
%N Number of m-shape set partitions, square array read by ascending antidiagonals, A(m,n) for m, n >= 0.
%C A set partition of m-shape is a partition of a set with cardinality m*n for some n >= 0 such that the sizes of the blocks are m times the parts of the integer partitions of n.
%C If m = 0, all possible sizes are zero. Thus the number of set partitions of 0-shape is the number of integer partitions of n (partition numbers A000041).
%C If m = 1, the set is {1, 2, ..., n} and the set of all possible sizes are the integer partitions of n. Thus the number of set partitions of 1-shape is the number of set partitions (Bell numbers A000110).
%C If m = 2, the set is {1, 2, ..., 2n} and the number of set partitions of 2-shape is the number of set partitions into even blocks A005046.
%C From _Petros Hadjicostas_, Aug 06 2019: (Start)
%C Irwin (1916) proved the following combinatorial result: Assume r_1, r_2, ..., r_n are positive integers and we have r_1*r_2*...*r_n objects. We divide them into r_1 classes of r_2*r_3*...*r_n objects each, then each class into r_2 subclasses of r_3*...*r_n objects each, and so on. We call each such classification, without reference to order, a "classification" par excellence. He proved that the total number of classifications is (r_1*r_2*...*r_n)!/( r1! * (r_2!)^(r_1) * (r_3!)^(r_1*r_2) * ... (r_n!)^(r_1*r_2*...*r_{n-1}) ).
%C Apparently, this problem appeared in Carmichael's "Theory of Numbers".
%C This result can definitely be used to prove some special cases of my conjecture below. (End)
%H Alois P. Heinz, <a href="/A260876/b260876.txt">Antidiagonals n = 0..54, flattened</a>
%H Frank Irwin, <a href="https://www.jstor.org/stable/2974030">Solution to Problem 223 proposed by T. E. Mason in October 1914</a>, Amer. Math. Monthly 23(9) (1916), 352-353.
%F From _Petros Hadjicostas_, Aug 02 2019: (Start)
%F A(m, 2) = 1 + (1/2) * binomial(2*m, m) for m >= 1.
%F A(m, 3) = 1 + binomial(3*m, m) + (3*m)!/(6 * (m!)^3) for m >= 1.
%F A(m, 4) = (1/4!) * multinomial(4*m, [m, m, m, m]) + (1/2) * multinomial(4*m, [2*m, m, m]) + multinomial(4*m, [m, 3*m]) + (1/2) * multinomial(4*m, [2*m, 2*m]) + 1 for m >= 1.
%F Conjecture: For n >= 0, let P be the set of all possible lists (a_1,...,a_n) of nonnegative integers such that a_1*1 + a_2*2 + ... + a_n*n = n. Consider terms of the form multinomial(n*m, m*[1,..., 1,2,..., 2,..., n,..., n])/(a_1! * a_2! * ... * a_n!), where in the list [1,...,1,2,...,2,...,n,...,n] the number 1 occurs a_1 times, 2 occurs a_2 times, ..., and n occurs a_n times. (Here a_n = 0 or 1.) Summing these terms over P we get A(m, n) provided m >= 1. (End)
%F Conjecture for a recurrence: A(m, n) = Sum_{k = 0..n-1} binomial(m*n - 1, m*k) * A(m, k) with A(m, 0) = 1 for m >= 1 and n >= 0. (Unfortunately, the recurrence does not hold for m = 0.) - _Petros Hadjicostas_, Aug 12 2019
%e [ n ] [0 1 2 3 4 5 6]
%e [ m ] ------------------------------------------------------
%e [ 0 ] [1, 1, 2, 3, 5, 7, 11] A000041
%e [ 1 ] [1, 1, 2, 5, 15, 52, 203] A000110
%e [ 2 ] [1, 1, 4, 31, 379, 6556, 150349] A005046
%e [ 3 ] [1, 1, 11, 365, 25323, 3068521, 583027547] A291973
%e [ 4 ] [1, 1, 36, 6271, 3086331, 3309362716, 6626013560301] A291975
%e A260878,A309725, ...
%e For example the number of set partitions of {1,2,...,9} with sizes in [9], [6,3] and [3,3,3] is 1, 84 and 280 respectively. Thus A(3,3) = 365.
%e Formatted as a triangle:
%e [1]
%e [1, 1]
%e [1, 1, 2]
%e [1, 1, 2, 3]
%e [1, 1, 4, 5, 5]
%e [1, 1, 11, 31, 15, 7]
%e [1, 1, 36, 365, 379, 52, 11]
%e [1, 1, 127, 6271, 25323, 6556, 203, 15]
%e .
%e From _Peter Luschny_, Aug 14 2019: (Start)
%e For example consider the case n = 4. There are five integer partitions of 4:
%e P = [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]. The shapes are m times the parts of the integer partitions: S(m) = [[4m], [3m, m], [2m, 2m], [2m, m, m], [m, m, m, m]].
%e * In the case m = 1 we look at set partitions of {1, 2, 3, 4} with sizes in [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]] which gives rise to [1, 4, 3, 6, 1] with sum 15.
%e * In the case m = 2 we look at set partitions of {1, 2, .., 8} with sizes in [[8], [6, 2], [4, 4], [4, 2, 2], [2, 2, 2, 2]] which gives rise to [1, 28, 35, 210, 105] with sum 379.
%e * In the case m = 0 we look at set partitions of {} with sizes in [[0], [0, 0], [0, 0], [0, 0, 0], [0, 0, 0, 0]] which gives rise to [1, 1, 1, 1, 1] with sum 5 (because the only partition of the empty set is the set that contains the empty set, thus from the definition T(0,4) = Sum_{S(0)} card({0}) = A000041(4) = 5).
%e If n runs through 0, 1, 2,... then the result is an irregular triangle in which the n-th row lists multinomials for partitions of [m*n] which have only parts which are multiples of m. These are the triangles A080575 (m = 1), A257490 (m = 2), A327003 (m = 3), A327004 (m = 4). In the case m = 0 the triangle is A000012 subdivided into rows of length A000041. See the cross references how this case integrates into the full picture.
%e (End)
%p A:= proc(m, n) option remember; `if`(m=0, combinat[numbpart](n),
%p `if`(n=0, 1, add(binomial(m*n-1, m*k-1)*A(m, n-k), k=1..n)))
%p end:
%p seq(seq(A(d-n, n), n=0..d), d=0..10); # _Alois P. Heinz_, Aug 14 2019
%t A[m_, n_] := A[m, n] = If[m==0, PartitionsP[n], If[n==0, 1, Sum[Binomial[m n - 1, m k - 1] A[m, n - k], {k, 1, n}]]];
%t Table[Table[A[d - n, n], {n, 0, d}], {d, 0, 10}] // Flatten (* _Jean-François Alcover_, Dec 06 2019, after _Alois P. Heinz_ *)
%o (SageMath)
%o def A260876(m, n):
%o shapes = ([x*m for x in p] for p in Partitions(n))
%o return sum(SetPartitions(sum(s), s).cardinality() for s in shapes)
%o for m in (0..4): print([A260876(m,n) for n in (0..6)])
%Y -----------------------------------------------------------------
%Y [m] | multi- | sum of | main | by | comple- |
%Y | nomials | rows | diagonal | size | mentary |
%Y -----------------------------------------------------------------
%Y [0] | A000012 | A000041 | A000012 | A008284 | A081362 |
%Y [1] | A036040 | A000110 | A000012 | A048993 | A000587 |
%Y [2] | A257490 | A005046 | A001147 | A156289 | A260884 |
%Y [3] | A327003 | A291973 | A025035 | A291451 | A291974 |
%Y [4] | A327004 | A291975 | A025036 | A291452 | A291976 |
%Y Cf. A326996 (main diagonal), A260883 (ordered), A260875 (complementary).
%Y Columns include A000012, A260878, A309725.
%K nonn,tabl
%O 0,6
%A _Peter Luschny_, Aug 02 2015
|
