A144500 -id:A144500 - 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

A144495 Row 2 of array in A144502.

Original entry on oeis.org

2, 7, 30, 155, 946, 6687, 53822, 486355, 4877250, 53759351, 646098622, 8409146187, 117836551730, 1768850337295, 28318532194206, 481652022466307, 8673291031865602, 164849403644999655, 3297954931572397790, 69274457019123638011, 1524368720086682440242

Offset: 0

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

nonn

Robert Israel, Table of n, a(n) for n = 0..447

Cf. A000522, A001339, A038720, A144496, A144497, A144498.

Cf. A144499, A144500, A144501, A144502, A144503.

A144495:= func< n | (&+[Binomial(n,k)*(k+4)*Factorial(k+1) : k in [0..n]])/2 >;
[A144495(n): n in [0..40]]; // G. C. Greubel, Oct 07 2023

f:= rectoproc({a(n)=((4+3*n)*a(n-1)-(n+3)*(n-1)*a(n-2)+(n-1)*(n-2)*a(n-3))/2,a(0)=2,a(1)=7,a(2)=30},a(n),remember):
map(f, [$0..40]); # Robert Israel, Oct 02 2016

(* First program *)
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];
a[n_] := t[2, n];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Aug 19 2022 *)
(* Second program *)
a[n_]:= a[n]= If[n==0, 2, (n*(n^2+3*n+1)*a[n-1] -(n+2))/(n^2+n-1)];
Table[a[n], {n,0,40}] (* G. C. Greubel, Oct 07 2023 *)

def A144495(n): return sum(binomial(n,j)*factorial(j+1)*(j+4) for j in range(n+1))/2
[A144495(n) for n in range(41)] # G. C. Greubel, Oct 07 2023

E.g.f.: exp(x)*(2-x)/(1-x)^3.
a(n) = (1/2) * (floor((n+1)*(n+1)!*e) + floor(n*n!*e)). [Gary Detlefs, Jun 06 2010]
a(n) = (1/2) * ( A001339(n) + A001339(n+1) ). [Gary Detlefs, Jun 06 2010]
a(n) = (1/2) * (3 + n + (1 + 3*n + n^2) * A000522(n)). - Gerry Martens, Oct 02 2016
a(n) = ((4+3*n)*a(n-1) - (n+3)*(n-1)*a(n-2) + (n-1)*(n-2)*a(n-3))/2. - Robert Israel, Oct 02 2016
From Peter Bala, May 27 2022: (Start)
a(n) = (1/2)*(A000522(n+2) - A000522(n)).
a(n) = (1/2)*Sum_{k = 0..n} binomial(n,k)*(k+4)*(k+1)!; binomial transform of A038720(n+1).
a(n) = (1/2)*e*Integral_{x >= 1} x^n*(x^2 - 1)*exp(-x).
a(2*n) is even and a(2*n+1) is odd. More generally, a(n+k) == a(n) (mod k) for all n and k. It follows that for each positive integer k, the sequence obtained by reducing a(n) modulo k is periodic, with the exact period dividing k. Various divisibility properties of the sequence follow from this; for example, a(3*n+2) == 0 (mod 3), a(5*n+2) == a(5*n+3) (mod 5), a(7*n+1) == 0 (mod 7) and a(11*n+4) == 0 (mod 11). (End)
a(n) = (n*(n^2 + 3*n + 1)*a(n-1) - (n + 2))/(n^2 + n - 1), with a(0) = 2. - G. C. Greubel, Oct 07 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

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

A144495 Row 2 of array in A144502.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

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