A290057 Number T(n,k) of X-rays of n X n binary matrices with exactly k ones; triangle T(n,k), n>=0, 0<=k<=n^2, read by rows.

1, 1, 1, 1, 3, 4, 3, 1, 1, 5, 13, 23, 30, 30, 23, 13, 5, 1, 1, 7, 26, 68, 139, 234, 334, 411, 440, 411, 334, 234, 139, 68, 26, 7, 1, 1, 9, 43, 145, 386, 860, 1660, 2838, 4362, 6090, 7779, 9135, 9892, 9892, 9135, 7779, 6090, 4362, 2838, 1660, 860, 386, 145, 43, 9, 1

Offset

0,5

Comments

The X-ray of a matrix is defined as the sequence of antidiagonal sums.

T(n,k) is defined for all n,k >= 0. The triangle contains only the positive terms. T(n,k) = 0 for k>n^2.

Links

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

C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.

Index entries for sequences related to binary matrices

Formula

T(n,floor(n^2/2)) = A290058(n).

T(n,k) = T(n,n^2-k).

Example

Triangle T(n,k) begins:
  1;
  1, 1;
  1, 3,  4,  3,   1;
  1, 5, 13, 23,  30,  30,  23,  13,   5,   1;
  1, 7, 26, 68, 139, 234, 334, 411, 440, 411, 334, 234, 139, 68, 26, 7, 1;
  ...

Maple

b:= proc(n, i, t) option remember; (m-> `if`(n>m, 0, `if`(n=m, 1,
      add(b(n-j, i-t, 1-t), j=0..min(i, n)))))(i*(i+1-t))
    end:
T:= (n, k)-> b(k, n, 1):
seq(seq(T(n, k), k=0..n^2), n=0..7);

Mathematica

b[n_, i_, t_]:= b[n, i, t] = Function[{m, jm}, If[n>m, 0, If[n==m, 1, Sum[b[n-j, i-t, 1-t], {j, 0, jm}]]]][i*(i+1-t), Min[i, n]]; T[n_, k_]:= b[k, n, 1]; Table[T[n, k], {n, 0, 7}, {k, 0, n^2}] // Flatten (* Jean-François Alcover, Aug 09 2017, translated from Maple *)

Crossrefs

Columns k=0-2 give: A000012, A004273, A091823(n-1) for n>1.

Main diagonal gives A290052.

Row sums give A010790.

Cf. A000290, A290058.

Sequence in context: A201162 A096646 A306234 * A249790 A302713 A136206

Adjacent sequences: A290054 A290055 A290056 * A290058 A290059 A290060

Keyword

nonn,tabf

Author

Alois P. Heinz, Jul 19 2017

Status

approved