login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A227451 Number whose binary expansion encodes via runlengths the partition that is at the top of the main trunk of Bulgarian solitaire game tree drawn for the deck with n(n+1)/2 cards. 5
0, 1, 5, 18, 77, 306, 1229, 4914, 19661, 78642, 314573, 1258290, 5033165, 20132658, 80530637, 322122546, 1288490189, 5153960754, 20615843021, 82463372082, 329853488333, 1319413953330, 5277655813325, 21110623253298, 84442493013197, 337769972052786, 1351079888211149 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

The terms have particular patterns in their binary expansion, which encodes for an "almost triangular partition" when runlength encoding of unordered partitions are used (please see A129594 for how that encoding works). These are obtained from the perfectly triangular partitions shown in A037481 by inserting 1 to the front of the partition and decrementing the last summand (the largest) by one:

  n   a(n)    same in binary           run lengths   unordered partition

  0      0                 0                    []                    {}

  1      1                 1                   [1]                   {1}

  2      5               101               [1,1,1]               {1+1+1}

  3     18             10010             [1,2,1,1]             {1+1+2+2}

  4     77           1001101           [1,2,2,1,1]           {1+1+2+3+3}

  5    306         100110010         [1,2,2,2,1,1]         {1+1+2+3+4+4}

  6   1229       10011001101       [1,2,2,2,2,1,1]       {1+1+2+3+4+5+5}

  7   4914     1001100110010     [1,2,2,2,2,2,1,1]     {1+1+2+3+4+5+6+6}

  8  19661   100110011001101   [1,2,2,2,2,2,2,1,1]   {1+1+2+3+4+5+6+7+7}

  9  78642 10011001100110010 [1,2,2,2,2,2,2,2,1,1] {1+1+2+3+4+5+6+7+8+8}

These partitions occur at the tops of the main trunks of the game trees constructed for decks consisting of 1+2+3+...+k cards. See A037481 for the encoding of the roots of the main trunks of the same trees.

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, Table of n, a(n) for n = 0..1000

Wikipedia, Bulgarian solitaire

Index entries for linear recurrences with constant coefficients, signature (4,1,-4).

FORMULA

a(0)=0, a(1)=1, for n>=2, a(n) = A053645(2*A037481(n)) + (1 - (n mod 2)). [Follows from the "insert 1 and decrement the largest part by one" operation on triangular partitions]

Alternatively:

a(0)=0, a(1)=1, and for n>=2, if n is even, then a(n) = 1 + (4*A182512((n-2)/2)) + 2^(2*(n-1)), and if n is odd, then a(n) = 2 + (16*A182512((n-3)/2)) + 2^(2*(n-1)).

From Ralf Stephan, Jul 20 2013: (Start)

a(n) = (1/10) * (3*4^n + 7*(-1)^n - 5).

a(n) = 4*a(n-1) + a(n-2) - 4*a(n-3), n>3.

G.f.: (4*x^4 - 3*x^3 + x^2 + x)/((1-x)*(1+x)/(1-4*x). (End)

MATHEMATICA

LinearRecurrence[{4, 1, -4}, {0, 1, 5, 18, 77}, 40] (* Harvey P. Dale, Sep 22 2016 *)

PROG

(Scheme, two variants)

(define (A227451 n) (if (< n 2) n (+ (A053645 (* 2 (A037481 n))) (- 1 (modulo n 2)))))

(define (A227451v2 n) (cond ((< n 2) n) ((even? n) (+ 1 (* 4 (+ (A182512 (/ (- n 2) 2)))) (expt 2 (* 2 (- n 1))))) (else (+ 2 (* 16 (A182512 (/ (- n 3) 2))) (expt 2 (* 2 (- n 1)))))))

(PARI) a(n)=if(n<1, 0, if(n==1, 1, (3*4^n+7*(-1)^n-5)/10)) \\ Ralf Stephan

CROSSREFS

Cf. A037481, A182512.

The left edge of the table A227452.

Sequence in context: A296123 A242054 A027134 * A017960 A162814 A082034

Adjacent sequences:  A227448 A227449 A227450 * A227452 A227453 A227454

KEYWORD

nonn,base,easy

AUTHOR

Antti Karttunen, Jul 12 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 14 07:59 EDT 2021. Contains 342946 sequences. (Running on oeis4.)