A055134 Triangle read by rows: T(n,k) = number of labeled endofunctions on n points with k fixed points.

1, 0, 1, 1, 2, 1, 8, 12, 6, 1, 81, 108, 54, 12, 1, 1024, 1280, 640, 160, 20, 1, 15625, 18750, 9375, 2500, 375, 30, 1, 279936, 326592, 163296, 45360, 7560, 756, 42, 1, 5764801, 6588344, 3294172, 941192, 168070, 19208, 1372, 56, 1, 134217728

Offset: 0

Author

Christian G. Bower, Apr 25 2000

Keywords

• nonn
• tabl

Comments

The same triangle (except for signs) may be obtained from the determinants of the Brahmagupta matrices, setting x->Sqrt[z], y->1, t->n. - Roger L. Bagula, Apr 09 2008

From Bob Selcoe, Nov 15 2014 (Start):

T(n,k)/A000312(n) is the probability P(n,k) that any member (j) of set J={1..n} will be selected k times given n random draws from J. This is equivalent to rolling an n-sided die (with standard assumptions) with sides numbered j=1..n: P(n,k) is the probability that any j will show k times with n rolls.

P(n,k) = (n-2)!*(n-1)^(n-k+1 )/k!*(n-k)!*n^(n-1); n>1. As n approaches infinity, P(n,0) and P(n,1) approach 1/e. (End)

Row sums give n^n (see A000312). - Bob Selcoe, Sep 08 2015

Examples

			Triangle T(n,k) begins:
       1;
       0,      1;
       1,      2,      1;
       8,     12,      6,     1;
      81,    108,     54,    12,    1;
    1024,   1280,    640,   160,   20,   1;
   15625,  18750,   9375,  2500,  375,  30,  1;
  279936, 326592, 163296, 45360, 7560, 756, 42, 1;
  ...
		

Links

• G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
• Eric W. Weisstein's World of Mathematics, Brahmagupta Matrix.

Crossrefs

Columns k=0-2 give: A065440, A055897, A081132(n-2) for n>=2.

Row sums give A000312.

Cf. A055135, A055136.

Programs

Mathematica

Clear[B] B[0] = {{x, y}, {t*y, x}}; B[n_] := B[n] = B[n - 1].B[0]; Table[Det[B[n]] /. x -> Sqrt[z] /. y -> 1 /. t -> n, {n, 0, 10}]; a = Join[{{1}}, Table[CoefficientList[Det[B[n]] /. x -> Sqrt[z] /. y ->1 /. t -> n, z], {n, 0, 10}]]; Flatten[a] (* Roger L. Bagula, Apr 09 2008 *)
row[n_] := CoefficientList[(x + n - 1)^n + O[x]^(n+1), x];
Table[row[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Apr 13 2017, after Geoffrey Critzer *)
Join[{1, 0, 1}, Table[Binomial[n, k]*(n - 1)^(n - k), {n, 2, 49}, {k, 0, n}]] // Flatten (* G. C. Greubel, Nov 14 2017 *)

PARI

for(n=0,15, for(k=0,n, print1(if(n==0 && k==0, 1, if(n==1 && k==0, 0, if(n==1 && k==1, 1, binomial(n,k)*(n-1)^(n-k)))), ", "))) \\ G. C. Greubel, Nov 14 2017

Formula

T(n, k) = C(n, k)*(n-1)^(n-k), for n>1.

E.g.f.: (-LambertW(-y)/y)^(x-1)/(1+LambertW(-y)). - Vladeta Jovovic

O.g.f. for row n: (x + n - 1)^n. - Geoffrey Critzer, Mar 21 2010