A334014 Array read by antidiagonals: T(n,k) is the number of functions f: X->Y, where X is a subset of Y, |X| = n, |Y| = n+k, such that for every x in X, f(f(x)) != x.

1, 1, 0, 1, 1, 0, 1, 2, 3, 2, 1, 3, 8, 18, 30, 1, 4, 15, 52, 163, 444, 1, 5, 24, 110, 478, 1950, 7360, 1, 6, 35, 198, 1083, 5706, 28821, 138690, 1, 7, 48, 322, 2110, 13482, 83824, 505876, 2954364, 1, 8, 63, 488, 3715, 27768, 203569, 1461944, 10270569, 70469000, 1, 9, 80, 702, 6078, 51894, 436656, 3618540, 29510268, 236644092, 1864204416, 1, 10, 99, 970, 9403, 90150, 854485, 8003950, 74058105, 676549450, 6098971555, 54224221050

Offset

0,8

Comments

Comes up in the study of the Zen Stare game (see description at A134362).

T(k,n-k)*binomial(n,k)*(n-k-1)!! is the number of different possible Zen Stare rounds with n starting players and k winners.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325

Formula

T(n,k) = Sum_{i=0..n} k^(n-i)*binomial(n,i)*T(i,n-i); This means that with a constant n, T(n,k) is a polynomial of k.

T(n,0) = A134362(n).

T(0,k) = 1.

For odd n, Sum_{k=1..(n+1)/2} T(2*k-1,n-2*k+1)*binomial(n,2*k-1)*(n-2*k)!! = (n-1)^n.

E.g.f. of k-th column: exp((k-1)*W(x) - W(x)^2/2)/(1-W(x)) where W(x) is the e.g.f. of A000169. - Andrew Howroyd, Apr 15 2020

Example

Array begins:
=======================================================
n\k |    0     1     2      3      4      5       6
----+--------------------------------------------------
  0 |    1     1     1      1      1      1       1 ...
  1 |    0     1     2      3      4      5       6 ...
  2 |    0     3     8     15     24     35      48 ...
  3 |    2    18    52    110    198    322     488 ...
  4 |   30   163   478   1083   2110   3715    6078 ...
  5 |  444  1950  5706  13482  27768  51894   90150 ...
  6 | 7360 28821 83824 203569 436656 854485 1557376 ...
  ...
T(2,2) = 8; This because given X = {A,B}, Y = {A,B,C,D}. The only functions f: X->Y that meet the requirement are:
f(A) = C, f(B) = C
f(A) = D, f(B) = D
f(A) = D, f(B) = C
f(A) = C, f(B) = D
f(A) = B, f(B) = C
f(A) = B, f(B) = D
f(A) = C, f(B) = A
f(A) = D, f(B) = A

Prog

(PARI) T(n, k)={my(w=-lambertw(-x + O(x^max(4, 1+n)))); n!*polcoef(exp((k-1)*w - w^2/2)/(1-w), n)} \\ Andrew Howroyd, Apr 15 2020

Crossrefs

Rows n=0..3 are A000012, A001477, A005563, A058794.

Columns k=0..4 are A134362, A089466, A089467, A089468, A220690(n+2).

Cf. A000169, A065440.

Sequence in context: A303868 A060475 A168069 * A280929 A231725 A106559

Adjacent sequences: A334011 A334012 A334013 * A334015 A334016 A334017

Keyword

nonn,tabl

Author

Mason C. Hart, Apr 14 2020

Status

approved