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.

1, 1, 1, 2, 2, 1, 7, 7, 5, 1, 37, 37, 30, 16, 1, 266, 266, 229, 155, 65, 1, 2431, 2431, 2165, 1633, 946, 326, 1, 27007, 27007, 24576, 19714, 13219, 6687, 1957, 1, 353522, 353522, 326515, 272501, 198773, 119917, 53822, 13700, 1, 5329837, 5329837, 4976315, 4269271, 3289726, 2199722, 1205857, 486355, 109601, 1

Offset

0,4

Links

G. C. Greubel, Antidiagonals n = 0..50, flattened

Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, Analysis of the Gift Exchange Problem, arXiv:1701.08394 [math.CO], 2017.

David Applegate and N. J. A. Sloane, The Gift Exchange Problem, arXiv:0907.0513 [math.CO], 2009.

Formula

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

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

Example

The array, A(n,k), begins:
    1,    1,     1,      1,       1,        1, ...
    1,    2,     5,     16,      65,      326, ...
    2,    7,    30,    155,     946,     6687, ...
    7,   37,   229,   1633,   13219,   119917, ...
   37,  266,  2165,  19714,  198773,  2199722, ...
  266, 2431, 24576, 272501, 3289726, 42965211, ...
  ...
Antidiagonal triangle, T(n,k), begins as:
      1;
      1,     1;
      2,     2,     1;
      7,     7,     5,     1;
     37,    37,    30,    16,     1;
    266,   266,   229,   155,    65,    1;
   2431,  2431,  2165,  1633,   946,  326,    1;
  27007, 27007, 24576, 19714, 13219, 6687, 1957,   1;

Maple

B:=proc(p, r) option remember;
if p=0 then RETURN(1); fi;
if r=0 then RETURN(B(p-1, 1)); fi;
B(p-1, r+1)+r*B(p, r-1); end;
seq(seq(B(d-k, k), k=0..d), d=0..9);

Mathematica

t[0, _]= 1; t[n_, 0]:= t[n, 0]= t[n-1, 1];
t[n_, k_]:= t[n, k]= t[n-1, k+1] + k*t[n, k-1];
Table[t[n-k, k], {n, 0, 12}, {k, 0, n}]//Flatten (* Jean-François Alcover, Jan 14 2014, after Maple *)

Prog

(Magma)
A144301:= func< n | (&+[ Binomial(n+k-1, 2*k)*Factorial(2*k)/( Factorial(k)*2^k): k in [0..n]]) >;
function A(n, k)
  if n eq 0 then return 1;
  elif k eq 0 then return A144301(n);
  elif k eq 1 then return A144301(n+1);
  else return A(n-1, k+1) + k*A(n, k-1);
  end if;
end function;
A144502:= func< n, k | A(n-k, k) >;
[A144502(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Sep 29 2023
(SageMath)
def A144301(n): return 1 if n<2 else (2*n-3)*A144301(n-1)+A144301(n-2)
@CachedFunction
def A(n, k):
    if n==0: return 1
    elif k==0: return A144301(n)
    elif k==1: return A144301(n+1)
    else: return A(n-1, k+1) + k*A(n, k-1)
def A144502(n, k): return A(n-k, k)
flatten([[A144502(n, k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Sep 29 2023

Crossrefs

Rows include A000522, A144495, A144496, A144497.

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

Main diagonal is A144501.

Antidiagonal sums give A144503.

Sequence in context: A248924 A307455 A136502 * A246945 A360377 A100632

Adjacent sequences: A144499 A144500 A144501 * A144503 A144504 A144505

Keyword

nonn,tabl

Author

David Applegate and N. J. A. Sloane, Dec 13 2008

Extensions

6 more terms from Michel Marcus, Feb 01 2023

Status

approved