A134431 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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