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,7

Comments

Row n has 1 + n(n+1)/2 terms (n >= 0). Row sums yield the arrangement numbers (A000522). T(n, n(n+1)/2) = n!. Sum_{k=0..n(n+1)/2} k*T(n,k) = A134432(n).

Links

Alois P. Heinz, Rows n = 0..48, flattened

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.]

Example

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;

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 *)

Crossrefs

Cf. A000522, A134432.

Sequence in context: A029332 A358172 A344058 * A211098 A070879 A125644

Adjacent sequences: A134428 A134429 A134430 * A134432 A134433 A134434

Keyword

nonn,tabf

Author

Emeric Deutsch, Nov 16 2007

Status

approved