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 *)
A209327
Total number of nodes in the largest connected component of a functional digraph summed over all endofunctions f:{1,2,...,n}-> {1,2,...,n}.
Original entry on oeis.org
1, 7, 70, 863, 13056, 231187, 4737986, 109531991, 2835638008, 80950287311, 2533758258912, 86089196479255, 3161596017956936, 124590870125959343, 5251666647713483356, 235497961945975068767, 11205025852314462333408, 563351626162952600815087, 29864689571162209608920060, 1663796497123214306448307031
Offset: 1
- R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Welsey, 1996, Chapter 8.
-
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, max(m, i))*binomial(n-1, i-1), i=1..n))
end:
a:= n-> (p-> add(coeff(p, x, i)*i, i=1..n))(b(n, 0)):
seq(a(n), n=1..20); # Alois P. Heinz, Dec 17 2021
-
nn=20;g[list_]:= Sum[list[[i]]*i,{i,1,Length[list]}];t=Sum[n^(n-1)x^n/n!,{n,1,nn}];c=Log[1/(1-t)];b=Drop[Range[0,nn]!CoefficientList[Series[c,{x,0,nn}],x],1];f[list_]:=Select[list,#>0&];Map[g,Map[ f,Drop[Transpose[Table[Range[0,nn]!CoefficientList[Series[ Exp[Sum[b[[i]]x^i/i!,{i,1,n+1}]]-Exp[Sum[b[[i]]x^i/i!,{i,1,n}]],{x,0,nn}],x],{n,0,nn-1}]],1]]]
A350202
Number T(n,k) of nodes in the k-th connected component of all endofunctions on [n] when components are ordered by increasing size; triangle T(n,k), n>=1, 1<=k<=n, read by rows.
Original entry on oeis.org
1, 7, 1, 61, 19, 1, 709, 277, 37, 1, 9911, 4841, 811, 61, 1, 167111, 91151, 19706, 1876, 91, 1, 3237921, 1976570, 486214, 60229, 3739, 127, 1, 71850913, 47203241, 13110749, 1892997, 152937, 6721, 169, 1, 1780353439, 1257567127, 380291461, 62248939, 5971291, 340729, 11197, 217, 1
Offset: 1
Triangle T(n,k) begins:
1;
7, 1;
61, 19, 1;
709, 277, 37, 1;
9911, 4841, 811, 61, 1;
167111, 91151, 19706, 1876, 91, 1;
3237921, 1976570, 486214, 60229, 3739, 127, 1;
71850913, 47203241, 13110749, 1892997, 152937, 6721, 169, 1;
...
-
g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
b:= proc(n, i, t) option remember; `if`(n=0, [1, 0], `if`(i>n, 0,
add((p-> p+`if`(t>0 and t-j<1, [0, p[1]*i], 0))(g(i)^j*
b(n-i*j, i+1, max(0, t-j))/j!*combinat[multinomial]
(n, i$j, n-i*j)), j=0..n/i)))
end:
T:= (n, k)-> b(n, 1, k)[2]:
seq(seq(T(n, k), k=1..n), n=1..10);
-
multinomial[n_, k_List] := n!/Times @@ (k!);
g[n_] := g[n] = Sum[n^(n - j)*(n - 1)!/(n - j)!, {j, 1, n}];
b[n_, i_, t_] := b[n, i, t] = If[n == 0, {1, 0}, If[i > n, {0, 0}, Sum[ Function[p, p + If[t > 0 && t - j < 1, {0, p[[1]]*i}, {0, 0}]][g[i]^j*b[n - i*j, i + 1, Max[0, t - j]]/j!*multinomial[n, Append[Table[i, {j}], n - i*j]]], {j, 0, n/i}]]];
T[n_, k_] := b[n, 1, k][[2]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Mar 18 2022, after Alois P. Heinz *)
Showing 1-3 of 3 results.
Comments