A090657 -id:A090657 - cp's OEIS frontend

A101817 Triangle read by rows: T(n,h) = number of functions f:{1,2,...,n}->{1,2,...,n} such that |Image(f)|=h; h=1,2,...,n, n=1,2,3,... . Essentially A090657, but without zeros.

1, 2, 2, 3, 18, 6, 4, 84, 144, 24, 5, 300, 1500, 1200, 120, 6, 930, 10800, 23400, 10800, 720, 7, 2646, 63210, 294000, 352800, 105840, 5040, 8, 7112, 324576, 2857680, 7056000, 5362560, 1128960, 40320, 9, 18360, 1524600, 23496480, 105099120

Offset: 1

Clark Kimberling, Dec 17 2004

Row sums = n^n. T(n,1) = n, T(n,n) = n!.

			First rows:
1;
2,   2;
3,  18,   6;
4,  84, 144,  24;

H. Picquet, Note #124, L'Intermédiaire des Mathématiciens, 1 (1894), pp. 125-127. - N. J. A. Sloane, Feb 28 2022

Cf. A090657, A048993, A101818, A101819, A101821, A288312.

Table[Table[StirlingS2[n, k] Binomial[n, k] k!, {k, 1, n}], {n, 1, 8}] // Grid

T(n, h) = C(n, h)*U(n, h), where U(n, h) is the array in A019538. Thus T(n, h) = C(n, h)*h!*S(n, h), where S(n, h) is a Stirling number of the second kind (given by A048993 with zeros removed).

T(2n,n) = A288312(n). - Alois P. Heinz, Jun 07 2017

A098546 Table read by rows: row n has a term T(n,k) for each of the partition(n) partitions of n. T(n,k) = binomial(n,m) where m is the number of parts.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 6, 6, 4, 1, 5, 10, 10, 10, 10, 5, 1, 6, 15, 15, 15, 20, 20, 20, 15, 15, 6, 1, 7, 21, 21, 21, 35, 35, 35, 35, 35, 35, 35, 21, 21, 7, 1, 8, 28, 28, 28, 28, 56, 56, 56, 56, 56, 70, 70, 70, 70, 70, 56, 56, 56, 28, 28, 8, 1, 9, 36, 36, 36, 36, 84, 84, 84, 84, 84, 84, 84

Offset: 1

Alford Arnold, Sep 14 2004

A035206 and A036038 were used to generate A049009 (Words over signatures). A098346 and A049019 provide another approach to the same end since A098346 times A049019 also yields A049009. (cf. A000312 and A000670).

Partitions are in Abramowitz and Stegun order. - Franklin T. Adams-Watters, Nov 20 2006

			A036042 begins 1 2 2 3 3 3 4 4 4 4 4 ...
A036043 begins 1 1 2 1 2 3 1 2 2 3 4 ...
so a(n) begins 1 2 1 3 3 1 4 6 6 4 1 ...
Table begins
.
1
2 1
3 3  1
4 6  6  4  1
5 10 10 10 10 5  1
6 15 15 20 15 20 15 20 15 6 1
.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

Cf. A090657, A000041 (row lengths), A098545 (row sums), A036036, A036042, A036043.

Table[Sequence @@
  Map[Function[p, Binomial[n, Length[p]]], IntegerPartitions[n]], {n,
  1, 10}] (* Olivier Gérard, May 07 2024 *)

a(n) = Combin( A036042(n), A036043(n) )

A068605 Number of functions from [1,2,...,n] to [1,2,...,n] such that the image contains exactly two elements.

Original entry on oeis.org

2, 18, 84, 300, 930, 2646, 7112, 18360, 45990, 112530, 270204, 638820, 1490762, 3440430, 7864080, 17825520, 40107726, 89652906, 199229060, 440401500, 968883762, 2122317318, 4630511064, 10066329000, 21810380150, 47110421826, 101468601612, 217969589460, 467077692570

Offset: 2

Sharon Sela (sharonsela(AT)hotmail.com), Mar 29 2002

The sequence is the column corresponding to k=2 in A090657. - Geoffrey Critzer, Mar 06 2009

Stefano Spezia, Table of n, a(n) for n = 2..3200
Index entries for linear recurrences with constant coefficients, signature (9,-33,63,-66,36,-8).

Cf. A000918, A090657, A161680.

Table[ Binomial[n, 2]*(2^n - 2), {n, 2, 30}]

def A068605(n): return n*(n-1)*((1<Chai Wah Wu, Jun 20 2025

a(n) = C(n, 2) * (2^n - 2).
O.g.f.: (4x^2/(1-2x)^3) - (2x^2/(1-x)^3). - Geoffrey Critzer, Mar 06 2009
E.g.f.: exp(x)*(2*exp(x) - 1)*x^2. - Stefano Spezia, May 06 2023

Edited and extended by Robert G. Wilson v, Apr 17 2002

A288312 Number of endofunctions on [2n] such that the image size equals n.

Original entry on oeis.org

1, 2, 84, 10800, 2857680, 1285956000, 880599202560, 853262368358400, 1111400775560275200, 1873276460474747328000, 3967400888465895264384000, 10313998054713896966296473600, 32291970618091110826769565696000, 119851615755915509174015455948800000

Offset: 0

Alois P. Heinz, Jun 07 2017

nonn

			a(1) = 2: (1,1), (2,2).

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

Cf. A000142, A048993, A090657, A101817, A219859.

b:= proc(n, k) option remember; `if`(k=n, n!,
      `if`(k=0, 0, n*(b(n-1, k-1)+b(n-1, k)*k/(n-k))))
    end:
a:= n-> b(2*n, n):
seq(a(n), n=0..15);

Table[StirlingS2[2*n, n]*(2*n)!/n!, {n, 0, 20}] (* Vaclav Kotesovec, Jun 10 2017 *)

a(n)=stirling(2*n, n, 2)*n!*binomial(2*n, n); \\ Indranil Ghosh, Jul 04 2017

from mpmath import *
mp.dps=100
def a(n): return int(stirling2(2*n, n)*fac(n)*binomial(2*n, n))
print([a(n) for n in range(21)]) # Indranil Ghosh, Jul 04 2017

a(n) = Stirling2(2*n,n) * n! * binomial(2*n,n).
a(n) = A090657(2n,n) = A101817(2n,n) = A219859(2n,n).
a(n) ~ n^(2*n - 1/2) * 2^(4*n) / (sqrt(Pi*(1-c)) * c^n * (2-c)^n * exp(2*n)), where c = -LambertW(-2*exp(-2)) = -A226775 = 0.4063757399599599... - Vaclav Kotesovec, Jun 10 2017

A090683 Triangle read by rows, defined by T(n,k) = C(n,k)*S2(n,k), 0 <= k <= n, where C(n,k) are the binomial coefficients and S2(n,k) are the Stirling numbers of the second kind.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 3, 9, 1, 0, 4, 42, 24, 1, 0, 5, 150, 250, 50, 1, 0, 6, 465, 1800, 975, 90, 1, 0, 7, 1323, 10535, 12250, 2940, 147, 1, 0, 8, 3556, 54096, 119070, 58800, 7448, 224, 1, 0, 9, 9180, 254100, 979020, 875826, 222264, 16632, 324, 1, 0, 10, 22995, 1119600, 7162050, 10716300, 4793670, 705600, 33750, 450, 1

Offset: 0

Philippe Deléham, Dec 18 2003

T(n,k) is the number of Green's H-classes contained in the D-class of rank k in the full transformation semigroup on [n]. - Geoffrey Critzer, Dec 27 2022

			Triangle begins:
  1;
  0,  1;
  0,  2,  1;
  0,  3,  9,  1;
  0,  4, 42, 24,  1;
  ...

O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, Springer, 2009, pages 58-62.

Vincenzo Librandi, Table of n, a(n) for n = 0..230
Wikipedia, Green's relations
Wikipedia, Transformation semigroup

Cf. A007318, A048993, A090657.

Row sum sequence is A122455.

Flatten[Table[Table[Binomial[n, k] StirlingS2[n, k], {k, 0, n}], {n, 0, 10}], 1]

create_list(binomial(n,k)*stirling2(n,k),n,0,12,k,0,n); /* Emanuele Munarini, Mar 11 2011 */

T(n, k) = binomial(n,k)*Stirling2(n,k).
T(n, k) = A007318(n, k)*A048993(n, k).
T(n, k) = A090657(n, k)/k!.

Edited by Olivier Gérard, Oct 23 2012

A098545 Row sums of A098546.

Original entry on oeis.org

1, 3, 7, 21, 51, 148, 365, 983, 2461, 6360, 15687, 39757, 97033, 240425, 582622, 1421273, 3409861, 8222920, 19565707, 46680362, 110309476, 260876036, 612293443, 1437616751, 3354111156, 7823501148, 18157700800, 42112132458

Offset: 1

Alford Arnold, Sep 14 2004

By using multisets (cf. A001700) and multinomials (cf. A005651); A035206 and A036038 were used to generate A049009 (Words over signatures). A098346 and A049019 provide another approach to the same end (compare A090657).

			A098546 begins
1
1 2
1 3 3
1 4 6 6 4
so sequence begins 1 3 7 21 ...

Cf. A000041, A000312.

a(n) = Sum_{k=1..n} binomial(n, k)*A008284(n, k). - Vladeta Jovovic, Jul 24 2005

More terms from Vladeta Jovovic, Jul 24 2005

A101818 Triangle read by rows: (1/n)*T(n,h), where T(n,h) is the array in A101817.

Original entry on oeis.org

1, 1, 1, 1, 6, 2, 1, 21, 36, 6, 1, 60, 300, 240, 24, 1, 155, 1800, 3900, 1800, 120, 1, 378, 9030, 42000, 50400, 15120, 720, 1, 889, 40572, 357210, 882000, 670320, 141120, 5040, 1, 2040, 169400, 2610720, 11677680, 17781120, 9313920, 1451520, 40320

Offset: 1

Clark Kimberling, Dec 17 2004

Column 2 is A066524.

T(n,h) is the number of partial functions f:{1,2,...,n-1}->{1,2,...,n-1} such that |Image(f)| = h-1. Equivalently T(n,h) = |D_h(a)| where D_h(a) is Green's D-class containing a, with a in the semigroup of partial transformations on [n-1] and rank(a) = h-1. - Geoffrey Critzer, Jan 02 2022

			First rows:
1
1 1
1 6 2
1 21 36 6

O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, 2009, page 61.

Cf. A019538, A066524, A090657, A101817, A101819, A101820, A101821, A000169 (row sums).

Table[Table[StirlingS2[n, k] (n-1)!/(n - k)!, {k, 1, n}], {n, 1,
   6}] // Grid (* Geoffrey Critzer, Jan 02 2022 *)

T(n, h) = (1/n)*C(n, h)*U(n, h), where U(n, h) is the array in A019538.

T(n, h) = Stirling2(n,h)*(n-1)!/(n-h)!. - Geoffrey Critzer, Jan 02 2022

Offset changed to 1 by Alois P. Heinz, Jan 03 2022

A219859 Triangular array read by rows: T(n,k) is the number of endofunctions, functions f:{1,2,...,n}->{1,2,...,n}, that have exactly k elements with no preimage; n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 0, 2, 2, 0, 6, 18, 3, 0, 24, 144, 84, 4, 0, 120, 1200, 1500, 300, 5, 0, 720, 10800, 23400, 10800, 930, 6, 0, 5040, 105840, 352800, 294000, 63210, 2646, 7, 0, 40320, 1128960, 5362560, 7056000, 2857680, 324576, 7112, 8, 0, 362880, 13063680, 83825280, 160030080, 105099120, 23496480, 1524600, 18360, 9, 0

Offset: 0

Geoffrey Critzer, Dec 01 2012

Equivalently, T(n,k) is the number of endofunctions whose functional digraph has exactly k leaves.
Equivalently, T(n,k) is the number of doubly rooted trees with k leaves.  Here, a doubly rooted tree is a labeled tree in which two special vertices have been selected and the order of the selection matters. [Bona page 266]
Row sums are n^n.

			Triangle T(n,k) begins:
    1;
    1,     0;
    2,     2,     0;
    6,    18,     3,     0;
   24,   144,    84,     4,   0;
  120,  1200,  1500,   300,   5, 0;
  720, 10800, 23400, 10800, 930, 6, 0;
  ...

M. Bona, Introduction to Enumerative Combinatorics, McGraw Hill, 2007.

Column k=0-1 give: A000142, A001804.
Row sums give A000312.
T(2n,n) gives A288312.
Cf. A055302, A055314, A090657, A101817, A209290, A344053.

Table[Table[n!/k!StirlingS2[n,n-k],{k,0,n}],{n,0,8}]//Grid

row(n) = vector(n+1, k, k--; n!/k! * stirling(n,n-k,2)); \\ Michel Marcus, Jan 24 2022

T(n,k) = n!/k! * Stirling2(n,n-k).
T(n,0) = n!.
T(n,k) = A055302(n,k)*(n-k) + A055302(n,k+1)*(k+1).  The first term (on rhs of this equation) is the number of such functions in which the preimage of f(n) contains more than one element. The second term is the number of such functions in which the preimage of f(n) contains exactly one element.
T(n,k) = binomial(n,k) Sum_{j=0..n-k}(-1)^j*binomial(n-k,j)*(n-k-j)^n. - Geoffrey Critzer, Aug 20 2013
E.g.f.:  1/(1 - (A(x,y) - y*x + x)) where A(x,y) is the e.g.f. for A055302. - Geoffrey Critzer, Jan 24 2022
From Alois P. Heinz, Jan 24 2022: (Start)
Sum_{k=0..n} k * T(n,k) = A209290(n).
Sum_{k=0..n} (-1)^k * T(n,k) = A344053(n). (End)

A152170 a(n) is the total size of all the image sets of all functions from [n] to [n]. I.e., a(n) is the sum of the cardinalities of every image set of every function whose domain and co-domain is {1,2,...,n}.

Original entry on oeis.org

0, 1, 6, 57, 700, 10505, 186186, 3805249, 88099320, 2278824849, 65132155990, 2038428376721, 69332064858420, 2546464715771353, 100444826158022178, 4234886922345707265, 190053371487946575856, 9045570064018726951457, 455099825218118626519470

Offset: 0

Geoffrey Critzer, Nov 27 2008

nonn

a(n)/n^n is the expected value for the cardinality of the image set of a function that takes [n] to [n].

a(n)/n^(n+1) is the probability that any particular element of [n] will be in the range of a function f : [n] to [n].

			a(2) = 6 because the image sets of the functions from [2] to [2] are {1},{2},{1,2},{1,2}.

[n*(n^n-(n-1)^n): n in [0..20]]; // Vincenzo Librandi, Jul 23 2017

Table[Sum[StirlingS2[n, i] i! Binomial[n, i] i, {i, 1, n}], {n, 0, 20}] (* Geoffrey Critzer, Mar 17 2009 *)

a(n) = n*(n^n - (n-1)^n).
a(n) = Sum_{i=1..n} S(n,i)*i!*binomial(n,i)*i where S(n,i) is the Stirling number of the second kind.
a(n) = Sum_{k=1..n} A090657(n,k)*k.
Limit_{n->infinity} a(n)/n^(n+1) = (e-1)/e. - Thomas Dybdahl Ahle, Apr 24 2011

More terms from Geoffrey Critzer, Mar 17 2009

A185289 In a bipartite graph with 2n vertices (|V_1|=|V_2|=n), this sequence gives the number of ways to create n edges, one for each vertex of V_1, and to rank the vertices of V_2 which have incident edges.

Original entry on oeis.org

1, 1, 6, 75, 1612, 52805, 2442666, 151382959, 12093970008, 1209295535049, 147859385866390, 21692929137930611, 3759744512444581860, 759740612270504941453, 177000400360669503651138, 47085371754008630756331255, 14182051733113750632290151856

Offset: 0

Paolo Hägler, Feb 20 2011

nonn

a(n) is the number of ways to choose a function f:{1,2,...,n}->{1,2,...,n} and then linearly order the blocks of the coimage of f. - Geoffrey Critzer, Dec 23 2011

			For n=2 the a(2)=6 solutions are Aab, Bab, AaBb, AbBa, BbAa, BaAb. The capital letters are the vertices of V_2, in order, and the lower-case letters are the vertices of V_1 joined to the vertex of V_2 represented by the capital letter.

Paolo Hägler, Il problema dei pasti, Bollettino dei docenti di matematica, 63 (2011), 101-108

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

f:= n-> add(add((-1)^(i-j)*j^n*n!*i!/(j!*(i-j)!*(n-i)!),j=0..i),i=0..n);
[seq(f(n),n=0..20)]; # N. J. A. Sloane, Mar 08 2011

Table[Sum[Binomial[n, k] StirlingS2[n, k] k!^2, {k, 0, n}], {n, 0,20}]  (* Geoffrey Critzer, Dec 23 2011 *)

a(n) = sum(k=0, n, binomial(n,k)*stirling(n,k,2)*k!^2); \\ Michel Marcus, Mar 23 2016

a(n) = Sum_{k=0..n} Sum_{j=0..k} (-1)^(k-j)*j^n*n!/(n-k)!*k!/(j!*(k-j)!). Paolo Hägler, Feb 20 2011
a(n) = Sum_{k=0..n} C(n,k)*Stirling2(n,k)*k!^2.
a(n) = Sum_{k=0..n} A090657(n,k)*k!.

cp's OEIS Frontend

A101817 Triangle read by rows: T(n,h) = number of functions f:{1,2,...,n}->{1,2,...,n} such that |Image(f)|=h; h=1,2,...,n, n=1,2,3,... . Essentially A090657, but without zeros.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

Formula

A098546 Table read by rows: row n has a term T(n,k) for each of the partition(n) partitions of n. T(n,k) = binomial(n,m) where m is the number of parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A068605 Number of functions from [1,2,...,n] to [1,2,...,n] such that the image contains exactly two elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A288312 Number of endofunctions on [2n] such that the image size equals n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A090683 Triangle read by rows, defined by T(n,k) = C(n,k)*S2(n,k), 0 <= k <= n, where C(n,k) are the binomial coefficients and S2(n,k) are the Stirling numbers of the second kind.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Maxima

Formula

Extensions

A098545 Row sums of A098546.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A101818 Triangle read by rows: (1/n)*T(n,h), where T(n,h) is the array in A101817.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs