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

%I #29 Mar 31 2018 16:58:46

%S 1,1,2,5,14,42,130,415,1368,4603,15788,54863,193112,686049,2459942,

%T 8881931,32292148,118038070,433790834,1601042055,5934546466,

%U 22074679425,82399006636,308471888767,1158175006638,4359154749776,16447468190380,62188658733901

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

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

%C A unique X-ray allows reconstruction of the binary matrix.

%C The number of unique X-rays of all n X n binary matrices is A081294(n).

%C The number of all X-rays of n X n binary matrices is A010790(n).

%H Alois P. Heinz, <a href="/A290134/b290134.txt">Table of n, a(n) for n = 0..750</a>

%H C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, <a href="https://arxiv.org/abs/math/0506334">On the X-rays of permutations</a>, arXiv:math/0506334 [math.CO], 2005.

%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>

%F a(n) ~ sqrt(3) * 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Jul 22 2017

%e a(3) = 5: 00301, 02020, 10021, 10300, 12001.

%e a(4) = 14: 0004301, 0030320, 0034001, 0200321, 0204020, 0230021, 0230300, 1004021, 1004300, 1030301, 1034000, 1200320, 1204001, 1230020.

%p b:= proc(n, i, t) option remember; (m-> `if`(n>m, 0, `if`(n=m, 1,

%p b(n, i-t, 1-t)+`if`(i>n, 0, b(n-i, i-t, 1-t)))))(i*(i+1-t))

%p end:

%p a:= n-> b(iquo(n^2, 2), n, 1):

%p seq(a(n), n=0..40);

%t 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)];

%t a[n_] := b[Quotient[n^2, 2], n, 1];

%t Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Nov 06 2017, after _Alois P. Heinz_ *)

%Y Cf. A010790, A081294, A290133, A290058.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Jul 20 2017