A293653 Young urn sequence (number of possible evolutions in n steps of the "Young" Pólya urn).

1, 2, 6, 30, 180, 1440, 12960, 142560, 1710720, 23950080, 359251200, 6107270400, 109930867200, 2198617344000, 46170964224000, 1061932177152000, 25486372251648000, 662645678542848000, 17891433320656896000, 518851566299049984000, 15565546988971499520000, 498097503647087984640000

Offset: 0

Author

Cyril Banderier, Feb 06 2018

Keywords

• nonn

Examples

			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.
		

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.

Crossrefs

Cf. A123144.

Programs

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

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 *)

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