A275422 - OEIS

A275422

Number A(n,k) of set partitions of [n] such that k is a multiple of each block size; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%I #13 Feb 08 2017 04:12:30

%S 1,1,1,1,1,2,1,1,1,5,1,1,2,1,15,1,1,1,4,1,52,1,1,2,2,10,1,203,1,1,1,4,

%T 5,26,1,877,1,1,2,1,11,11,76,1,4140,1,1,1,5,1,31,31,232,1,21147,1,1,2,

%U 1,14,2,106,106,764,1,115975,1,1,1,4,1,46,7,372,337,2620,1,678570

%N Number A(n,k) of set partitions of [n] such that k is a multiple of each block size; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%H Alois P. Heinz, <a href="/A275422/b275422.txt">Antidiagonals n = 0..200, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>

%F E.g.f. for column k>0: exp(Sum_{d|k} x^d/d!), for k=0: exp(exp(x)-1).

%e A(5,3) = 11: 123|4|5, 124|3|5, 125|3|4, 134|2|5, 135|2|4, 1|234|5, 1|235|4, 145|2|3, 1|245|3, 1|2|345, 1|2|3|4|5.

%e A(4,4) = 11: 1234, 12|34, 12|3|4, 13|24, 13|2|4, 14|23, 1|23|4, 14|2|3, 1|24|3, 1|2|34, 1|2|3|4.

%e A(6,5) = 7: 12345|6, 12346|5, 12356|4, 12456|3, 13456|2, 1|23456, 1|2|3|4|5|6.

%e Square array A(n,k) begins:

%e : 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e : 2, 1, 2, 1, 2, 1, 2, 1, 2, ...

%e : 5, 1, 4, 2, 4, 1, 5, 1, 4, ...

%e : 15, 1, 10, 5, 11, 1, 14, 1, 11, ...

%e : 52, 1, 26, 11, 31, 2, 46, 1, 31, ...

%e : 203, 1, 76, 31, 106, 7, 167, 1, 106, ...

%e : 877, 1, 232, 106, 372, 22, 659, 2, 372, ...

%e : 4140, 1, 764, 337, 1499, 57, 2836, 9, 1500, ...

%p A:= proc(n, k) option remember; `if`(n=0, 1, add(

%p `if`(j>n, 0, A(n-j, k)*binomial(n-1, j-1)), j=

%p `if`(k=0, 1..n, numtheory[divisors](k))))

%p end:

%p seq(seq(A(n, d-n), n=0..d), d=0..14);

%t A[n_, k_] := A[n, k] = If[n==0, 1, Sum[If[j>n, 0, A[n-j, k]*Binomial[n-1, j - 1]], {j, If[k==0, Range[n], Divisors[k]]}]]; Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* _Jean-François Alcover_, Feb 08 2017, translated from Maple *)

%Y Columns k=0-10 give: A000110, A000012, A000085, A190865, A190452, A275423, A275424, A275425, A275426, A275427, A275428.

%Y Main diagonal gives A275429.

%K nonn,tabl

%O 0,6

%A _Alois P. Heinz_, Jul 27 2016