A290058 -id:A290058 - cp's OEIS frontend

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

Alois P. Heinz, Jul 19 2017

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.

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

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

Columns k=0-2 give: A000012, A004273, A091823(n-1) for n>1.
Main diagonal gives A290052.
Row sums give A010790.
Cf. A000290, A290058.

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

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

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

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

A290134 Number of unique X-rays of n X n binary matrices with exactly floor(n^2/2) ones.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 130, 415, 1368, 4603, 15788, 54863, 193112, 686049, 2459942, 8881931, 32292148, 118038070, 433790834, 1601042055, 5934546466, 22074679425, 82399006636, 308471888767, 1158175006638, 4359154749776, 16447468190380, 62188658733901

Offset: 0

Alois P. Heinz, Jul 20 2017

nonn

The X-ray of a matrix is defined as the sequence of antidiagonal sums.
A unique X-ray allows reconstruction of the binary matrix.
The number of unique X-rays of all n X n binary matrices is A081294(n).
The number of all X-rays of n X n binary matrices is A010790(n).

			a(3) = 5: 00301, 02020, 10021, 10300, 12001.
a(4) = 14: 0004301, 0030320, 0034001, 0200321, 0204020, 0230021, 0230300, 1004021, 1004300, 1030301, 1034000, 1200320, 1204001, 1230020.

Alois P. Heinz, Table of n, a(n) for n = 0..750
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

Cf. A010790, A081294, A290133, A290058.

b:= proc(n, i, t) option remember; (m-> `if`(n>m, 0, `if`(n=m, 1,
      b(n, i-t, 1-t)+`if`(i>n, 0, b(n-i, i-t, 1-t)))))(i*(i+1-t))
    end:
a:= n-> b(iquo(n^2, 2), n, 1):
seq(a(n), n=0..40);

b[n_, i_, t_] := b[n, i, t] = Function[m, If[n > m, 0, If[n == m, 1, b[n, i-t, 1-t] + If[i > n, 0, b[n - i, i - t, 1 - t]]]]][i*(i + 1 - t)];
a[n_] := b[Quotient[n^2, 2], n, 1];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)

a(n) ~ sqrt(3) * 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jul 22 2017

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula