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,5

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

Links

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Eric W. Weisstein's World of Mathematics, Brahmagupta Matrix.

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

Example

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

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

Prog

(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

Crossrefs

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

Row sums give A000312.

Cf. A055135, A055136.

Sequence in context: A328821 A367382 A118708 * A137370 A214272 A214273

Adjacent sequences: A055131 A055132 A055133 * A055135 A055136 A055137

Keyword

nonn,tabl

Author

Christian G. Bower, Apr 25 2000

Status

approved