|
%I #24 Apr 02 2017 00:50:06
%S 1,1,1,1,1,1,1,1,1,1,1,3,2,1,1,1,1,2,2,1,1,1,2,4,3,2,1,1,1,1,3,3,3,2,
%T 1,1,1,2,2,5,4,3,2,1,1,1,1,3,4,4,4,3,2,1,1,1,2,4,4,6,5,4,3,2,1,1,1,1,
%U 2,3,5,5,5,4,3,2,1,1,1,2,3,4,5,7,6,5,4,3,2,1,1
%N Array A(n,k) where A(1,k)=1 for row 1, and subsequent rows A(n > 1, k) are computed by recurrences related to Bulgarian Solitaire; square array A(n,k), with row n >= 1, column k >= 0, read by antidiagonals.
%C The initial terms give the summands of the partitions (or: number of parts, when shifted once) that occur in the main trunk of Bulgarian solitaire tree computed for a pack containing 1+2+...+n cards.
%C The irregular table A227147 gives just the palindromic subsequence from each row. After that part, the recurrence on row n always leads to a sequence of period n.
%D Martin Gardner, Colossal Book of Mathematics, Chapter 34, Bulgarian Solitaire and Other Seemingly Endless Tasks, pp. 455-467, W. W. Norton & Company, 2001.
%H Antti Karttunen, <a href="/A227141/b227141.txt">The first 99 antidiagonals of the table, flattened</a>
%H Ethan Akin and Morton Davis, <a href="http://www.jstor.org/stable/2323643">"Bulgarian solitaire"</a>, American Mathematical Monthly 92 (4): 237-250. (1985).
%F The recurrence for the r-th row of the table (after the first row, which contains a constant sequence A000012) is defined as follows:
%F a_r(0) = 1; a_r(0<n<r) = n, a_r(n=r) = r-1, a_r(n=(r+1)) = n, a_r(n<2r) = r, and otherwise (for values n>=2r), a_r(n) = the least natural number k such that a_r(n-k-1) < k+1.
%F See also the given Scheme program.
%e The top left corner of the array begins
%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, ...
%e 1, 1, 2, 2, 4, 3, 2, 3, 4, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, ...
%e 1, 1, 2, 3, 3, 5, 4, 4, 3, 4, 5, 4, 3, 4, 4, 5, 3, 4, 4, 4, 3, 4, ...
%e 1, 1, 2, 3, 4, 4, 6, 5, 5, 5, 4, 5, 6, 5, 5, 4, 5, 5, 6, 5, 4, 5, ...
%e ...
%e For row 3, the recurrence manifests itself as:
%e a_3(0) = 1; a_3(0<n<3) = n (i.e., a_3(1)=1, a_3(2)=2), a_3(3) = 2, a_3(4) = 4, a_3(4<n<6) (that is, a_3(5)) = 3, and after that, for values n>=6, a_3(n) = the least natural number k such that a_3(n-k-1) < k+1.
%e As a_3(6-0-1) = a_3(5) = 3 is not less than 1, nor a_3(6-1-1) = a_3(4) = 2 is not less than 2, but a_3(6-2-1) = a_3(3) = 2 IS less than 3 (2+1), the sought value of k is 2, and a_3(6)=2.
%o (Scheme, with _Antti Karttunen_'s IntSeq-library, using memoizing macros definec and implement-cached-function):
%o (define (A227141 n) (A227141bi (+ 1 (A002262 n)) (A025581 n)))
%o (define (A227141bi row col) ((rowfun-for-A227141 row) col))
%o (definec (rowfun-for-A227141 n) (if (< n 2) (lambda (k) n) (implement-cached-function 0 (rowfun-n k) (cond ((zero? k) 1) ((< k n) k) ((= k n) (- n 1)) ((= k (+ n 1)) k) ((< k (* 2 n)) n) (else (let loop ((i 1)) (if (< (rowfun-n (- k i)) i) (- i 1) (loop (+ i 1)))))))))
%Y Cf. A227147.
%K nonn,tabl
%O 0,12
%A _Antti Karttunen_, Jul 03 2013
|
