A240315 Triangular array read by rows: T(n,k) is the number of compositions of n into exactly k parts in which no part is unique (each part occurs at least twice).

1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 6, 0, 1, 0, 0, 0, 0, 0, 10, 0, 1, 0, 0, 1, 0, 7, 10, 15, 0, 1, 0, 0, 0, 1, 0, 10, 20, 21, 0, 1, 0, 0, 1, 0, 12, 1, 30, 35, 28, 0, 1, 0, 0, 0, 0, 0, 20, 0, 56, 56, 36, 0, 1, 0, 0, 1, 1, 13, 10, 126, 21, 98, 84, 45, 0, 1

Offset

0,26

Comments

Row sums = A240085.

References

S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Chapman and Hall, 2009 page 87.

Links

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

Formula

Product_{i>=1} exp(x^i*y) - x^i*y = Sum_{k>=0} A_k(x)*y^k/k!, where A_k(x) is the o.g.f. for the number of compositions of n into k parts in which no part is unique. In other words, A_k(x) is the o.g.f. for column k.

Example

Triangle begins:
  1;
  0, 0;
  0, 0, 1;
  0, 0, 0, 1;
  0, 0, 1, 0,  1;
  0, 0, 0, 0,  0,  1;
  0, 0, 1, 1,  6,  0,   1;
  0, 0, 0, 0,  0, 10,   0,  1;
  0, 0, 1, 0,  7, 10,  15,  0,  1;
  0, 0, 0, 1,  0, 10,  20, 21,  0,  1;
  0, 0, 1, 0, 12,  1,  30, 35, 28,  0,  1;
  0, 0, 0, 0,  0, 20,   0, 56, 56, 36,  0, 1;
  0, 0, 1, 1, 13, 10, 126, 21, 98, 84, 45, 0, 1;
  ...
T(8,4) = 7 because we have: 3+3+1+1, 3+1+3+1, 3+1+1+3, 1+3+3+1, 1+3+1+3, 1+1+3+3, 2+2+2+2.

Maple

b:= proc(n, i, t) option remember; `if`(n=0, t!, `if`(i<1, 0,
      expand(b(n, i-1, t)+add(x^j*b(n-i*j, i-1, t+j)/j!, j=2..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$2, 0)):
seq(T(n), n=0..14);  # Alois P. Heinz, Apr 03 2014

Mathematica

nn=10; Table[Take[Transpose[Range[0, nn]!CoefficientList[Series[ Product[Exp[x^i y]-x^i y, {i, 1, nn}], {y, 0, nn}], {y, x}]], nn+1][[j, Range[1, j]]], {j, 1, nn}]//Grid

Crossrefs

Sequence in context: A293568 A192072 A060297 * A339431 A256041 A137378

Adjacent sequences: A240312 A240313 A240314 * A240316 A240317 A240318

Keyword

nonn,tabl

Author

Geoffrey Critzer, Apr 03 2014

Status

approved