A066274 -id:A066274 - 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

A228273 T(n,k) is the number of s in {1,...,n}^n having longest ending contiguous subsequence with the same value of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 2, 2, 0, 18, 6, 3, 0, 192, 48, 12, 4, 0, 2500, 500, 100, 20, 5, 0, 38880, 6480, 1080, 180, 30, 6, 0, 705894, 100842, 14406, 2058, 294, 42, 7, 0, 14680064, 1835008, 229376, 28672, 3584, 448, 56, 8, 0, 344373768, 38263752, 4251528, 472392, 52488, 5832, 648, 72, 9

Offset: 0

Alois P. Heinz, Aug 19 2013

			T(0,0) = 1: [].
T(1,1) = 1: [1].
T(2,1) = 2: [1,2], [2,1].
T(2,2) = 2: [1,1], [2,2].
T(3,1) = 18: [1,1,2], [1,1,3], [1,2,1], [1,2,3], [1,3,1], [1,3,2], [2,1,2], [2,1,3], [2,2,1], [2,2,3], [2,3,1], [2,3,2], [3,1,2], [3,1,3], [3,2,1], [3,2,3], [3,3,1], [3,3,2].
T(3,2) = 6: [1,2,2], [1,3,3], [2,1,1], [2,3,3], [3,1,1], [3,2,2].
T(3,3) = 3: [1,1,1], [2,2,2], [3,3,3].
Triangle T(n,k) begins:
  1;
  0,        1;
  0,        2,       2;
  0,       18,       6,      3;
  0,      192,      48,     12,     4;
  0,     2500,     500,    100,    20,    5;
  0,    38880,    6480,   1080,   180,   30,   6;
  0,   705894,  100842,  14406,  2058,  294,  42,  7;
  0, 14680064, 1835008, 229376, 28672, 3584, 448, 56,  8;

Alois P. Heinz, Rows n = 0..140, flattened

Row sums give: A000312.
Columns k=0-4 give: A000007, A066274(n) = 2*A081131(n) for n>1, A053506(n) for n>2, A055865(n-1) = A085389(n-1) for n>3, A085390(n-1) for n>4.
Main diagonal gives: A028310.
Lower diagonals include (offsets may differ): A002378, A045991, A085537, A085538, A085539.
Cf. A228154, A228617.

T:= (n, k)-> `if`(n=0 and k=0, 1, `if`(k<1 or k>n, 0,
             `if`(k=n, n, (n-1)*n^(n-k)))):
seq(seq(T(n,k), k=0..n), n=0..12);

f[0,0]=1;
f[n_,k_]:=Which[1<=k<=n-1,n^(n-k)*(n-1),k<1,0,k==n,n,k>n,0];
Table[Table[f[n,k],{k,0,n}],{n,0,10}]//Grid (* Geoffrey Critzer, May 19 2014 *)

T(0,0) = 1, else T(n,k) = 0 for k<1 or k>n, else T(n,n) = n, else T(n,k) = (n-1)*n^(n-k).
Sum_{k=0..n}   T(n,k) = A000312(n).
Sum_{k=0..n} k*T(n,k) = A031972(n).

A368849 Triangle read by rows: T(n, k) = binomial(n, k - 1)(k - 1)^(k - 1)(n - k)*(n - k + 1)^(n - k).

Original entry on oeis.org

0, 0, 0, 0, 2, 0, 0, 18, 6, 0, 0, 192, 72, 48, 0, 0, 2500, 960, 720, 540, 0, 0, 38880, 15000, 11520, 9720, 7680, 0, 0, 705894, 272160, 210000, 181440, 161280, 131250, 0, 0, 14680064, 5647152, 4354560, 3780000, 3440640, 3150000, 2612736, 0

Offset: 0

Peter Luschny, Jan 11 2024

A motivation for this triangle was to provide an alternative sum representation for A001864(n) = n! * Sum_{k=0..n-2} n^k/k!. See formula 3 and formula 15 in Riordan and Sloane.

			Triangle starts:
  [0] [0]
  [1] [0,        0]
  [2] [0,        2,       0]
  [3] [0,       18,       6,       0]
  [4] [0,      192,      72,      48,      0]
  [5] [0,     2500,     960,     720,     540,       0]
  [6] [0,    38880,   15000,   11520,    9720,    7680,       0]
  [7] [0,   705894,  272160,  210000,  181440,  161280,  131250,       0]
  [8] [0, 14680064, 5647152, 4354560, 3780000, 3440640, 3150000, 2612736, 0]

John Riordan and N. J. A. Sloane, Enumeration of rooted trees by total height, J. Austral. Math. Soc., vol. 10 pp. 278-282, 1969.

T(n, 1) = A066274(n) for n >= 1.
T(n, 1)/(n - 1) = A000169(n) for n >= 2.
T(n, n - 1) = 2*A081133(n) for n >= 1.
Sum_{k=0..n} T(n, k) = A001864(n).
(Sum_{k=0..n} T(n, k)) / n = A000435(n) for n >= 1.
(Sum_{k=0..n} T(n, k)) * n / 2 = A262973(n) for n >= 1.
(Sum_{k=2..n} T(n, k)) / (2*n) = A057500(n) for n >= 1.
T(n, 1)/(n - 1) + (Sum_{k=2..n} T(n, k)) / (2*n) = A368951(n) for n >= 2.
Sum_{k=0..n} (-1)^(k-1) * T(n, k) = A368981(n).

A368849[n_, k_] := Binomial[n, k-1] If[k == 1, 1, (k-1)^(k-1)] (n-k) (n-k+1)^(n-k);
Table[A368849[n, k], {n, 0, 10}, {k, 0, n}] (* Paolo Xausa, Jan 13 2024 *)

def T(n, k):
    return binomial(n, k - 1)*(k - 1)^(k - 1)*(n - k)*(n - k + 1)^(n - k)
for n in range(0, 9): print([n], [T(n, k) for k in range(n + 1)])

A066275 Number of endofunctions of [n] such that some element is fixed, but 1 is not fixed.

Original entry on oeis.org

0, 1, 10, 111, 1476, 23255, 425958, 8915263, 210156040, 5513215599, 159374246010, 5034663700847, 172583816090700, 6380915666604583, 253132868797656526, 10725414213389814015, 483431164831317069840

Offset: 1

Len Smiley, Dec 09 2001

nonn

			a(2)=1: [1->2,2->2].

Cf. A045531, A066274.

A066275 := proc(n)
    n^n-n^(n-1)-(n-1)^n ;
end proc: # R. J. Mathar, Oct 31 2015

a(n) = n^n-n^(n-1)-(n-1)^n. E.g.f.: (T^3-T^2+T-x)/(T-T^2), where T=T(x) is Euler's tree function (see A000169).

A154715 Triangle interpolating between the subsets of an n-set (A000079) and the trees on n labeled nodes (A000272) (read by rows).

Original entry on oeis.org

1, 2, 3, 4, 18, 16, 8, 81, 192, 125, 16, 324, 1536, 2500, 1296, 32, 1215, 10240, 31250, 38880, 16807, 64, 4374, 61440, 312500, 699840, 705894, 262144, 128, 15309, 344064, 2734375, 9797760, 17294403, 14680064, 4782969

Offset: 0

Peter Luschny, Jan 14 2009

Formatted as a square array:
1st row is A000079(n). Subsets of an n-set.
2nd row is A036290(n+1). Special (n+1)-subsets of a 3n-set partitioned into 3-blocks.
2nd column is A066274(n+1). Endofunctions of [n] such that 1 is not a fixed point.
1st column is A000272(n+2). Trees on n labeled nodes (Cayley's formula).
Alternating sum of rows in the triangle, Sum_{k=0..n} (-1)^(n-k) * T(n,k) = n! = A000142(n).
This triangle gives the coefficient of Sidi's polynomials D_{n,2,n}(-z)/(-z), for n >= 0. See [Sidi 1980]. - Wolfdieter Lang, Oct 27 2022

			Triangle begins as:
   1;
   2,    3;
   4,   18,    16;
   8,   81,   192,    125;
  16,  324,  1536,   2500,   1296;
  32, 1215, 10240,  31250,  38880,  16807;
  64, 4374, 61440, 312500, 699840, 705894, 262144;

G. C. Greubel, Rows n = 0..100 of triangle, flattened
Harlan J. Brothers, Pascal's triangle, Sidi polynomials, and powers of e, Missouri J. Math. Sci. (2025) Vol. 37, No. 1, 67-78.
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Avram Sidi, Numerical Quadrature and Nonlinear Sequence Transformations; Unified Rules for Efficient Computation of Integrals with Algebraic and Logarithmic Endpoint Singularities, Math. Comp., 35 (1980), 851-874. Eq. (4.10), p. 862.

Cf. A000079, A000272, A036290, A066274, A075513.

Flat(List([0..12], n-> List([0..n], k-> Binomial(n,k)*(k+2)^n ))); # G. C. Greubel, May 09 2019

[[Binomial(n,k)*(k+2)^n: k in [0..n]]: n in [0..12]]; // G. C. Greubel, May 09 2019

T := proc(n,k) binomial(n,k)*(k+2)^n end;

Table[Binomial[n, k]*(k+2)^n, {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, May 09 2019 *)

{T(n, k) = binomial(n,k)*(k+2)^n}; \\ G. C. Greubel, May 09 2019

[[binomial(n,k)*(k+2)^n for k in (0..n)] for n in (0..12)] # G. C. Greubel, May 09 2019

T(n,k) = binomial(n,k)*(k+2)^n, where n >= 0, and k >= 0.
From Wolfdieter Lang, Oct 20 2022: (Start)
O.g.f. of column k: (-x)^k*(k + 2)^k/(1 - (k + 2)*x)^(k+1), for k >= 0. See |A075513| with offset 0.
E.g.f. of column k: exp((k+2)*x)*((k+2)*x)^k/k!, for k >= 0. (End)
E.g.f. of triangle (of row polynomials in y): exp(2*x)*substitute(z = x*y*exp(x), LambertW(-z)^2/(-z)*2*(1 + LambertW(-z)))). - Wolfdieter Lang, Oct 24 2022

A229078 Number of ascending runs in {1,...,n}^n.

Original entry on oeis.org

0, 1, 7, 63, 736, 10625, 182736, 3647119, 82837504, 2109289329, 59500000000, 1841557146671, 62041198952448, 2259914256880657, 88499197217837056, 3707501605224609375, 165444235911082541056, 7834451891982365825441, 392371124973096027488256

Offset: 0

Alois P. Heinz, Sep 12 2013

nonn

			a(1) = 1: [1].
a(2) = 7 = 2+2+1+2: [1,1], [2,1], [1,2], [2,2].

Alois P. Heinz, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Lambert W-Function
Wikipedia, Lambert W function

Main diagonal of A229079.

Cf. A062023 (nondescending runs), A066274.

a:= n-> `if`(n=0, 0, n^(n-1)*(n*(n+2)-1)/2):
seq(a(n), n=0..25);

a(n) = n^(n-1)*(n*(n+2)-1)/2 for n>0, a(0) = 0.
E.g.f.: 1/2*W(-x)*(W(-x)^3+W(-x)^2-W(-x)-2)/(1+W(-x))^3, W(x) Lambert's function (principal branch).
a(n) = A062023(n) + A066274(n) for n>0.

A134574 Array, a(n,k) = total size of all n-length words on a k-letter alphabet, read by antidiagonals.

Original entry on oeis.org

1, 2, 2, 3, 8, 3, 4, 24, 18, 4, 5, 64, 81, 32, 5, 6, 160, 324, 192, 50, 6, 7, 384, 1215, 1024, 375, 72, 7, 8, 896, 4374, 5120, 2500, 648, 98, 8, 9, 2048, 15309, 24576, 15625, 5184, 1029, 128, 9, 10, 4608, 52488, 114688, 93750, 38880, 9604, 1536, 162, 10

Offset: 1

Ross La Haye, Jan 22 2008

			a(2,2) = 8 because there are 2^2 = 4 2-length words on a 2 letter alphabet, each of size 2 and 2*4 = 8.
Array begins:
==================================================================
n\k|  1     2       3        4         5         6          7  ...
---|--------------------------------------------------------------
1  |  1     2       3        4         5         6          7  ...
2  |  2     8      18       32        50        72         98  ...
3  |  3    24      81      192       375       648       1029  ...
4  |  4    64     324     1024      2500      5184       9604  ...
5  |  5   160    1215     5120     15625     38880      84035  ...
6  |  6   384    4374    24576     93750    279936     705894  ...
7  |  7   896   15309   114688    546875   1959552    5764801  ...
8  |  8  2048   52488   524288   3125000  13436928   46118408  ...
9  |  9  4608  177147  2359296  17578125  90699264  363182463  ...
... - _Franck Maminirina Ramaharo_, Aug 07 2018

Cf. a(n, 1) = a(1, k) = A000027(n); a(n, 2) = A036289(n); a(n, 3) = A036290(n); a(n, 4) = A018215(n); a(n, 5) = A036291(n); a(n, 6) = A036292(n); a(n, 7) = A036293(n); a(n, 8) = A036294(n); a(2, k) = A001105(k); a(3, k) = A117642(k); a(n, n) = A007778(n); a(n, n+1) = A066274(n+1): sum[a(i-1, n-i+1), {i, 1, n}] = A062807(n).

t[n_, k_] := Sum[k^n, {j, n}]; Table[ t[n - k + 1, k], {n, 10}, {k, n}] // Flatten (* Robert G. Wilson v, Aug 07 2018 *)

a(n,k) = n*k^n.
O.g.f. (by columns): (k*x)/(-1+k*x)^2.
E.g.f. (by columns): k*x*exp(k*x).
a(n,k) = Sum[k^n,{j,1,n}] = n*Sum[C(n,m)*(k-1)^m,{m,0,n}]. - Ross La Haye, Jan 26 2008

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

A228273 T(n,k) is the number of s in {1,...,n}^n having longest ending contiguous subsequence with the same value of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A368849 Triangle read by rows: T(n, k) = binomial(n, k - 1)*(k - 1)^(k - 1)*(n - k)*(n - k + 1)^(n - k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

SageMath

A066275 Number of endofunctions of [n] such that some element is fixed, but 1 is not fixed.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Formula

A154715 Triangle interpolating between the subsets of an n-set (A000079) and the trees on n labeled nodes (A000272) (read by rows).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A229078 Number of ascending runs in {1,...,n}^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A134574 Array, a(n,k) = total size of all n-length words on a k-letter alphabet, read by antidiagonals.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A368849 Triangle read by rows: T(n, k) = binomial(n, k - 1)(k - 1)^(k - 1)(n - k)*(n - k + 1)^(n - k).