cp's OEIS Frontend

A260876 Number of m-shape set partitions, square array read by ascending antidiagonals, A(m,n) for m, n >= 0.

%I A260876 #91 Dec 20 2023 15:08:55
%S A260876 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 A260876 1,127,6271,25323,6556,203,15,1,1,463,129130,3086331,3068521,150349,
%U A260876 877,22,1,1,1717,2877421,512251515,3309362716,583027547,4373461,4140,30
%N A260876 Number of m-shape set partitions, square array read by ascending antidiagonals, A(m,n) for m, n >= 0.
%C A260876 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 A260876 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 A260876 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 A260876 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 A260876 From _Petros Hadjicostas_, Aug 06 2019: (Start)
%C A260876 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 A260876 Apparently, this problem appeared in Carmichael's "Theory of Numbers".
%C A260876 This result can definitely be used to prove some special cases of my conjecture below. (End)
%H A260876 Alois P. Heinz, <a href="/A260876/b260876.txt">Antidiagonals n = 0..54, flattened</a>
%H A260876 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 A260876 From _Petros Hadjicostas_, Aug 02 2019: (Start)
%F A260876 A(m, 2) = 1 + (1/2) * binomial(2*m, m) for m >= 1.
%F A260876 A(m, 3) = 1 + binomial(3*m, m) + (3*m)!/(6 * (m!)^3) for m >= 1.
%F A260876 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 A260876 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 A260876 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 A260876 [ n ] [0  1   2       3        4           5              6]
%e A260876 [ m ] ------------------------------------------------------
%e A260876 [ 0 ] [1, 1,  2,      3,       5,          7,            11]  A000041
%e A260876 [ 1 ] [1, 1,  2,      5,      15,         52,           203]  A000110
%e A260876 [ 2 ] [1, 1,  4,     31,     379,       6556,        150349]  A005046
%e A260876 [ 3 ] [1, 1, 11,    365,   25323,    3068521,     583027547]  A291973
%e A260876 [ 4 ] [1, 1, 36,   6271, 3086331, 3309362716, 6626013560301]  A291975
%e A260876         A260878,A309725, ...
%e A260876 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 A260876 Formatted as a triangle:
%e A260876 [1]
%e A260876 [1, 1]
%e A260876 [1, 1,   2]
%e A260876 [1, 1,   2,    3]
%e A260876 [1, 1,   4,    5,     5]
%e A260876 [1, 1,  11,   31,    15,    7]
%e A260876 [1, 1,  36,  365,   379,   52,  11]
%e A260876 [1, 1, 127, 6271, 25323, 6556, 203, 15]
%e A260876 .
%e A260876 From _Peter Luschny_, Aug 14 2019: (Start)
%e A260876 For example consider the case n = 4. There are five integer partitions of 4:
%e A260876   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 A260876 * 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 A260876 * 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 A260876 * 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 A260876 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 A260876 (End)
%p A260876 A:= proc(m, n) option remember; `if`(m=0, combinat[numbpart](n),
%p A260876       `if`(n=0, 1, add(binomial(m*n-1, m*k-1)*A(m, n-k), k=1..n)))
%p A260876     end:
%p A260876 seq(seq(A(d-n, n), n=0..d), d=0..10);  # _Alois P. Heinz_, Aug 14 2019
%t A260876 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 A260876 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 A260876 (SageMath)
%o A260876 def A260876(m, n):
%o A260876     shapes = ([x*m for x in p] for p in Partitions(n))
%o A260876     return sum(SetPartitions(sum(s), s).cardinality() for s in shapes)
%o A260876 for m in (0..4): print([A260876(m,n) for n in (0..6)])
%Y A260876 -----------------------------------------------------------------
%Y A260876 [m] |  multi-   |  sum of   |  main     |  by       |  comple-  |
%Y A260876     |  nomials  |  rows     |  diagonal |  size     |  mentary  |
%Y A260876 -----------------------------------------------------------------
%Y A260876 [0] |  A000012  |  A000041  |  A000012  |  A008284  |  A081362  |
%Y A260876 [1] |  A036040  |  A000110  |  A000012  |  A048993  |  A000587  |
%Y A260876 [2] |  A257490  |  A005046  |  A001147  |  A156289  |  A260884  |
%Y A260876 [3] |  A327003  |  A291973  |  A025035  |  A291451  |  A291974  |
%Y A260876 [4] |  A327004  |  A291975  |  A025036  |  A291452  |  A291976  |
%Y A260876 Cf. A326996 (main diagonal), A260883 (ordered), A260875 (complementary).
%Y A260876 Columns include A000012, A260878, A309725.
%K A260876 nonn,tabl
%O A260876 0,6
%A A260876 _Peter Luschny_, Aug 02 2015