login
Number of n X n 0..1 arrays with rows unimodal and columns nondecreasing.
4

%I #50 Apr 07 2024 11:24:33

%S 1,2,9,50,295,1792,11088,69498,439791,2803658,17978389,115837592,

%T 749321716,4863369656,31655226108,206549749930,1350638103791,

%U 8848643946550,58069093513635,381650672631330,2511733593767295,16550500379912640,109176697072162080

%N Number of n X n 0..1 arrays with rows unimodal and columns nondecreasing.

%C Diagonal of A225010.

%C Number of unimodal maps [1..n]->[1..n+1], see example. - _Joerg Arndt_, May 10 2013

%H G. C. Greubel and R. H. Hardin, <a href="/A225006/b225006.txt">Table of n, a(n) for n = 0..1000</a> (terms 1..51 from R. H. Hardin)

%F From _Vaclav Kotesovec_, May 22 2013: (Start)

%F Empirical: 4*n*(2*n-1)*(5*n-7)*a(n) = 2*(145*n^3 - 343*n^2 + 235*n - 48)*a(n-1) - 3*(3*n-4)*(3*n-2)*(5*n-2)*a(n-2).

%F a(n) ~ 3^(3*n+3/2)/(5*2^(2*n+1)*sqrt(Pi*n)). (End)

%F a(n) = A261668(n)+1.

%F a(n) = Sum_{d=0..n} binomial(2d+n-1,n-1). Also, a(n) is the coefficient of x^(2n) in (1+x)^(-n-1)/(1-x). - _Max Alekseyev_, Sep 14 2015

%F It appears that a(n) = Sum_{k = 0..2*n} (-1)^k*binomial(n+k,k). - _Peter Bala_, Oct 08 2021

%F From _Seiichi Manyama_, Apr 06 2024: (Start)

%F a(n) = Sum_{k=0..floor(n/2)} (-1)^k * binomial(3*n-2*k-1,n-2*k).

%F a(n) = [x^n] 1/((1+x^2) * (1-x)^(2*n)). (End)

%e Some solutions for n=3

%e ..0..1..1....0..1..0....0..0..1....0..0..0....0..0..0....0..0..0....0..0..0

%e ..1..1..1....0..1..0....1..1..1....0..0..0....0..0..0....0..1..0....0..0..1

%e ..1..1..1....0..1..1....1..1..1....0..0..1....0..1..0....1..1..1....0..1..1

%e From _Joerg Arndt_, May 10 2013: (Start)

%e The a(2) = 9 unimodal maps [1,2]->[1,2,3] are

%e 01: [ 1 1 ]

%e 02: [ 1 2 ]

%e 03: [ 1 3 ]

%e 04: [ 2 1 ]

%e 05: [ 2 2 ]

%e 06: [ 2 3 ]

%e 07: [ 3 1 ]

%e 08: [ 3 2 ]

%e 09: [ 3 3 ]

%e (End)

%t a[n_] := Sum[Binomial[2d+n-1, n-1], {d, 0, n}]; Array[a, 30] (* _Jean-François Alcover_, Feb 17 2016, after _Max Alekseyev_ *)

%o (PARI) { a(n) = polcoeff( (1+x+O(x^(2*n+1)))^(-n-1)/(1-x), 2*n) }

%Y Cf. A088536 (unimodal maps [1..n]->[1..n]).

%Y Cf. A183160, A371798.

%K nonn

%O 0,2

%A _R. H. Hardin_, Apr 23 2013

%E a(0)=1 prepended by _Alois P. Heinz_, Feb 04 2017