A045531 -id:A045531 - cp's OEIS frontend

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

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

A085529 a(n) = (2n+1)^(2n+1).

Original entry on oeis.org

1, 27, 3125, 823543, 387420489, 285311670611, 302875106592253, 437893890380859375, 827240261886336764177, 1978419655660313589123979, 5842587018385982521381124421, 20880467999847912034355032910567, 88817841970012523233890533447265625, 443426488243037769948249630619149892803

Offset: 0

N. J. A. Sloane, Jul 05 2003

nonn

a(n) == 2*n + 1 (mod 24). - Mathew Englander, Aug 16 2020

Cf. A000312, A005408, A016754, A085527, A085528, A085530, A085531, A085532, A085533, A085534, A085535.

Cf. A073009, A083648.

#^#&/@Range[1,31,2] (* Harvey P. Dale, Oct 05 2019 *)

From Mathew Englander, Aug 16 2020: (Start)
a(n) = A000312(2*n + 1).
a(n) = A016754(n)^n * (2*n + 1).
a(n) = A085527(n)^2 * (2*n + 1).
a(n) = A085528(n)^2 / (2*n + 1).
a(n) = A085530(n) * A005408(n).
a(n) = A085531(n) * A016754(n).
a(n) = A085532(n)^2 - A215265(2*n + 1).
a(n) = A085533(n) + A045531(2*n + 1).
a(n) = A085534(n+1) - A007781(2*n + 1).
a(n) = A085535(n+1) - A055869(2*n + 1).
(End)
Sum_{n>=0} 1/a(n) = (A073009 + A083648)/2 = 1.0373582538... . - Amiram Eldar, May 17 2022

A174551 Triangular array T(n,k): functions f:{1,2,...,n}-> {1,2,...,n} such that each of k fixed (but arbitrary) elements are in the image of f.

Original entry on oeis.org

1, 1, 1, 4, 3, 2, 27, 19, 12, 6, 256, 175, 110, 60, 24, 3125, 2101, 1320, 750, 360, 120, 46656, 31031, 19502, 11340, 5880, 2520, 720, 823543, 543607, 341796, 201726, 109200, 52080, 20160, 5040, 16777216, 11012415, 6927230, 4131036, 2298744, 1164240, 514080, 181440, 40320

Offset: 0

Geoffrey Critzer, Mar 22 2010

			Letting the k arbitrary elements be {1,2}, T(3,2) = 12 because there are 12 such functions from [3] into [3]. {1, 1, 2}, {1, 2, 1}, {1, 2, 2}, {1, 2, 3}, {1, 3, 2}, {2, 1, 1}, {2,1, 2}, {2, 1, 3}, {2, 2, 1}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}.
The triangle begins:
1;
1, 1;
4, 3, 2;
27, 19, 12, 6;
256, 175, 110, 60, 24;
3125, 2101, 1320, 750, 360, 120;
46656, 31031, 19502, 11340, 5880, 2520, 720;
823543, 543607, 341796, 201726, 109200, 52080, 20160, 5040;

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

Columns are: A045531, A126778, A126779, A126780, A126232, A126781

T:= (n,k)-> add((-1)^i*binomial(k, i)*(n-i)^n, i=0..k):
seq(seq(T(n,k), k=0..n), n=0..10);  # Alois P. Heinz, Dec 26 2012

Table[Table[ Sum[(-1)^i Binomial[k, i] (n - i)^n, {i, 0, k}], {k, 0, n}], {n, 0, 7}] // Grid

T(n,k) = Sum_{i=0..k} (-1)^i C(k,i) (n-i)^n; T(n,0) = n^n; T(n,n) = n!.

A281595 a(n) = (n^n - 3(n-1)^n + 3(n-2)^n - (n-3)^n)/6.

Original entry on oeis.org

0, 0, 0, 1, 10, 125, 1890, 33621, 688506, 15958405, 413066170, 11810819141, 369730963602, 12577271147805, 461980538087250, 18223376862518101, 768327068469302218, 34480595937671194805, 1641060381277816308810, 82562177153973368528901, 4378026144983797903473954

Offset: 0

Peter Luschny, Jan 26 2017

nonn

Paolo Xausa, Table of n, a(n) for n = 0..380

Cf. A000312, A045531, A281596.

a := n -> (n^n-3*(n-1)^n+3*(n-2)^n-(n-3)^n)/6:
seq(a(n), n=0..20);

A281595[n_] := If[n == 0, 0, (n^n - 3*(n-1)^n + 3*(n-2)^n - (n-3)^n)/6];
Array[A281595, 25, 0] (* Paolo Xausa, Jul 10 2024 *)

A343237 Triangle T obtained from the array A(n, k) = (k+1)^(n+1) - k^(n+1), n, k >= 0, by reading antidiagonals upwards.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 5, 1, 1, 15, 19, 7, 1, 1, 31, 65, 37, 9, 1, 1, 63, 211, 175, 61, 11, 1, 1, 127, 665, 781, 369, 91, 13, 1, 1, 255, 2059, 3367, 2101, 671, 127, 15, 1, 1, 511, 6305, 14197, 11529, 4651, 1105, 169, 17, 1

Offset: 0

Wolfdieter Lang, May 10 2021

This is the row reversed version of the triangle A047969(n, m). The corresponding array A047969 is a(n, k) = A(k, n) (transposed of array A).

A(n-1, k-1) = k^n - (k-1)^n gives the number of n-digit numbers with digits from K = {1, 2, 3, ..., k} such that any digit from K, say k, appears at least once. Motivated by a comment in A005061 by Enrique Navarrete, the instance k=4 for n >= 1 (the column 3 in array A), and the d = 3 (sub)-diagonal sequence of T for m >= 0.

			The array A begins:
n\k  0  1   2    3     4     5     6      7      8      9 ...
-------------------------------------------------------------
0:   1  1   1    1     1     1     1      1      1      1 ...
1:   1  3   5    7     9    11    13     15     17     19 ...
2:   1  7  19   37    61    91   127    169    217    271 ...
3:   1 15  65  175   369   671  1105   1695   2465   3439 ...
4:   1 31 211  781  2101  4651  9031  15961  26281  40951 ...
5:   1 63 665 3367 11529 31031 70993 144495 269297 468559 ...
...
The triangle T begins:
n\m   0    1     2     3     4     5    6    7   8  9 10 ...
-------------------------------------------------------------
0:    1
1:    1    1
2:    1    3     1
3:    1    7     5     1
4:    1   15    19     7     1
5:    1   31    65    37     9     1
6:    1   63   211   175    61    11    1
7:    1  127   665   781   369    91   13    1
8:    1  255  2059  3367  2101   671  127   15   1
9:    1  511  6305 14197 11529  4651 1105  169  17  1
10:   1 1023 19171 58975 61741 31031 9031 1695 217 19  1
...
Combinatorial interpretation (cf. A005061 by _Enrique Navarrete_)
The three digits numbers with digits from K ={1, 2, 3, 4} having at least one 4 are:
j=1 (one 4): 114, 141, 411; 224, 242, 422; 334, 343, 433; 124, 214, 142, 241, 412, 421; 134, 314, 143, 341, 413, 431; 234, 243, 423. That is,  3*3 + 3!*3 = 27 = binomial(3, 1)*(4-1)^(3-1) = 3*3^2;
j=2 (twice 4):  144, 414, 441;  244, 424, 442;  344, 434, 443; 3*3 = 9 = binomial(3, 2)*(4-1)^(3-2) = 3*3;
j=3 (thrice 4) 444; 1 = binomial(3, 3)*(4-1)^(3-3).
Together: 27 + 9 + 1 = 37 = A(2, 3) = T(5, 3).

Cf. A005061, A008292, A047969 (reversed), A045531 (central diagonal), A047970 (row sums of triangle).
Row sequences of array A (nexus numbers): A000012, A005408, A003215, A005917(k+1), A022521, A022522, A022523, A022524, A022525, A022526, A022527, A022528.
Column sequences of array A: A000012, A000225(n+1), A001047(n+1), A005061(n+1), A005060(n+1), A005062(n+1), A016169(n+1), A016177(n+1), A016185(n+1), A016189(n+1), A016195(n+1), A016197(n+1).

egf := exp(exp(x)*y + x)*(exp(x)*y - y + 1): ser := series(egf, x, 12):
cx := n -> series(n!*coeff(ser, x, n), y, 12):
Arow := n -> seq(k!*coeff(cx(n), y, k), k=0..9):
for n from 0 to 5 do Arow(n) od; # Peter Luschny, May 10 2021

A[n_, k_] := (k + 1)^(n + 1) - k^(n + 1); Table[A[n - k, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Amiram Eldar, May 10 2021 *)

Array A(n, k) = (k+1)^(n+1) - k^(n+1), n, k >= 0.
A(n-1, k-1) = Sum_{j=1} binomial(n, j)*(k-1)^(n-j) = Sum_{j=0} binomial(n, j)*(k-1)^(n-j) - (k-1)^n = (1+(k-1))^n - (k-1)^n = k^n - (k-1)^n (from the combinatorial comment on A(n-1, k-1) above).
O.g.f. row n of array A: RA(n, x) = P(n, x)/(1 - x)^n, with P(n, x) = Sum_{m=0..n} A008292(n+1, m+1)*x^m, (the Eulerian number triangle  A008292 has offset 1) for n >= 0. (See the Oct 26 2008 comment in A047969 by Peter Bala). RA(n, x) = polylog(-(n+1), x)*(1-x)/x. (For P(n, x) see the formula by Vladeta Jovovic, Sep 02 2002.)
E.g.f. of e.g.f.s of the rows of array A: EE(x, y) = exp(x)*(1 + y*(exp(x) - 1))*exp(y*exp(x)), that is A(n, k) = [y^k/k!][x^n/n!] EE(x, y).
Triangle T(n, m) = A(n-m, m) = (m+1)^(n-m+1) - m^(n-m+1), n >= 0, m = 0, 1, ..., n.
E.g.f.: -(exp(x)-1)/(x*exp(x)*y-x). - Vladimir Kruchinin, Nov 02 2022

A350454 Number T(n,k) of endofunctions on [n] with exactly k fixed points, none of which are isolated; triangle T(n,k), n >= 0, 0 <= k <= n/2, read by rows.

Original entry on oeis.org

1, 0, 1, 2, 8, 9, 81, 76, 12, 1024, 875, 180, 15625, 12606, 2910, 120, 279936, 217217, 53550, 3780, 5764801, 4348856, 1118936, 102480, 1680, 134217728, 99111735, 26280072, 2817360, 90720, 3486784401, 2532027610, 686569050, 81864720, 3729600, 30240

Offset: 0

Alois P. Heinz, Dec 31 2021

			Triangle T(n,k) begins:
           1;
           0;
           1,          2;
           8,          9;
          81,         76,        12;
        1024,        875,       180;
       15625,      12606,      2910,      120;
      279936,     217217,     53550,     3780;
     5764801,    4348856,   1118936,   102480,    1680;
   134217728,   99111735,  26280072,  2817360,   90720;
  3486784401, 2532027610, 686569050, 81864720, 3729600, 30240;
  ...

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

Column k=0 gives A065440.
Row sums give |A069856|.
T(2n,n) gives A001813.
Cf. A349454.

c:= proc(n) option remember; add(n!*n^(n-k-1)/(n-k)!, k=2..n) end:
t:= proc(n) option remember; n^(n-1) end:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(b(n-i)*
      binomial(n-1, i-1)*(c(i)+`if`(i=1, 0, x*t(i))), i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n/2))(b(n)):
seq(T(n), n=0..12);
# second Maple program:
egf := k-> exp(LambertW(-x))*(-x-LambertW(-x))^k/((1+LambertW(-x))*k!):
A350454 := (n, k)-> n! * coeff(series(egf(k), x, n+1), x, n):
seq(print(seq(A350454(n, k), k=0..n/2)), n=0..9); # Mélika Tebni, Nov 22 2022

c[n_] := c[n] = Sum[n!*n^(n - k - 1)/(n - k)!, {k, 2, n}];
t[n_] := t[n] = n^(n - 1);
b[n_] := b[n] = Expand[If[n == 0, 1, Sum[b[n - i]*
     Binomial[n - 1, i - 1]*(c[i] + If[i == 1, 0, x*t[i]]), {i, 1, n}]]];
T[n_] := With[{p = b[n]}, Table[Coefficient[p, x, i], {i, 0, n/2}]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, May 06 2022, after Alois P. Heinz *)

E.g.f. column k: exp(W(-x))*(-x - W(-x))^k / ((1 + W(-x))*k!), W(x) the Lambert W-function. - Mélika Tebni, Nov 22 2022
From Mélika Tebni, Dec 22 2022: (Start)
For n > 1, T(n,1) = n*A045531(n-1).
Sum_{k=0..n} (-1)^(n-k)*T(n+k,k) = 2^n.
Sum_{k=0..n} (-1)^(n-k)*T(n+k,k)/(n+k-1) = 1/n, for n > 1. (End)

A048743 Triangle a(n,k) = k!C(n-1,k-1)Stirling_2(n,k), 1<=k<=n.

Original entry on oeis.org

1, 1, 2, 1, 12, 6, 1, 42, 108, 24, 1, 120, 900, 960, 120, 1, 310, 5400, 15600, 9000, 720, 1, 756, 27090, 168000, 252000, 90720, 5040, 1, 1778, 121716, 1428840, 4410000, 4021920, 987840, 40320, 1, 4080, 508200, 10442880, 58388400, 106686720

Offset: 1

Alford Arnold

			The 3rd row is formed from [ 1,2,6,24 ]*[ 1,3,3,1 ]*[ 1,7,6,1 ] => [ 1,42,108,24 ].
1;
1,2;
1,12,6;
1,42,108,24;
1,120,900,960,120;

Cf. A007318, A008277. Row sums give A045531.

A048743 := proc(n,k) k!*binomial(n-1,k-1)*combinat[stirling2](n,k) ; end proc:
seq(seq(A048743(n,k),k=1..n),n=1..12) ; # R. J. Mathar, Aug 30 2011

Flatten[Table[k!Binomial[n-1,k-1]StirlingS2[n,k],{n,10},{k,n}]] (* Harvey P. Dale, Feb 21 2013 *)

More terms from James Sellers, Apr 22 2000

A091884 Triangle of numbers defined by Knuth.

Original entry on oeis.org

1, 1, 1, 4, 3, 3, 27, 19, 20, 20, 256, 175, 191, 190, 190, 3125, 2101, 2344, 2312, 2313, 2313, 46656, 31031, 35127, 34398, 34462, 34461, 34461, 823543, 543607, 621732, 605348, 607535, 607407, 607408, 607408, 16777216, 11012415, 12692031, 12301406, 12366942, 12360381, 12360637, 12360636, 12360636

Offset: 0

Michael Somos, Feb 08 2004

			Triangle begins:
     1;
     1,    1;
     4,    3,    3;
    27,   19,   20,   20;
   256,  175,  191,  190,  190;
  3125, 2101, 2344, 2312, 2313, 2313;
  ...

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 6.4 Answer to Exer. 46.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.

Seiichi Manyama, Rows n = 0..139, flattened

Column k=0..1 give A000312, A045531.

Main diagonal gives A120485.

T(n,k)=if(k<0 || k>n,0,sum(j=0,k,(-1)^j*(n-j)^n))

T(n,k) = Sum_{j=0..k} (-1)^j * (n-j)^n.

A085283 a(n) = nn^n - (n-1)(n-1)^n.

Original entry on oeis.org

1, 1, 7, 65, 781, 11529, 201811, 4085185, 93864121, 2413042577, 68618940391, 2138428376721, 72470493235141, 2653457921150425, 104382202543721467, 4390455017903519489, 196621779843659466481, 9340717969198079777313

Offset: 0

Paul Barry, Jun 26 2003

The system of equations
x(0) = n*x(1) + 1,
(n-1)*x(1) = n*x(2) + 1,
...
(n-1)*x(n) = n*x(n+1) + 1.
relates to the Monkey-And-Coconuts problem and reduces to the single equation
A007778(n-1)*x(0) = A007778(n)*x(n+1) + a(n),
whose solutions {x(0),x(n+1)} are given by {A014293(n), A085606(n)=A007778(n-1) - 1}. - Lekraj Beedassy, Jul 15 2003
For n >= 1, a(n) is equal to the number of functions f: {1,2,...,n+1}->{1,2,...,n} such that Im(f) contains a fixed element. - Aleksandar M. Janjic and Milan Janjic, Feb 27 2007

Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
BBC, The Monkey and the Coconuts
K. Belcourt, How Many Coconuts
Santo D'Agostino, "The Coconut Problem"; Updated With Solution, May 2011.
J. Dean, Sailors, monkey and coconuts
A. K. Dewdney, The Monkey and the Coconuts
G. Lewandrowski, The Monkey Problem
R. Raja, Monkeys and Coconuts
A. Rishi, Nemo's sailors and the monkey
Dr. Rob, The MathForum, Coconut piles
D. J. Wright, Five Pirates and a Monkey

Cf. A045531, A055869.

Join[{1},Table[n*n^n-(n-1)(n-1)^n,{n,20}]] (* Harvey P. Dale, Sep 08 2016 *)

E.g.f.: -(x + 2*x*W(-x) + W(-x)^2)/(W(-x)*(1 + W(-x))^3), where W(x) is the Lambert W function. - Fabian Pereyra, Sep 26 2023

A348154 Number of inequivalent strip arrangements.

Original entry on oeis.org

1, 3, 11, 100, 1063, 15686, 271975, 5509456, 126604661, 3256687324, 92655915831, 2888838414540, 97940953019995, 3587315304010374, 141162897496953263, 5939167862427259456, 266046178356979847881, 12641661811772879875640, 635092155152649300232063, 33633813271235206436451100

Offset: 1

Joseph Rozhenko, Oct 04 2021

nonn

Given n strips, each of length n squares (dimensions 1 X n), a(n) is the number of distinct shapes that can be created by setting the strips side by side while satisfying the condition that the shape must include at least one row of length L=n squares (row considered to be a direction measured perpendicular to the strips). Shapes differing only by a rotation are considered to be equivalent.

Joseph Rozhenko, Illustration of a(3) = 11

Cf. A045531 (when rotations are considered distinct).

a(n) = (n^n - (n-1)^n + n^(n\2) + !(n%2)*(n-1)^(n\2))/2; \\ Jinyuan Wang, Oct 08 2021

From Jinyuan Wang, Oct 08 2021: (Start)
a(2*k+1) = ((2*k+1)^(2*k+1) - (2*k)^(2*k+1) + (2*k+1)^k) / 2.
a(2*k) = ((2*k)^(2*k) - (2*k-1)^(2*k) + (2*k)^k + (2*k-1)^k) / 2.
(End)

More terms from Jinyuan Wang, Oct 08 2021

cp's OEIS Frontend

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

A085529 a(n) = (2n+1)^(2n+1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A174551 Triangular array T(n,k): functions f:{1,2,...,n}-> {1,2,...,n} such that each of k fixed (but arbitrary) elements are in the image of f.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A281595 a(n) = (n^n - 3*(n-1)^n + 3*(n-2)^n - (n-3)^n)/6.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A343237 Triangle T obtained from the array A(n, k) = (k+1)^(n+1) - k^(n+1), n, k >= 0, by reading antidiagonals upwards.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A350454 Number T(n,k) of endofunctions on [n] with exactly k fixed points, none of which are isolated; triangle T(n,k), n >= 0, 0 <= k <= n/2, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A048743 Triangle a(n,k) = k!*C(n-1,k-1)*Stirling_2(n,k), 1<=k<=n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A091884 Triangle of numbers defined by Knuth.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

A281595 a(n) = (n^n - 3(n-1)^n + 3(n-2)^n - (n-3)^n)/6.

A048743 Triangle a(n,k) = k!C(n-1,k-1)Stirling_2(n,k), 1<=k<=n.

A085283 a(n) = nn^n - (n-1)(n-1)^n.