A209327 -id:A209327

Search: a209327 -id:a209327

Displaying 1-2 of 2 results found.

page 1

A209324

Triangular array read by rows: T(n,k) is the number of endofunctions f:{1,2,...,n}-> {1,2,...,n} whose largest component has exactly k nodes; n>=1, 1<=k<=n.

+10
4

1, 1, 3, 1, 9, 17, 1, 45, 68, 142, 1, 165, 680, 710, 1569, 1, 855, 6290, 8520, 9414, 21576, 1, 3843, 47600, 134190, 131796, 151032, 355081, 1, 21819, 481712, 1838900, 2372328, 2416512, 2840648, 6805296, 1, 114075, 5025608, 21488292, 50609664, 48934368, 51131664, 61247664, 148869153

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

Here component means weakly connected component in the functional digraph of f.

Row sums are n^n.

T(n,n) = A001865.

For the statistic "length of the smallest component", see A347999.

REFERENCES

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, Chapter 8.

LINKS

Alois P. Heinz, Rows n = 1..141, 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.

FORMULA

E.g.f. for column k: exp( Sum_{n=1..k} A001865(n) x^n/n!) - exp( Sum_{n=1..k-1} A001865(n) x^n/n!).

Sum_{k=1..n} k * T(n,k) = A209327(n). - Alois P. Heinz, Dec 16 2021

EXAMPLE

Triangle T(n,k) begins:

1, 3;

1, 9, 17;

1, 45, 68, 142;

1, 165, 680, 710, 1569;

1, 855, 6290, 8520, 9414, 21576;

1, 3843, 47600, 134190, 131796, 151032, 355081;

1, 21819, 481712, 1838900, 2372328, 2416512, 2840648, 6805296;

...

MAPLE

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:

T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0)):

seq(T(n), n=1..12); # Alois P. Heinz, Dec 16 2021

MATHEMATICA

nn=8; 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[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]]//Grid

(* Second program: *)

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, Max[m, i]]* Binomial[n - 1, i - 1], {i, 1, n}]];

T[n_] := With[{p = b[n, 0]}, Table[Coefficient[p, x, i], {i, 1, n}]];

Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Dec 30 2021, after Alois P. Heinz *)

CROSSREFS

Main diagonal gives A001865.

Row sums give A000312.

Cf. A209327, A347999.

KEYWORD

nonn,tabl

AUTHOR

Geoffrey Critzer, Jan 19 2013

STATUS

approved

A350157

Total number of nodes in the smallest connected component summed over all endofunctions on [n].

+10
4

0, 1, 7, 61, 709, 9911, 167111, 3237921, 71850913, 1780353439, 49100614399, 1482061739423, 48873720208853, 1740252983702871, 66793644836081827, 2740470162691675711, 120029057782404141841, 5575505641199441262767, 274412698693082818767335, 14236421024010426118259883

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

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

FORMULA

a(n) = Sum_{k=1..n} k * A347999(n,k).

EXAMPLE

a(2) = 7 = 2 + 2 + 1 + 2: 11, 22, 12, 21.

MAPLE

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(

b(n-i, min(m, i))*g(i)*binomial(n-1, i-1), i=1..n))

end:

a:= n-> (p-> add(coeff(p, x, i)*i, i=0..n))(b(n, n)):

seq(a(n), n=0..23);

MATHEMATICA

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[

b[n - i, Min[m, i]]*g[i]*Binomial[n - 1, i - 1], {i, 1, n}]];

a[n_] := Function[p, Sum[Coefficient[p, x, i]*i, {i, 0, n}]][b[n, n]];

Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Apr 27 2022, after Alois P. Heinz *)

CROSSREFS

Column k=1 of A350202.

Cf. A000312, A001865, A007778, A209327, A347999.

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Dec 17 2021

STATUS

approved

page 1

Search completed in 0.004 seconds