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

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

Comments

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

Links

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

Formula

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

Example

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.

Maple

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

Mathematica

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

Crossrefs

Cf. A010790, A081294, A290133, A290058.

Sequence in context: A316779 A344571 A148328 * A080937 A196417 A054392

Adjacent sequences: A290131 A290132 A290133 * A290135 A290136 A290137

Keyword

nonn

Author

Alois P. Heinz, Jul 20 2017

Status

approved