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.
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, 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, 1, 14, 2, 106, 106, 764, 1, 115975, 1, 1, 1, 4, 1, 46, 7, 372, 337, 2620, 1, 678570
Offset: 0
Examples
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. 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. A(6,5) = 7: 12345|6, 12346|5, 12356|4, 12456|3, 13456|2, 1|23456, 1|2|3|4|5|6. Square array A(n,k) begins: : 1, 1, 1, 1, 1, 1, 1, 1, 1, ... : 1, 1, 1, 1, 1, 1, 1, 1, 1, ... : 2, 1, 2, 1, 2, 1, 2, 1, 2, ... : 5, 1, 4, 2, 4, 1, 5, 1, 4, ... : 15, 1, 10, 5, 11, 1, 14, 1, 11, ... : 52, 1, 26, 11, 31, 2, 46, 1, 31, ... : 203, 1, 76, 31, 106, 7, 167, 1, 106, ... : 877, 1, 232, 106, 372, 22, 659, 2, 372, ... : 4140, 1, 764, 337, 1499, 57, 2836, 9, 1500, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..200, flattened
- Wikipedia, Partition of a set
Crossrefs
Programs
-
Maple
A:= proc(n, k) option remember; `if`(n=0, 1, add( `if`(j>n, 0, A(n-j, k)*binomial(n-1, j-1)), j= `if`(k=0, 1..n, numtheory[divisors](k)))) end: seq(seq(A(n, d-n), n=0..d), d=0..14); -
Mathematica
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 *)
Formula
E.g.f. for column k>0: exp(Sum_{d|k} x^d/d!), for k=0: exp(exp(x)-1).