A231807 -id:A231807 - cp's OEIS frontend

A231812 Number of endofunctions on [n] where all nonempty preimages have the same cardinality.

1, 1, 4, 9, 64, 125, 2826, 5047, 218688, 504009, 32216950, 39916811, 7585223196, 6227020813, 2424646536326, 1813027195995, 1072898135852416, 355687428096017, 616925243565037854, 121645100408832019, 441395941479128984940, 72313131901887676821

Offset: 0

Alois P. Heinz, Nov 13 2013

nonn

Number of endofunctions f:{1,...,n}-> {1,...,n} such that (1<=i0 and |f^(-1)(j)|>0) implies |f^(-1)(i)| = |f^(-1)(j)|.

			a(2) = 4: (1,1), (1,2), (2,1), (2,2).
a(3) = 9: (1,1,1), (1,2,3), (1,3,2), (2,1,3), (2,2,2), (2,3,1), (3,1,2), (3,2,1), (3,3,3).
a(4) = 64: (1,1,1,1), (1,1,2,2), (1,1,3,3), ..., (4,4,3,3), (4,4,4,4).

Alois P. Heinz, Table of n, a(n) for n = 0..300

Main diagonal of A231915.

Cf. A000312, A005095, A231807.

with(numtheory): with(combinat): C:= binomial:
a:= n-> `if`(n=0, 1, add(multinomial(n, n/d$d)*C(n, d), d=divisors(n))):
seq(a(n), n=0..25);

multinomial[n_, k_List] := n!/Times @@ (k!); a[n_] := If[n == 0, 1, Sum[multinomial[n, Array[n/d&, d]]*Binomial[n, d], {d, Divisors[n]}]]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

a(n) = Sum_{d|n} multinomial(n; {n/d}^d)*C(n,d) for n>0, a(0) = 1.

a(n) = n! + n = A005095(n) for prime n.

A231915 Number T(n,k) of endofunctions on [n] such that at most k elements with nonempty preimage have equal preimage cardinality and non-equinumerous preimages have cardinalities that differ by at least k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 2, 4, 0, 21, 3, 9, 0, 52, 88, 40, 64, 0, 305, 705, 105, 5, 125, 0, 7836, 2736, 4086, 2286, 2106, 2826, 0, 24703, 20293, 34993, 4711, 301, 7, 5047, 0, 155688, 557488, 107472, 283872, 188224, 178816, 178368, 218688

Offset: 0

Alois P. Heinz, Nov 15 2013

T(n,k) is defined for n,k >= 0. The triangle contains terms with k <= n. T(n,k) = T(n,n) = A231812(n) for k >= n.
T(p,p) = p! + p = A005095(p) for p prime.
T(p,p-1) = p for prime p.

			Triangle T(n,k) begins:
  1;
  0,     1;
  0,     2,     4;
  0,    21,     3,     9;
  0,    52,    88,    40,   64;
  0,   305,   705,   105,    5,  125;
  0,  7836,  2736,  4086, 2286, 2106, 2826;
  0, 24703, 20293, 34993, 4711,  301,    7, 5047;
  ...

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-1 give: A000007, A231807,
Main diagonal gives: A231812.
T(n,n)-T(n,n-1) gives: A000142.
Cf. A005095.

with(combinat):
b:= proc(t, i, u, k) option remember; `if`(t=0, 1,
      `if`(i<1, 0, b(t, i-1, u, k) +add(multinomial(t, t-i*j, i$j)
      *b(t-i*j, i-k, u-j, k)*u!/(u-j)!/j!, j=1.. min(k, t/i) )))
    end:
T:= (n, k)-> b(n$3, k):
seq(seq(T(n, k), k=0..n), n=0..11);

multinomial[n_, k_List] := n!/Times@@(k!); b[t_, i_, u_, k_] := b[t, i, u, k] = If[t == 0, 1, If[i < 1, 0, b[t, i-1, u, k] + Sum[multinomial[t, Join[{t-i*j}, Array[i&, j]]]*b[t-i*j, i-k, u-j, k]*u!/(u-j)!/j!, {j, 1, Min[k, t/i]}]]]; T[n_, k_] := b[n, n, n, k]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 11}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

cp's OEIS Frontend

A231812 Number of endofunctions on [n] where all nonempty preimages have the same cardinality.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula