A039621 -id:A039621 - cp's OEIS frontend

A045531 Number of sticky functions: endofunctions of [n] having a fixed point.

1, 3, 19, 175, 2101, 31031, 543607, 11012415, 253202761, 6513215599, 185311670611, 5777672071535, 195881901213181, 7174630439858727, 282325794823047151, 11878335717996660991, 532092356706983938321, 25283323623228812584415, 1270184310304975912766347

Offset: 1

Len Smiley

a(n) is also the number of functions f{1,2,...,n}->{1,2,...,n} with at least one element mapped to 1. - Geoffrey Critzer, Dec 10 2012
Equivalently, a(n) is the number of endofunctions with minimum 1. - Olivier Gérard, Aug 02 2016
Number of bargraphs of width n and height n. Equivalently: number of ordered n-tuples of positive integers such that the largest is n. Example: a(3) = 19 because we have 113, 123, 213, 223, 131, 132, 231, 232, 311, 312, 321, 322, 331, 332, 313, 323, 133, 233, and 333. - Emeric Deutsch, Jan 30 2017

Vincenzo Librandi, Table of n, a(n) for n = 1..100
A. Blecher, C. Brennan, A. Knopfmacher and H. Prodinger, The height and width of bargraphs, Discrete Applied Math. 180, (2015), 36-44.

Column |a(n, 2)| of A039621. Row sums of triangle A055858.
Cf. A000312, A066274, A066275, A047969.
Column k=1 of A246049.
Cf. A068996, A350454.

[n^n-(n-1)^n: n in [1..20] ]; // Vincenzo Librandi, May 07 2011

Table[Sum[Binomial[n, i] (n - 1)^(n - i), {i, 1, n}], {n, 1, 20}]

a(n) = sum(k!*binomial(n-1,k-1)*stirling2(n,k),k,1,n); /* Vladimir Kruchinin, Mar 01 2014 */

a(n)=n^n-(n-1)^n; \\ Charles R Greathouse IV, May 08 2011

a(n) = n^n - (n-1)^n.
E.g.f.: (T - x)/(T-T^2), where T=T(x) is Euler's tree function (see A000169).
With interpolated zeros, ceiling(n/2)^ceiling(n/2) - floor(n/2)^ceiling(n/2). - Paul Barry, Jul 13 2005
a(n) = A047969(n,n). - Alford Arnold, May 07 2005
a(n) = Sum_{i=1..n} binomial(n,i)*(i-1)^(i-1)*(n-i)^(n-i) = Sum_{i=1..n} binomial(n,i)*A000312(i-1)*A000312(n-i). - Vladimir Shevelev, Sep 30 2010
a(n) = Sum_{k=1..n} k!*binomial(n-1,k-1)*Stirling2(n,k). - Vladimir Kruchinin, Mar 01 2014
a(n) = A350454(n+1, 1) / (n+1). - Mélika Tebni, Dec 20 2022
Limit_{n->oo} a(n)/n^n = 1 - 1/e = A068996. - Luc Rousseau, Jan 20 2023

A008296 Triangle of Lehmer-Comtet numbers of the first kind.

Original entry on oeis.org

1, 1, 1, -1, 3, 1, 2, -1, 6, 1, -6, 0, 5, 10, 1, 24, 4, -15, 25, 15, 1, -120, -28, 49, -35, 70, 21, 1, 720, 188, -196, 49, 0, 154, 28, 1, -5040, -1368, 944, 0, -231, 252, 294, 36, 1, 40320, 11016, -5340, -820, 1365, -987, 1050, 510, 45, 1, -362880, -98208, 34716, 9020, -7645, 3003, -1617, 2970, 825, 55, 1, 3628800

Offset: 1

N. J. A. Sloane

Triangle arising in the expansion of ((1+x)*log(1+x))^n.

Also the Bell transform of (-1)^(n-1)*(n-1)! if n>1 else 1 adding 1,0,0,0,... as column 0. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 16 2016

			Triangle begins:
   1;
   1,  1;
  -1,  3,   1;
   2, -1,   6,  1;
  -6,  0,   5, 10,  1;
  24,  4, -15, 25, 15, 1;
  ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 139.

Alois P. Heinz, Rows n = 1..141, flattened
H. W. Gould, A Set of Polynomials Associated with the Higher Derivatives of y = x^x, Rocky Mountain J. Math. Volume 26, Number 2 (1996), 615-625.
Tian-Xiao He and Yuanziyi Zhang, Centralizers of the Riordan Group, arXiv:2105.07262 [math.CO], 2021.
D. H. Lehmer, Numbers Associated with Stirling Numbers and x^x, Rocky Mountain J. Math., 15(2) 1985, pp. 461-475.

Cf. A039621 (second kind), A354795 (variant), A185164, A005727 (row sums), A298511 (central).
Columns: A045406 (column 2), A347276 (column 3), A345651 (column 4).
Diagonals: A000142, A000217, A059302.
Cf. A176118.

for n from 1 to 20 do for k from 1 to n do
printf(`%d,`, add(binomial(l,k)*k^(l-k)*Stirling1(n,l), l=k..n)) od: od:
# second program:
A008296 := proc(n, k) option remember; if k=1 and n>1 then (-1)^n*(n-2)! elif n=k then 1 else (n-1)*procname(n-2, k-1) + (k-n+1)*procname(n-1, k) + procname(n-1, k-1) end if end proc:
seq(print(seq(A008296(n, k), k=1..n)), n=1..7); # Mélika Tebni, Aug 22 2021

a[1, 1] = a[2, 1] = 1; a[n_, 1] = (-1)^n (n-2)!;
a[n_, n_] = 1; a[n_, k_] := a[n, k] = (n-1) a[n-2, k-1] + a[n-1, k-1] + (k-n+1) a[n-1,k]; Flatten[Table[a[n, k], {n, 1, 12}, {k, 1, n}]][[1 ;; 67]]
(* Jean-François Alcover, Apr 29 2011 *)

{T(n, k) = if( k<1 || k>n, 0, n! * polcoeff(((1 + x) * log(1 + x + x * O(x^n)))^k / k!, n))}; /* Michael Somos, Nov 15 2002 */

# uses[bell_matrix from A264428]
# Adds 1, 0, 0, 0, ... as column 0 at the left side of the triangle.
bell_matrix(lambda n: (-1)^(n-1)*factorial(n-1) if n>1 else 1, 7) # Peter Luschny, Jan 16 2016

E.g.f. for a(n, k): (1/k!)[ (1+x)*log(1+x) ]^k. - Len Smiley
Left edge is (-1)*n!, for n >= 2. Right edge is all 1's.
a(n+1, k) = n*a(n-1, k-1) + a(n, k-1) + (k-n)*a(n, k).
a(n, k) = Sum_{m} binomial(m, k)*k^(m-k)*Stirling1(n, m).
From Peter Bala, Mar 14 2012: (Start)
E.g.f.: exp(t*(1 + x)*log(1 + x)) = Sum_{n>=0} R(n,t)*x^n/n! = 1 + t*x + (t+t^2)x^2/2! + (-t+3*t^2+t^3)x^3/3! + .... Cf. A185164. The row polynomials R(n,t) are of binomial type and satisfy the recurrence R(n+1,t) = (t-n)*R(n,t) + t*d/dt(R(n,t)) + n*t*R(n-1,t) with R(0,t) = 1 and R(1,t) = t. Inverse array is A039621.
(End)
Sum_{k=0..n} (-1)^k * a(n,k) = A176118(n). - Alois P. Heinz, Aug 25 2021

More terms from James Sellers, Jan 26 2001

Edited by N. J. A. Sloane at the suggestion of Andrew Robbins, Dec 11 2007

A055858 Coefficient triangle for certain polynomials.

Original entry on oeis.org

1, 1, 2, 4, 9, 6, 27, 64, 48, 36, 256, 625, 500, 400, 320, 3125, 7776, 6480, 5400, 4500, 3750, 46656, 117649, 100842, 86436, 74088, 63504, 54432, 823543, 2097152, 1835008, 1605632, 1404928, 1229312, 1075648, 941192, 16777216, 43046721

Offset: 0

Wolfdieter Lang, Jun 20 2000

The coefficients of the partner polynomials are found in triangle A055864.

			{1}; {1,2}; {4,9,6}; {27,64,48,36}; ...
Fourth row polynomial (n=3): p(3,x) = 27 + 64*x + 48*x^2 + 36*x^3.

Column sequences are A000312(n), n >= 1, A055860 (A000169), A055861 (A053506), A055862-3 for m=0..4, row sums: A045531(n+1)= |A039621(n+1, 2)|, n >= 0.

a[n_, m_] /; n < m = 0; a[0, 0] = 1; a[n_, 0] := n^n; a[n_, m_] := n^(m-1)*(n+1)^(n-m+1); Table[a[n, m], {n, 0, 8}, {m, 0, n}] // Flatten (* Jean-François Alcover, Jun 20 2013 *)

a(n, m)=0 if n < m; a(0, 0)=1, a(n, 0) = n^n, n >= 1, a(n, m) = n^(m-1)*(n+1)^(n-m+1), n >= m >= 1;

E.g.f. for column m: A(m, x); A(0, x) = 1/(1+W(-x)); A(1, x) = -1 - (d/dx)W(-x) = -1-W(-x)/((1+W(-x))*x); A(2, x) = A(1, x)-int(A(1, x), x)/x-(1/x+x); recursion: A(m, x) = A(m-1, x)-int(A(m-1, x), x)/x-((m-1)^(m-1))*(x^(m-1))/(m-1)!, m >= 3; W(x) principal branch of Lambert's function.

A354794 Triangle read by rows. The Bell transform of the sequence {m^m | m >= 0}.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 4, 3, 1, 0, 27, 19, 6, 1, 0, 256, 175, 55, 10, 1, 0, 3125, 2101, 660, 125, 15, 1, 0, 46656, 31031, 9751, 1890, 245, 21, 1, 0, 823543, 543607, 170898, 33621, 4550, 434, 28, 1, 0, 16777216, 11012415, 3463615, 688506, 95781, 9702, 714, 36, 1

Offset: 0

Peter Luschny, Jun 09 2022

For the definition of the Bell transform see A264428. The Bell transform of {(-m)^m | m >= 0} is A039621. The numbers A039621(n, k) are known as the Lehmer-Comtet numbers of 2nd kind. We think it is more natural to use Bell_{n, k}({m^m}) as the basis for the definition (and let the triangle start at (0, 0)).

			Triangle T(n, k) begins:
[0] 1;
[1] 0,        1;
[2] 0,        1,        1;
[3] 0,        4,        3,       1;
[4] 0,       27,       19,       6,      1;
[5] 0,      256,      175,      55,     10,     1;
[6] 0,     3125,     2101,     660,    125,    15,    1;
[7] 0,    46656,    31031,    9751,   1890,   245,   21,   1;
[8] 0,   823543,   543607,  170898,  33621,  4550,  434,  28,  1;
[9] 0, 16777216, 11012415, 3463615, 688506, 95781, 9702, 714, 36, 1;

Louis Comtet, Advanced Combinatorics. Reidel, Dordrecht, 1974, p. 139-140.

D. H. Lehmer, Numbers Associated with Stirling Numbers and x^x, Rocky Mountain J. Math., 15(2) 1985, pp. 461-475.
Peter Luschny, The Bell transform
Wikipedia, Bell polynomials.

Cf. A264428, A039621 (signed variant), A195979 (row sums), A000312 (column 1), A045531 (column 2), A281596 (column 3), A281595 (column 4), A000217 (diagonal 1), A215862 (diagonal 2), A354795 (matrix inverse), A137452 (Abel).

T := (n, k) -> if n = k then 1 else
add((-1)^j*(n-j-1)^(n-1)/(j!*(k-1-j)!), j = 0.. k-1) fi:
seq(seq(T(n, k), k = 0..n), n = 0..9);
# Alternatively, using the function BellMatrix from A264428:
BellMatrix(n -> n^n, 9);
# Or by recursion:
R := proc(n, k, m) option remember;
   if k < 0 or n < 0 then 0 elif k = 0 then 1 else
   m*R(n, k-1, m) + R(n-1, k, m+1) fi end:
A039621 := (n, k) -> ifelse(n = 0, 1, R(k-1, n-k, n-k)):

Unprotect[Power]; Power[0, 0] = 1; pow[n_] := n^n;
R = Range[0, 9]; T[n_, k_] := BellY[n, k, pow[R]];
Table[T[n, k], {n, R}, {k, 0, n}] // Flatten

from functools import cache
@cache
def t(n, k, m):
    if k < 0 or n < 0: return 0
    if k == 0: return n ** k
    return m * t(n, k - 1, m) + t(n - 1, k, m + 1)
def A354794(n, k): return t(k - 1, n - k, n - k) if n != k else 1
for n in range(9): print([A354794(n, k) for k in range(n + 1)])

T(n, k) = Bell_{n, k}(A000312), where Bell_{n, k} is the partial Bell polynomial evaluated over the powers m^m (with 0^0 = 1). See the Mathematica program.
T(n, k) = Sum_{j=0..k-1} (-1)^j*(n-j-1)^(n - 1)/(j! * (k-1-j)!) for 0 <= k < n and T(n, n) = 1.
T(n, k) = r(k-1, n-k, n-k) for n,k >= 1 and T(0, 0) = 1, where r(n, k, m) = m*r(n, k-1, m) + r(n-1, k, m+1) and r(n, 0, m) = 1. (see Vladimir Kruchinin's formula in A039621).
Sum_{k=1..n} binomial(k + x - 1, k-1)*(k-1)!*T(n, k) = (n + x)^(n - 1) for n >= 1.
Sum_{k=1..n} (-1)^(k+j)*Stirling1(k, j)*T(n, k) = n^(n-j)*binomial(n-1, j-1) for n >= 1, which are, up to sign, the coefficients of the Abel polynomials (A137452).
From Werner Schulte, Jun 14 2022 and Jun 19 2022: (Start)
E.g.f. of column k >= 0: (Sum_{i>0} (i-1)^(i-1) * t^i / i!)^k / k!.
Conjecture: T(n, k) = Sum_{i=0..n-k} A048994(n-k, i) * A048993(n+i-1, n-1) for 0 < k <= n and T(n, 0) = 0^n for n >= 0; proved by Mike Earnest, see link at A354797. (End)

A126781 Number of functions f:{1,2,...,n}->{1,2,...,n} such that Im(f) contains 6 fixed elements.

Original entry on oeis.org

720, 20160, 514080, 13608000, 385363440, 11760819840, 386860668480, 13682898028800, 518666099711760, 20997894426949440, 904827327153291360, 41367795437773022400, 2000634709955550047280, 102066613831917982920960

Offset: 6

Aleksandar M. Janjic and Milan Janjic, Feb 18 2007

nonn

			a(7)=20160

Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets

Cf. A039621 (Lehmer-Comtet numbers of 2nd kind).

a:=n->n^n-6*(n-1)^n+15*(n-2)^n-20*(n-3)^n+15*(n-4)^n-6*(n-5)^n+(n-6)^n;

Drop[Table[Sum[(-1)^k Binomial[6,k] (n-k)^n,{k,0,6}],{n,1,20}],5]  (* Geoffrey Critzer, Dec 23 2012 *)

a(n)=n^n-6*(n-1)^n+15*(n-2)^n-20*(n-3)^n+15*(n-4)^n-6*(n-5)^n+(n-6)^n, (n=6,7,...)

cp's OEIS Frontend

A045531 Number of sticky functions: endofunctions of [n] having a fixed point.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Formula

A008296 Triangle of Lehmer-Comtet numbers of the first kind.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A055858 Coefficient triangle for certain polynomials.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A354794 Triangle read by rows. The Bell transform of the sequence {m^m | m >= 0}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A126781 Number of functions f:{1,2,...,n}->{1,2,...,n} such that Im(f) contains 6 fixed elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula