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

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, 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, 2, 3, 5, 5, 5, 4, 3, 2, 1, 1, 1, 2, 3, 4, 5, 7, 6, 5, 4, 3, 2, 1, 1

Offset: 0

Author

Antti Karttunen, Jul 03 2013

Keywords

• nonn
• tabl

Comments

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.

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.

Examples

			The top left corner of the array begins
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, ...
1, 1, 2, 2, 4, 3, 2, 3, 4, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, ...
1, 1, 2, 3, 3, 5, 4, 4, 3, 4, 5, 4, 3, 4, 4, 5, 3, 4, 4, 4, 3, 4, ...
1, 1, 2, 3, 4, 4, 6, 5, 5, 5, 4, 5, 6, 5, 5, 4, 5, 5, 6, 5, 4, 5, ...
...
For row 3, the recurrence manifests itself as:
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.
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.
		

References

• Martin Gardner, Colossal Book of Mathematics, Chapter 34, Bulgarian Solitaire and Other Seemingly Endless Tasks, pp. 455-467, W. W. Norton & Company, 2001.

Links

• Antti Karttunen, The first 99 antidiagonals of the table, flattened
• Ethan Akin and Morton Davis, "Bulgarian solitaire", American Mathematical Monthly 92 (4): 237-250. (1985).

Crossrefs

Cf. A227147.

Formula

The recurrence for the r-th row of the table (after the first row, which contains a constant sequence A000012) is defined as follows:

a_r(0) = 1; a_r(0=2r), a_r(n) = the least natural number k such that a_r(n-k-1) < k+1.

See also the given Scheme program.