A347999
Triangular array read by rows: T(n,k) is the number of endofunctions f:{1,2,...,n}-> {1,2,...,n} whose smallest connected component has exactly k nodes; n >= 0, 0 <= k <= n.
Original entry on oeis.org
1, 0, 1, 0, 1, 3, 0, 10, 0, 17, 0, 87, 27, 0, 142, 0, 1046, 510, 0, 0, 1569, 0, 15395, 6795, 2890, 0, 0, 21576, 0, 269060, 114912, 84490, 0, 0, 0, 355081, 0, 5440463, 2332029, 1493688, 705740, 0, 0, 0, 6805296, 0, 124902874, 53389746, 32186168, 28072548, 0, 0, 0, 0, 148869153
Offset: 0
Triangle begins:
1;
0, 1;
0, 1, 3;
0, 10, 0, 17;
0, 87, 27, 0, 142;
0, 1046, 510, 0, 0, 1569;
0, 15395, 6795, 2890, 0, 0, 21576;
0, 269060, 114912, 84490, 0, 0, 0, 355081;
0, 5440463, 2332029, 1493688, 705740, 0, 0, 0, 6805296;
...
- R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, Chapter 8.
- Alois P. Heinz, Rows n = 0..140, flattened
- Steven Finch, Permute, Graph, Map, Derange, arXiv:2111.05720 [math.CO], 2021.
- D. Panario and B. Richmond, Exact largest and smallest size of components, Algorithmica, 31 (2001), 413-432.
-
g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
b:= proc(n, m) option remember; `if`(n=0, x^m, add(g(i)*
b(n-i, min(m, i))*binomial(n-1, i-1), i=1..n))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$2)):
seq(T(n), n=0..12); # Alois P. Heinz, Dec 16 2021
-
g[n_] := g[n] = Sum[n^(n - j)*(n - 1)!/(n - j)!, {j, 1, n}];
b[n_, m_] := b[n, m] = If[n == 0, x^m, Sum[g[i]*b[n - i, Min[m, i]]* Binomial[n - 1, i - 1], {i, 1, n}]];
T[n_] := With[{p = b[n, n]}, Table[Coefficient[p, x, i], {i, 0, n}]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 28 2021, after Alois P. Heinz *)
A350212
Number T(n,k) of endofunctions on [n] with exactly k isolated fixed points; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.
Original entry on oeis.org
1, 0, 1, 3, 0, 1, 17, 9, 0, 1, 169, 68, 18, 0, 1, 2079, 845, 170, 30, 0, 1, 31261, 12474, 2535, 340, 45, 0, 1, 554483, 218827, 43659, 5915, 595, 63, 0, 1, 11336753, 4435864, 875308, 116424, 11830, 952, 84, 0, 1, 262517615, 102030777, 19961388, 2625924, 261954, 21294, 1428, 108, 0, 1
Offset: 0
T(3,1) = 9: 122, 133, 132, 121, 323, 321, 113, 223, 213.
Triangle T(n,k) begins:
1;
0, 1;
3, 0, 1;
17, 9, 0, 1;
169, 68, 18, 0, 1;
2079, 845, 170, 30, 0, 1;
31261, 12474, 2535, 340, 45, 0, 1;
554483, 218827, 43659, 5915, 595, 63, 0, 1;
11336753, 4435864, 875308, 116424, 11830, 952, 84, 0, 1;
...
-
g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
b:= proc(n, m) option remember; `if`(n=0, x^m, add(g(i)*
b(n-i, m+`if`(i=1, 1, 0))*binomial(n-1, i-1), i=1..n))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..10);
# second Maple program:
A350212 := (n,k)-> add((-1)^(j-k)*binomial(j,k)*binomial(n,j)*(n-j)^(n-j), j=0..n):
seq(print(seq(A350212(n, k), k=0..n)), n=0..9); # Mélika Tebni, Nov 24 2022
-
g[n_] := g[n] = Sum[n^(n - j)*(n - 1)!/(n - j)!, {j, 1, n}];
b[n_, m_] := b[n, m] = If[n == 0, x^m, Sum[g[i]*
b[n - i, m + If[i == 1, 1, 0]]*Binomial[n - 1, i - 1], {i, 1, n}]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 0]];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Mar 11 2022, after Alois P. Heinz *)
A204042
The number of functions f:{1,2,...,n}->{1,2,...,n} (endofunctions) such that all of the fixed points in f are isolated.
Original entry on oeis.org
1, 1, 2, 12, 120, 1520, 23160, 413952, 8505280, 197631072, 5125527360, 146787894440, 4601174623584, 156693888150384, 5761055539858528, 227438694372072120, 9596077520725211520, 430920897407809702208, 20520683482765477749120, 1032920864149903149579336, 54797532208320308334631840
Offset: 0
a(2)=2 because there are two functions f:{1,2}->{1,2} in which all the fixed points are isolated: 1->1,2->2 and 1->2,2->1 (which has no fixed points).
-
a:= n-> add((j-1)^j*binomial(n, j), j=0..n):
seq(a(n), n=0..20); # Alois P. Heinz, Dec 16 2021
-
t = Sum[n^(n-1) x^n/n!, {n,1,20}]; Range[0,20]! CoefficientList[Series[Exp[x] Exp[Log[1/(1-t)]-t], {x,0,20}], x]
Showing 1-3 of 3 results.
Comments