A260876 Number of m-shape set partitions, square array read by ascending antidiagonals, A(m,n) for m, n >= 0.
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
Offset: 0
Examples
[ 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
A260878,A309725, ...
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]
.
From _Peter Luschny_, Aug 14 2019: (Start)
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)
Links
- Alois P. Heinz, Antidiagonals n = 0..54, flattened
- Frank Irwin, Solution to Problem 223 proposed by T. E. Mason in October 1914, Amer. Math. Monthly 23(9) (1916), 352-353.
Crossrefs
-----------------------------------------------------------------
[m] | multi- | sum of | main | by | comple- |
| nomials | rows | diagonal | size | mentary |
-----------------------------------------------------------------
Programs
-
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: seq(seq(A(d-n, n), n=0..d), d=0..10); # Alois P. Heinz, Aug 14 2019 -
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}]]]; Table[Table[A[d - n, n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 06 2019, after Alois P. Heinz *) -
SageMath
def A260876(m, n): 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)])
Formula
From Petros Hadjicostas, Aug 02 2019: (Start)
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
Comments