A028498 Let [n] = {0,...,n-1}; a(n) is number of functions f:[n] -> [n] for which there exists an injection g:[n] -> [n+1] such that for j with 0 <= j < n, either g(j) = f(j) or g(j) = f(j)+1.

1, 4, 24, 186, 1770, 19980, 260820, 3863160, 63980280, 1171195200, 23476068000, 511296786000, 12021166357200, 303414507396000, 8182057223340000, 234753130435824000, 7139815170664176000, 229442416696164672000, 7767967204994540544000, 276345182709766890720000

Offset

0,2

Links

Table of n, a(n) for n=0..19.

Ariel Halpert, Flórián Lengyel and János Pach, Cellular telephone networks and random maps in hypergraphs, Discrete Appl. Math. 103 (2000), no. 1-3, 111-126.

Formula

a(n) = T(n, n) where T(1, n) = n, T(2, n) = n^2, and T(m, n) = T(m, n-1) + 2*m*T(m-1, n-1) - m*T(m-1, n-2) - binomial(m, 2)*T(m-2, n-2) for 1 <= m <= n+1. - Sean A. Irvine, Feb 03 2020

Crossrefs

Sequence in context: A271215 A135905 A239296 * A001397 A001506 A354123

Adjacent sequences: A028495 A028496 A028497 * A028499 A028500 A028501

Keyword

nonn

Author

Florian Lengyel (flengyel(AT)email.gc.cuny.edu)

Extensions

More terms from Sean A. Irvine, Feb 03 2020

Status

approved