A134431 Triangle read by rows: T(n,k) is the number of arrangements of the set {1,2,...,n} in which the sum of the entries is equal to k (n >= 0, k >= 0; to n=0 there corresponds the empty set).
1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 2, 6, 1, 1, 1, 3, 3, 4, 8, 8, 6, 6, 24, 1, 1, 1, 3, 3, 5, 10, 10, 14, 14, 36, 30, 30, 24, 24, 120, 1, 1, 1, 3, 3, 5, 11, 12, 16, 22, 44, 44, 66, 60, 78, 174, 168, 144, 144, 120, 120, 720, 1, 1, 1, 3, 3, 5, 11, 13, 18, 24, 52, 52, 80, 98, 120, 234
Offset: 0
Examples
T(4,7)=8 because we have 34,43 and the six permutations of {1,2,4}.
Triangle starts:
1;
1, 1;
1, 1, 1, 2;
1, 1, 1, 3, 2, 2, 6;
1, 1, 1, 3, 3, 4, 8, 8, 6, 6, 24;
Links
- Alois P. Heinz, Rows n = 0..48, flattened
Programs
-
Maple
Q[0]:=1: for n to 7 do Q[n]:=sort(simplify(Q[n-1]+t^n*x*(diff(x*Q[n-1],x))), t) end do: for n from 0 to 7 do P[n]:=sort(subs(x=1,Q[n])) end do: for n from 0 to 7 do seq(coeff(P[n],t,j),j=0..(1/2)*n*(n+1)) end do; # yields sequence in triangular form # second Maple program: b:= proc(n, s, t) option remember; `if`(n=0, t!*x^s, b(n-1, s, t)+b(n-1, s+n, t+1)) end: T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)): seq(T(n), n=0..8); # Alois P. Heinz, Dec 22 2017 -
Mathematica
b[n_, s_, t_] := b[n, s, t] = If[n == 0, t!*x^s, b[n - 1, s, t] + b[n - 1, s + n, t + 1]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]] @ b[n, 0, 0]; T /@ Range[0, 8] // Flatten (* Jean-François Alcover, Feb 19 2020, after Alois P. Heinz *)
Formula
The row generating polynomials P[n](t) are equal to Q[n](t,1), where the polynomials Q[n](t,x) are defined by Q[0]=1 and Q[n]=Q[n-1] + xt^n (d/dx)xQ[n-1]. [Q[n](t,x) is the bivariate generating polynomial of the arrangements of {1,2,...,n}, where t (x) marks the sum (number) of the entries; for example, Q[2](t,x)=1+tx + t^2*x + 2t^3*x^2, corresponding to: empty, 1, 2, 12 and 21, respectively.]
Comments