login
A260883
Number of m-shape ordered set partitions, square array read by ascending antidiagonals, A(m, n) for m, n >= 0.
3
1, 1, 1, 1, 1, 3, 1, 1, 3, 9, 1, 1, 7, 13, 35, 1, 1, 21, 121, 75, 161, 1, 1, 71, 1849, 3907, 541, 913, 1, 1, 253, 35641, 426405, 202741, 4683, 6103, 1, 1, 925, 762763, 65782211, 203374081, 15430207, 47293, 47319, 1, 1, 3433, 17190265, 11872636325, 323213457781, 173959321557
OFFSET
1,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. It is ordered if the positions of the blocks are taken into account.
If m = 0, all possible sizes are zero. Thus the number of ordered set partitions of 0-shape is the number of ordered partitions of n (partition numbers A101880).
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 ordered set partitions of 1-shape is a Fubini number (sequence A000670).
If m = 2, the set is {1, 2, ..., 2n} and the number of ordered set partitions of 2-shape is also the number of 2-packed words of degree n (sequence A094088).
FORMULA
From Petros Hadjicostas, Aug 02 2019: (Start)
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]) * multinomial(a_1 + ... + a_n, [a_1,..., 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)
EXAMPLE
[ n ] [0 1 2 3 4 5 6]
[ m ] -----------------------------------------------------------
[ 0 ] [1, 1, 3, 9, 35, 161, 913] A101880
[ 1 ] [1, 1, 3, 13, 75, 541, 4683] A000670
[ 2 ] [1, 1, 7, 121, 3907, 202741, 15430207] A094088
[ 3 ] [1, 1, 21, 1849, 426405, 203374081, 173959321557] A243664
[ 4 ] [1, 1, 71, 35641, 65782211, 323213457781, 3482943541940351] A243665
For example the number of ordered set partitions of {1,2,...,9} with sizes in [9], [6,3] and [3,3,3] is 1, 168 and 1680 respectively. Thus A(3,3) = 1849.
Formatted as a triangle:
[1]
[1, 1]
[1, 1, 3]
[1, 1, 3, 9]
[1, 1, 7, 13, 35]
[1, 1, 21, 121, 75, 161]
[1, 1, 71, 1849, 3907, 541, 913]
[1, 1, 253, 35641, 426405, 202741, 4683, 6103]
PROG
(Sage)
def A260883(m, n):
shapes = ([x*m for x in p] for p in Partitions(n))
return sum(factorial(len(s))*SetPartitions(sum(s), s).cardinality() for s in shapes)
for m in (0..4): print([A260883(m, n) for n in (0..6)])
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Aug 02 2015
STATUS
approved