A363519 Number T(n,k) of partitions of [n] having exactly k parity changes within the partition, n>=0, 0<=k<=max(0,n-1), read by rows.
1, 1, 0, 2, 0, 1, 4, 0, 3, 4, 8, 0, 2, 18, 14, 18, 0, 7, 27, 87, 42, 40, 0, 5, 102, 162, 360, 147, 101, 0, 20, 179, 866, 931, 1456, 434, 254, 0, 15, 675, 1746, 5836, 4755, 5778, 1619, 723, 0, 67, 1321, 9087, 16416, 36031, 22893, 23052, 5044, 2064, 0, 52, 5216, 19863, 93452, 117172, 206570, 115178, 94210, 20271, 6586
Offset: 0
Examples
T(4,1) = 3: 134|2, 13|24, 13|2|4. T(4,2) = 4: 124|3, 14|23, 14|2|3, 1|24|3. T(4,3) = 8: 1234, 123|4, 12|34, 12|3|4, 1|234, 1|23|4, 1|2|34, 1|2|3|4. T(5,2) = 18: 1245|3, 124|35, 124|3|5, 134|25, 134|2|5, 13|245, 13|24|5, 13|2|45, 13|2|4|5, 14|235, 14|23|5, 14|25|3, 14|2|35, 14|2|3|5, 15|24|3, 1|245|3, 1|24|35, 1|24|3|5. T(5,4) = 18: 12345, 1234|5, 123|45, 123|4|5, 12|345, 12|34|5, 12|3|45, 12|3|4|5, 145|23, 1|2345, 1|234|5, 1|23|45, 1|23|4|5, 145|2|3, 1|2|345, 1|2|34|5, 1|2|3|45, 1|2|3|4|5. Triangle T(n,k) begins: 1; 1; 0, 2; 0, 1, 4; 0, 3, 4, 8; 0, 2, 18, 14, 18; 0, 7, 27, 87, 42, 40; 0, 5, 102, 162, 360, 147, 101; 0, 20, 179, 866, 931, 1456, 434, 254; 0, 15, 675, 1746, 5836, 4755, 5778, 1619, 723; 0, 67, 1321, 9087, 16416, 36031, 22893, 23052, 5044, 2064; ...
Links
- Alois P. Heinz, Rows n = 0..27, flattened
- Wikipedia, Partition of a set
Crossrefs
Programs
-
Maple
b:= proc(l, i, t) option remember; expand(`if`(l=[], 1, add((f-> b(subsop(j=[][], l), j, `if`(f, 1-t, t))* `if`(f, x, 1))(l[j]=t), j=[1, $i..nops(l)]))) end: T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))( b([ seq(irem(i, 2), i=2..n)], 1, 0)): seq(T(n), n=0..12); -
Mathematica
b[l_, i_, t_] := b[l, i, t] = Expand[If[l == {}, 1, Sum[Function[f, b[ReplacePart[l, j -> Nothing], j, If[f, 1 - t, t]]*If[f, x, 1]][l[[j]] == t], {j, Join[{1}, Range[i, Length@l]]}]]]; T[n_] := CoefficientList[b[ Table[Mod[i, 2], {i, 2, n}], 1, 0], x]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Nov 17 2023, after Alois P. Heinz *)
Formula
Sum_{k=0..max(0,n-1)} k * T(n,k) = A363549(n).
Comments