|
| |
|
|
A260876
|
|
Number of m-shape set partitions, square array read by ascending antidiagonals, A(m,n) for m, n >= 0.
|
|
11
|
|
|
|
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, 1, 127, 6271, 25323, 6556, 203, 15, 1, 1, 463, 129130, 3086331, 3068521, 150349, 877, 22, 1, 1, 1717, 2877421, 512251515, 3309362716, 583027547, 4373461, 4140, 30
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,6
|
|
|
COMMENTS
|
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.
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).
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).
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.
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}) ).
Apparently, this problem appeared in Carmichael's "Theory of Numbers".
This result can definitely be used to prove some special cases of my conjecture below. (End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
A(m, 2) = 1 + (1/2) * binomial(2*m, m) for m >= 1.
A(m, 3) = 1 + binomial(3*m, m) + (3*m)!/(6 * (m!)^3) for m >= 1.
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.
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)
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
|
|
|
EXAMPLE
|
[ n ] [0 1 2 3 4 5 6]
[ m ] ------------------------------------------------------
[ 0 ] [1, 1, 2, 3, 5, 7, 11] A000041
[ 1 ] [1, 1, 2, 5, 15, 52, 203] A000110
[ 2 ] [1, 1, 4, 31, 379, 6556, 150349] A005046
[ 3 ] [1, 1, 11, 365, 25323, 3068521, 583027547] A291973
[ 4 ] [1, 1, 36, 6271, 3086331, 3309362716, 6626013560301] A291975
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.
Formatted as a triangle:
[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, 1, 127, 6271, 25323, 6556, 203, 15]
.
For example consider the case n = 4. There are five integer partitions of 4:
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]].
* 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.
* 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.
* 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).
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.
(End)
|
|
|
MAPLE
|
A:= proc(m, n) option remember; `if`(m=0, combinat[numbpart](n),
`if`(n=0, 1, add(binomial(m*n-1, m*k-1)*A(m, n-k), k=1..n)))
end:
|
|
|
MATHEMATICA
|
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}]]];
|
|
|
PROG
|
(SageMath)
shapes = ([x*m for x in p] for p in Partitions(n))
return sum(SetPartitions(sum(s), s).cardinality() for s in shapes)
for m in (0..4): print([A260876(m, n) for n in (0..6)])
|
|
|
CROSSREFS
|
-----------------------------------------------------------------
[m] | multi- | sum of | main | by | comple- |
| nomials | rows | diagonal | size | mentary |
-----------------------------------------------------------------
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
