A144502 - OEIS

A144502

Square array read by antidiagonals upwards: T(n,k) is the number of scenarios for the gift exchange problem in which each gift can be stolen at most once, when there are n gifts in the pool and k gifts (not yet frozen) in peoples' hands.

%I #42 Oct 08 2023 09:04:36

%S 1,1,1,2,2,1,7,7,5,1,37,37,30,16,1,266,266,229,155,65,1,2431,2431,

%T 2165,1633,946,326,1,27007,27007,24576,19714,13219,6687,1957,1,353522,

%U 353522,326515,272501,198773,119917,53822,13700,1,5329837,5329837,4976315,4269271,3289726,2199722,1205857,486355,109601,1

%N Square array read by antidiagonals upwards: T(n,k) is the number of scenarios for the gift exchange problem in which each gift can be stolen at most once, when there are n gifts in the pool and k gifts (not yet frozen) in peoples' hands.

%H G. C. Greubel, <a href="/A144502/b144502.txt">Antidiagonals n = 0..50, flattened</a>

%H Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1701.08394">Analysis of the Gift Exchange Problem</a>, arXiv:1701.08394 [math.CO], 2017.

%H David Applegate and N. J. A. Sloane, <a href="http://arxiv.org/abs/0907.0513">The Gift Exchange Problem</a>, arXiv:0907.0513 [math.CO], 2009.

%F Let A_n(x) be the e.g.f. for row n. Then A_0(x) = exp(x) and for n >= 1, A_n(x) = (d/dx)A_{n-1}(x)/(1-x).

%F For n >= 1, the rows A_{n}(x) = P_{n}(x)*exp(x)/(1-x)^(2*n), where P_{n}(x) = (1-x)*(d/dx)( P_{n-1}(x) ) + (2*n-x)*P_{n-1}(x) and P_{0}(x) = 1. - _G. C. Greubel_, Oct 08 2023

%e The array, A(n,k), begins:

%e 1, 1, 1, 1, 1, 1, ...

%e 1, 2, 5, 16, 65, 326, ...

%e 2, 7, 30, 155, 946, 6687, ...

%e 7, 37, 229, 1633, 13219, 119917, ...

%e 37, 266, 2165, 19714, 198773, 2199722, ...

%e 266, 2431, 24576, 272501, 3289726, 42965211, ...

%e ...

%e Antidiagonal triangle, T(n,k), begins as:

%e 1;

%e 1, 1;

%e 2, 2, 1;

%e 7, 7, 5, 1;

%e 37, 37, 30, 16, 1;

%e 266, 266, 229, 155, 65, 1;

%e 2431, 2431, 2165, 1633, 946, 326, 1;

%e 27007, 27007, 24576, 19714, 13219, 6687, 1957, 1;

%p B:=proc(p,r) option remember;

%p if p=0 then RETURN(1); fi;

%p if r=0 then RETURN(B(p-1,1)); fi;

%p B(p-1,r+1)+r*B(p,r-1); end;

%p seq(seq(B(d-k, k), k=0..d), d=0..9);

%t t[0, _]= 1; t[n_, 0]:= t[n, 0]= t[n-1, 1];

%t t[n_, k_]:= t[n, k]= t[n-1, k+1] + k*t[n, k-1];

%t Table[t[n-k, k], {n,0,12}, {k,0,n}]//Flatten (* _Jean-François Alcover_, Jan 14 2014, after Maple *)

%o (Magma)

%o A144301:= func< n | (&+[ Binomial(n+k-1,2*k)*Factorial(2*k)/( Factorial(k)*2^k): k in [0..n]]) >;

%o function A(n,k)

%o if n eq 0 then return 1;

%o elif k eq 0 then return A144301(n);

%o elif k eq 1 then return A144301(n+1);

%o else return A(n-1,k+1) + k*A(n,k-1);

%o end if;

%o end function;

%o A144502:= func< n,k | A(n-k, k) >;

%o [A144502(n,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, Sep 29 2023

%o (SageMath)

%o def A144301(n): return 1 if n<2 else (2*n-3)*A144301(n-1)+A144301(n-2)

%o @CachedFunction

%o def A(n,k):

%o if n==0: return 1

%o elif k==0: return A144301(n)

%o elif k==1: return A144301(n+1)

%o else: return A(n-1,k+1) + k*A(n,k-1)

%o def A144502(n,k): return A(n-k,k)

%o flatten([[A144502(n,k) for k in range(n+1)] for n in range(13)]) # _G. C. Greubel_, Sep 29 2023

%Y Rows include A000522, A144495, A144496, A144497.

%Y Columns include A144301, A001515, A144498, A144499, A144500.

%Y Main diagonal is A144501.

%Y Antidiagonal sums give A144503.

%K nonn,tabl

%O 0,4

%A _David Applegate_ and _N. J. A. Sloane_, Dec 13 2008

%E 6 more terms from _Michel Marcus_, Feb 01 2023