login
Square array a(n,k) read by antidiagonals: a(n,1)=n, a(1,k)=k, a(n,k)=a(n-1,k-1)+a(n-1,k)+a(n,k-1)+1.
8

%I #36 May 10 2021 10:18:57

%S 1,2,2,3,6,3,4,12,12,4,5,20,31,20,5,6,30,64,64,30,6,7,42,115,160,115,

%T 42,7,8,56,188,340,340,188,56,8,9,72,287,644,841,644,287,72,9,10,90,

%U 416,1120,1826,1826,1120,416,90,10,11,110,579,1824,3591

%N Square array a(n,k) read by antidiagonals: a(n,1)=n, a(1,k)=k, a(n,k)=a(n-1,k-1)+a(n-1,k)+a(n,k-1)+1.

%H Vincenzo Librandi, <a href="/A047662/b047662.txt">Rows n = 1..100, flattened</a>

%H M. L. Fredman, <a href="https://doi.org/10.1145/322290.322305">The complexity of maintaining an array and its partial sums</a>, J. Assoc. Comp. Machin., 29 (1982), 250-260.

%H D. E. Knuth and N. J. A. Sloane, <a href="/A047662/a047662.pdf">Correspondence, December 1999</a>

%H Matthew Roughan, <a href="https://arxiv.org/abs/1810.10373">Surreal Birthdays and Their Arithmetic</a>, arXiv:1810.10373 [math.HO], 2018.

%F a(n, k) =(A008288(n, k)-1)/2. Sum of antidiagonals is A048776.

%e The array begins:

%e 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...

%e 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, ...

%e 3, 12, 31, 64, 115, 188, 287, 416, 579, 780, 1023, 1312, ...

%e 4, 20, 64, 160, 340, 644, 1120, 1824, 2820, 4180, 5984, 8320, ...

%e 5, 30, 115, 340, 841, 1826, 3591, 6536, 11181, 18182, 28347, 42652, ...

%e 6, 42, 188, 644, 1826, 4494, 9912, 20040, 37758, 67122, 113652, 184652, ...

%e 7, 56, 287, 1120, 3591, 9912, 24319, 54272, 112071, 216952, 397727, 696032, ...

%e 8, 72, 416, 1824, 6536, 20040, 54272, 132864, 299208, 628232, 1242912, 2336672, ...

%e ...

%e The first few antidiagonals are:

%e 1,

%e 2, 2,

%e 3, 6, 3,

%e 4, 12, 12, 4,

%e 5, 20, 31, 20, 5,

%e 6, 30, 64, 64, 30, 6,

%e 7, 42, 115, 160, 115, 42, 7,

%e 8, 56, 188, 340, 340, 188, 56, 8,

%e 9, 72, 287, 644, 841, 644, 287, 72, 9,

%e 10, 90, 416, 1120, 1826, 1826, 1120, 416, 90, 10,

%e ...

%p A047662 := proc(n,k) option remember; if n = 1 then k; elif k = 1 then n; else A047662(n-1,k-1)+A047662(n,k-1)+A047662(n-1,k)+1; fi; end;

%t a[n_, 1] := n; a[1, k_] := k; a[n_, k_] := a[n, k] = a[n-1, k-1] + a[n-1, k] + a[n, k-1] + 1; Table[ a[n-k+1, k], {n, 1, 11}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Aug 13 2013 *)

%Y Rows give A037237, 4*A006007, A047661, A047663, A047664, main diagonal is A047665 (see also A001850).

%Y See also A008288, A048776.

%K nonn,tabl,nice,easy

%O 1,2

%A _Don Knuth_, _N. J. A. Sloane_