A261959 Number A(n,k) of ordered set partitions of {1,2,...,n} such that no part has the same size as any of its k immediate predecessors; square array A(n,k), n>=0, k>=0, read by antidiagonals.
1, 1, 1, 1, 1, 3, 1, 1, 1, 13, 1, 1, 1, 7, 75, 1, 1, 1, 7, 21, 541, 1, 1, 1, 7, 9, 81, 4683, 1, 1, 1, 7, 9, 31, 793, 47293, 1, 1, 1, 7, 9, 31, 403, 4929, 545835, 1, 1, 1, 7, 9, 31, 403, 1597, 33029, 7087261, 1, 1, 1, 7, 9, 31, 403, 757, 7913, 388537, 102247563
Offset: 0
Examples
A(3,1) = 7: 123, 1|23, 23|1, 2|13, 13|2, 3|12, 12|3. A(4,1) = 21: 1234, 1|234, 234|1, 2|134, 134|2, 3|124, 124|3, 4|123, 123|4, 3|12|4, 4|12|3, 2|13|4, 4|13|2, 2|14|3, 3|14|2, 1|23|4, 4|23|1, 1|24|3, 3|24|1, 1|34|2, 2|34|1. Square array A(n,k) begins: : 1, 1, 1, 1, 1, 1, 1, ... : 1, 1, 1, 1, 1, 1, 1, ... : 3, 1, 1, 1, 1, 1, 1, ... : 13, 7, 7, 7, 7, 7, 7, ... : 75, 21, 9, 9, 9, 9, 9, ... : 541, 81, 31, 31, 31, 31, 31, ... : 4683, 793, 403, 403, 403, 403, 403, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..50, flattened
Crossrefs
Programs
-
Maple
b:= proc(n, l) option remember; `if`(n=0, 1, add(`if`(j in l, 0, binomial(n, j)*b(n-j, `if`(l=[], [], [subsop(1=NULL, l)[], j]))), j=1..n)) end: A:= (n, k)-> b(n, [0$min(n,k)]): seq(seq(A(n, d-n), n=0..d), d=0..10); -
Mathematica
b[n_, l_List] := b[n, l] = If[n == 0, 1, Sum[If[MemberQ[l, j], 0, Binomial[n, j]*b[n-j, If[l == {}, {}, Append[ReplacePart[l, 1 -> Nothing], j]]]], {j, 1, n}]]; A[n_, k_] := b[n, Array[0&, Min[n, k]]]; Table[A[n, d-n], {d, 0, 10} , {n, 0, d}] // Flatten (* Jean-François Alcover, Dec 17 2016, after Alois P. Heinz *)