OFFSET
0,2
LINKS
Robert G. Wilson v, Table of n, a(n) for n = 0..422
Cyril Banderier, Philippe Marchal, and Michael Wallner, Periodic Pólya urns and an application to Young tableaux, Leibniz International Proceedings in Informatics (LIPIcs), 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), 1-12, also arXiv:1806.03133 [cs.DM], 2018.
Cyril Banderier, Philippe Marchal, Michael Wallner, Periodic Pólya Urns, the Density Method, and Asymptotics of Young Tableaux, arXiv:1912.01035 [math.PR], 2019.
FORMULA
a(n+2) = (3/2)*a(n+1) + (9*n^2+21*n+12)/4*a(n), a(0) = 1, a(1) = 2.
Also, a(2n+k) has a hypergeometric expression (for k=0,1, see Maple code below) (proved).
EXAMPLE
We based the following explanations on Figure 1 from the Banderier et al. reference:
We have an urn with black and white balls in it.
At odd-numbered steps, we apply rule M1: we choose a ball, check its color, and add to the urn a ball of the same color.
At even-numbered steps, we apply rule M2: we choose a ball and check its color;
if it is black, we add 1 white ball and 1 black ball;
if it is white, we add 2 white balls.
At step 0, we start with the urn containing 1 black ball and 1 white ball (in short, 1b/1w). Accordingly, a(0)=1.
At step 1, we apply rule M1. This leads to 2 compositions: 2b/1w and 1b/2w. Accordingly, a(1) = 1 + 1 = 2.
At step 2, we apply rule M2. This leads to 3 compositions: 3b/2w, 2b/3w, and 1b/4w, each having multiplicity two. Accordingly, a(2) = 2 + 2 + 2 = 6. This leads to 4 compositions at step 3: 4b/2w (with multiplicity 6), and 3b/3w, 2b/4w, and 1b/5w (each of these last three with multiplicity 8). Accordingly, a(3) = 6 + 8 + 8 + 8 = 30.
MAPLE
a:=proc(n) if n mod 2= 0 then 3^n /GAMMA(2/3) * GAMMA(n/2+2/3) * GAMMA(n/2+1);
else 3^n /GAMMA(2/3) * GAMMA(n/2+7/6) * GAMMA(n/2+1/2); fi; end:
seq(a(n), n=0..30);
MATHEMATICA
f[n_] := FullSimplify[ 3^n/Gamma[2/3]*If[OddQ@ n, Gamma[n/2 + 7/6] Gamma[n/2 + 1/2], Gamma[n/2 + 2/3]Gamma[n/2 + 1]]]; Array[f, 20, 0] (* Robert G. Wilson v, Feb 07 2018 *)
PROG
(GAP) a:=[1, 2];; for n in [3..25] do a[n]:=(3/2)*a[n-1]+(9*(n-3)^2+21*n-51)/4*a[n-2]; od; a; # Muniru A Asiru, Dec 19 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Cyril Banderier, Feb 06 2018
STATUS
approved