cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A306800 Square array whose entry A(n,k) is the number of endofunctions on a set of size n with preimage constraint {0,1,...,k}, for n >= 0, k >= 0, read by descending antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 1, 4, 6, 0, 1, 1, 4, 24, 24, 0, 1, 1, 4, 27, 204, 120, 0, 1, 1, 4, 27, 252, 2220, 720, 0, 1, 1, 4, 27, 256, 3020, 29520, 5040, 0, 1, 1, 4, 27, 256, 3120, 44220, 463680, 40320, 0, 1, 1, 4, 27, 256, 3125, 46470, 765030, 8401680, 362880, 0
Offset: 0

Views

Author

Benjamin Otto, Mar 10 2019

Keywords

Comments

A preimage constraint is a set of nonnegative integers such that the size of the inverse image of any element is one of the values in that set.
Thus, A(n,k) is the number of endofunctions on a set of size n such that each preimage has at most k entries. Equivalently, A(n,k) is the number of n-letter words from an n-letter alphabet such that no letter appears more than k times.

Examples

			Array begins:
  1    1     1     1     1 ...
  0    1     1     1     1 ...
  0    2     4     4     4 ...
  0    6    24    27    27 ...
  0   24   204   252   256 ...
  0  120  2220  3020  3120 ...
  0  720 29520 44220 46470 ...
  ...

Links

Crossrefs

Columns 0-9: A000007, A000142, A012244, A239368, A324804, A324805, A324806, A324807, A324808, A324809.
A(n,n) gives A000312.
Similar array for preimage condition {i>=0 | i!=k}: A245413.
Number of functions with preimage condition given by the even nonnegative integers: A209289.
Sum over all k of the number of functions with preimage condition {0,k}: A231812.
Cf. A019575.

Programs

  • Maple
    b:= proc(n, i, k) option remember; `if`(n=0 and i=0, 1, `if`(i<1, 0,
      add(b(n-j, i-1, k)*binomial(n, j), j=0..min(k, n))))
    end:
A:= (n, k)-> b(n$2, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, Apr 05 2019
  • Mathematica
    b[n_, i_, k_] := b[n, i, k] = If[n==0 && i==0, 1, If[i<1, 0, Sum[b[n-j, i-1, k] Binomial[n, j], {j, 0, Min[k, n]}]]];
A[n_, k_] := b[n, n, k];
Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 29 2019, after Alois P. Heinz *)
  • Python
    # print first num_entries entries in column k
import math, sympy; x=sympy.symbols('x')
k=5; num_entries = 64
P=range(k+1); eP=sum([x**d/math.factorial(d) for d in P]); r = [1]; curr_pow = 1
for term in range(1,num_entries):
   curr_pow=(curr_pow*eP).expand()
   r.append(curr_pow.coeff(x**term)*math.factorial(term))
print(r)

Formula

A(n,k) = n! * [x^n] e_k(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. When k>1, the link above yields explicit constants c_k, r_k so that the columns are asymptotically c_k * n^(-1/2) * r_k^-n. Stirling's approximation gives column k=1, and column k=0 is 0.
A(n,k) = Sum_{j=1..min(k,n)} A019575(n,j) for n>=1. - Alois P. Heinz, Jun 28 2023

Extensions

Offset changed to 0 by Alois P. Heinz, Jun 28 2023

A231807 Number of endofunctions on [n] with distinct cardinalities of the nonempty preimages.

Original entry on oeis.org

1, 1, 2, 21, 52, 305, 7836, 24703, 155688, 1034433, 67124260, 235173191, 1728147312, 11309344813, 106962615592, 14055613872945, 55558358852176, 450373499691137, 3156524223157332, 28327606849223119, 307533111218771040, 81782486813477643501
Offset: 0

Views

Author

Alois P. Heinz, Nov 13 2013

Keywords

Comments

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

Examples

			a(3) = 3! * (multinomial(3;3)/2! + multinomial(3;2,1)/1!) = 3+18 = 21: (1,1,1), (2,2,2), (3,3,3), (1,1,2), (1,1,3), (1,2,1), (1,3,1), (2,1,1), (3,1,1), (2,2,1), (2,2,3), (2,1,2), (2,3,2), (1,2,2), (3,2,2), (3,3,1), (3,3,2), (3,1,3), (3,2,3), (1,3,3), (2,3,3).
a(4) = 52: (1,1,1,1), (1,1,1,2), (1,1,1,3), ..., (4,4,4,2), (4,4,4,3), (4,4,4,4).

Links

Crossrefs

Column k=1 of A231915.
Cf. A000009, A000312, A231812.

Programs

  • Maple
    b:= proc(t, i, u) option remember; `if`(t=0, 1, `if`(i<1, 0,
       b(t, i-1, u) +`if`(i>t, 0, b(t-i, i-1, u-1)*u*binomial(t,i))))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..25);
  • Mathematica
    b[t_, i_, u_] := b[t, i, u] = If[t == 0, 1, If[i < 1, 0, b[t, i - 1, u] + If[i > t, 0, b[t - i, i - 1, u - 1] u Binomial[t, i]]]];
a[n_] := b[n, n, n];
a /@ Range[0, 25] (* Jean-François Alcover, Dec 10 2020, after Alois P. Heinz *)

Formula

a(n) = n! * Sum_{lambda} multinomial(n;lambda)/(n-|lambda|)!, where lambda ranges over all partitions of n into distinct parts (A118457).

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

Views

Author

Alois P. Heinz, Nov 15 2013

Keywords

Comments

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.

Examples

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

Links

Crossrefs

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

Programs

  • Maple
    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);
  • Mathematica
    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 *)
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.