login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 7
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,9

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.

LINKS

Table of n, a(n) for n=1..66.

B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.6 and 7.8.

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.

EXAMPLE

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

  ...

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

PROG

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

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.

Sequence in context: A292712 A331571 A247504 * A235955 A077762 A244677

Adjacent sequences:  A306797 A306798 A306799 * A306801 A306802 A306803

KEYWORD

easy,nonn,tabl

AUTHOR

Benjamin Otto, Mar 10 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 03:47 EST 2021. Contains 340301 sequences. (Running on oeis4.)