A185391 -id:A185391 - cp's OEIS frontend

A185390 Triangular array read by rows. T(n,k) is the number of partial functions on n labeled objects in which the domain of definition contains exactly k elements such that for all i in {1,2,3,...}, (f^i)(x) is defined.

1, 1, 1, 3, 2, 4, 16, 9, 12, 27, 125, 64, 72, 108, 256, 1296, 625, 640, 810, 1280, 3125, 16807, 7776, 7500, 8640, 11520, 18750, 46656, 262144, 117649, 108864, 118125, 143360, 196875, 326592, 823543, 4782969, 2097152, 1882384, 1959552, 2240000, 2800000, 3919104, 6588344, 16777216

Offset: 0

Geoffrey Critzer, Feb 09 2012

Here, for any x in the domain of definition (f^i)(x) denotes the i-fold composition of f with itself, e.g., (f^2)(x) = f(f(x)). The domain of definition is the set of all values x for which f(x) is defined.
T(n,n) = n^n, the partial functions that are total functions.
T(n,0) = A000272(offset), see comment and link by Dennis P. Walsh.

			Triangle begins:
      1;
      1,     1;
      3,     2,     4;
     16,     9,    12,    27;
    125,    64,    72,   108,   256;
   1296,   625,   640,   810,  1280,  3125;
  16807,  7776,  7500,  8640, 11520, 18750, 46656;
  ...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Geoffrey Critzer, Distribution of non-functional points under a random partial function
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 132, II.21.

Row sums give A000169(n+1).
T(n,n-1) gives A055897(n).
T(n,n)-T(n,n-1) gives A060226(n).
Cf. A000272, A000312, A185391.

T(n, k) = binomial(n, k)*k^k*(n-k+1)^(n-k-1)
for n in 0:9 (println([T(n, k) for k in 0:n])) end
# Peter Luschny, Jan 12 2024

T:= (n, k)-> binomial(n,k)*k^k*(n-k+1)^(n-k-1):
seq(seq(T(n,k), k=0..n), n=0..10);  # Alois P. Heinz, Jan 12 2024

nn = 7; tx = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; txy = Sum[n^(n - 1) (x y)^n/n!, {n, 1, nn}]; f[list_] := Select[list, # > 0 &]; Map[f, Range[0, nn]! CoefficientList[Series[Exp[tx]/(1 - txy), {x, 0, nn}], {x, y}]] // Flatten

E.g.f.: exp(T(x))/(1-T(x*y)) where T(x) is the e.g.f. for A000169.
T(n,k) = binomial(n,k)*k^k*(n-k+1)^(n-k-1). - Geoffrey Critzer, Feb 28 2022
Sum_{k=0..n} k * T(n,k) = A185391(n). - Alois P. Heinz, Jan 12 2024

A345445 a(n) = n^n - (n+1)!/2.

Original entry on oeis.org

0, 1, 15, 196, 2765, 44136, 803383, 16595776, 385606089, 9980041600, 285072169811, 8912986937856, 302831517446653, 11111352988374016, 437883428985915375, 18446566229995503616, 827237060699483900177, 39346347252746333159424, 1978418439209309500803979, 104857574454528914145280000

Offset: 1

Olivier Gérard, Jun 19 2021

This sequence appears as a class of nonsortable words of length n for several unadapted sorting algorithms. For instance this one:
- scan all values not at their index position
- rotate left 1 step all of them as a cycle
- repeat.
This is linked to the fact that one can encode the alternating permutations of length n+1 as words of length n.

Cf. A185391 (Complement to n^n of a class of words).

Mathematica
```
Table[n^n - (n + 1)!/2, {n, 1, 20}]
```

cp's OEIS Frontend

A185390 Triangular array read by rows. T(n,k) is the number of partial functions on n labeled objects in which the domain of definition contains exactly k elements such that for all i in {1,2,3,...}, (f^i)(x) is defined.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Maple

Mathematica

Formula