A144495 -id:A144495 - cp's OEIS frontend

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

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

			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;

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.

Rows include A000522, A144495, A144496, A144497.
Columns include A144301, A001515, A144498, A144499, A144500.
Main diagonal is A144501.
Antidiagonal sums give A144503.

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

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

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

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

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

6 more terms from Michel Marcus, Feb 01 2023

A144496 Row 3 of array in A144502.

Original entry on oeis.org

7, 37, 229, 1633, 13219, 119917, 1205857, 13318249, 160305343, 2088846709, 29297613277, 440110297777, 7050173910619, 119970793032253, 2161243124917849, 41091937905633337, 822320410135133047, 17277401903869659589, 380267691288777510613, 8749454854573455141889

Offset: 0

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

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A144495, A144497, A144498, A144499, A144500, A144501, A144502, A144503.

R:=PowerSeriesRing(Rationals(), 40); Coefficients(R!(Laplace( (7-5*x+x^2)*Exp(x)/(1-x)^5 ))); // G. C. Greubel, Oct 07 2023

CoefficientList[Series[E^x*(7-5*x+x^2)/(1-x)^5, {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Oct 08 2013 *)

def a(n): # a = A144496
    if (n==0): return 7
    else: return (n*(n^4+10*n^3+33*n^2+44*n+21)*a(n-1) + n^2+6*n+7)/(n^4+6*n^3+9*n^2+4*n+1)
[a(n) for n in range(41)] # G. C. Greubel, Oct 07 2023

E.g.f.: (7-5*x+x^2)*exp(x)/(1-x)^5.
a(n) ~ n! * n^4 * exp(1)/8. - Vaclav Kotesovec, Oct 08 2013
a(n) = (n*(n^4 + 10*n^3 + 33*n^2 + 44*n + 21)*a(n-1) + n^2 + 6*n +
   7)/(n^4 + 6*n^3 + 9*n^2 + 4*n + 1), with a(0) = 7. - G. C. Greubel, Oct 07 2023

A144497 Row 4 of array in A144502.

Original entry on oeis.org

37, 266, 2165, 19714, 198773, 2199722, 26516581, 345921410, 4856217989, 73003575178, 1170146049557, 19921780455746, 359032158501205, 6828661185433514, 136693194501702533, 2872718327660671042, 63240895146440396261, 1455362908778264247050, 34945987212582211588789

Offset: 0

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

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..444

Cf. A144495, A144496, A144498, A144499, A144500, A144501, A144502, A144503.

R:=PowerSeriesRing(Rationals(), 40); Coefficients(R!(Laplace( (37-30*x+9*x^2-x^3)*Exp(x)/(1-x)^7 ))); // G. C. Greubel, Oct 08 2023

a[n_]:= If[n<1, 37, (n*(n^6+21*n^5+172*n^4+705*n^3+1522*n^2+1623*n +653)*a[n-1] -(n^3+12*n^2+41*n+37))/(n^6+15*n^5+82*n^4+207*n^3 +244*n^2+105*n-1)];
Table[a[n], {n,0,40}] (* G. C. Greubel, Oct 08 2023 *)

my(x='x+O('x^25)); Vec(serlaplace(exp(x)*(37-30*x+9*x^2-x^3)/(1-x)^7)) \\ Michel Marcus, Apr 06 2019

def A144497_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( (37-30*x+9*x^2-x^3)*exp(x)/(1-x)^7 ).egf_to_ogf().list()
A144497_list(40) # G. C. Greubel, Oct 08 2023

E.g.f.: exp(x)*(37-30*x+9*x^2-x^3)/(1-x)^7.

a(n) = (n*(n^6 + 21*n^5 + 172*n^4 + 705*n^3 + 1522*n^2 + 1623*n + 653)*a(n-1) - (n^3 + 12*n^2 + 41*n + 37))/(n^6 + 15*n^5 + 82*n^4 + 207*n^3 + 244*n^2 + 105*n - 1), with a(0) = 37. - G. C. Greubel, Oct 08 2023

A144500 Column 4 of array in A144502.

Original entry on oeis.org

1, 65, 946, 13219, 198773, 3289726, 60042295, 1203809111, 26367604594, 627370195033, 16127774194871, 445733080387750, 13185075339881521, 415765494276887249, 13925084982848794378, 493754789222478044011, 18480155500259244528605, 728143711886491334229526

Offset: 0

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

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..401

Cf. A144495, A144496, A144497, A144498, A144499, A144501, A144502, A144503.

[n le 2 select (65)^(n-1) else ((24*n^3-12*n^2+2*n-9)*Self(n-1) + (12*n^2-11)*Self(n-2))/(12*(n-1)^2 -11): n in [1..40]]; // G. C. Greubel, Oct 08 2023

a[n_]:= a[n]= If[n<2, (65)^n, ((24*n^3+60*n^2+50*n+5)*a[n-1] +(12*n^2 + 24*n+1)*a[n-2])/(12*n^2-11)];
Table[a[n], {n,0,40}] (* G. C. Greubel, Oct 08 2023 *)

@CachedFunction
def a(n): # a = A144500
    if (n<2): return (65)^n
    else: return ((24*n^3 + 60*n^2 + 50*n + 5)*a(n-1) + (12*n^2 + 24*n + 1)*a(n-2))/(12*n^2 - 11)
[a(n) for n in range(41)] # G. C. Greubel, Oct 08 2023

a(n) = ((24*n^3 + 60*n^2 + 50*n + 5)*a(n-1) + (12*n^2 + 24*n + 1)*a(n-2))/(12*n^2 - 11), with a(0) = 1, a(1) = 65. - G. C. Greubel, Oct 08 2023

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A144496 Row 3 of array in A144502.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A144497 Row 4 of array in A144502.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A144500 Column 4 of array in A144502.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula