A231797 -id:A231797 - cp's OEIS frontend

A245405 Number A(n,k) of endofunctions on [n] such that no element has a preimage of cardinality k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 0, 2, 1, 1, 2, 6, 1, 1, 2, 3, 24, 1, 1, 4, 9, 40, 120, 1, 1, 4, 24, 76, 205, 720, 1, 1, 4, 27, 208, 825, 2556, 5040, 1, 1, 4, 27, 252, 2325, 10206, 24409, 40320, 1, 1, 4, 27, 256, 3025, 31956, 143521, 347712, 362880, 1, 1, 4, 27, 256, 3120, 44406, 520723, 2313200, 4794633, 3628800

Offset: 0

Alois P. Heinz, Jul 21 2014

			Square array A(n,k) begins:
0 :   1,    1,     1,     1,     1,     1,     1, ...
1 :   1,    0,     1,     1,     1,     1,     1, ...
2 :   2,    2,     2,     4,     4,     4,     4, ...
3 :   6,    3,     9,    24,    27,    27,    27, ...
4 :  24,   40,    76,   208,   252,   256,   256, ...
5 : 120,  205,   825,  2325,  3025,  3120,  3125, ...
6 : 720, 2556, 10206, 31956, 44406, 46476, 46650, ...

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

Column k=0-10 give: A000142, A231797, A245406, A245407, A245408, A245409, A245410, A245411, A245412, A245413, A245414.
Main diagonal gives A061190.
A(n,n+1) gives A000312.

b:= proc(n, i, k) option remember; `if`(n=0 and i=0, 1,
      `if`(i<1, 0, add(`if`(j=k, 0, b(n-j, i-1, k)*
       binomial(n, j)), j=0..n)))
    end:
A:= (n, k)-> b(n$2, k):
seq(seq(A(n, d-n), n=0..d), d=0..14);

nn = n; f[m_]:=Flatten[Table[m[[j, i - j + 1]], {i, 1, Length[m]}, {j, 1, i}]]; f[Transpose[Table[Prepend[Table[n! Coefficient[Series[(Exp[x] -x^k/k!)^n, {x, 0, nn}],x^n], {n, 1, 10}], 1], {k, 0, 10}]]] (* Geoffrey Critzer, Jan 31 2015 *)

A(n,k) = n! * [x^n] (exp(x)-x^k/k!)^n.

A254382 Number of rooted labeled trees on n nodes such that every nonroot node is the child of a branching node or of the root.

Original entry on oeis.org

0, 1, 2, 3, 16, 85, 696, 6349, 72080, 918873, 13484080, 219335281, 3962458248, 78203547877, 1680235050872, 38958029188485, 970681471597216, 25847378934429361, 732794687650764000, 22032916968153975769, 700360446794528578520

Offset: 0

Geoffrey Critzer, Jan 29 2015

nonn

Here, a branching node is a node with at least two children.
In other words, a(n) is the number of labeled rooted trees on n nodes such that the path from every node towards the root reaches a branching node (or the root) in one step.
Also labeled rooted trees that are lone-child-avoiding except possibly for the root. The unlabeled version is A198518. - Gus Wiseman, Jan 22 2020

			a(5) = 85:
...0................0...............0-o...
...|.............../ \............ /|\....
...o..............o   o...........o o o...
../|\............/ \   ...................
.o o o..........o   o   ..................
These trees have 20 + 60 + 5 = 85 labelings.
From _Gus Wiseman_, Jan 22 2020: (Start)
The a(1) = 1 through a(4) = 16 trees (in the format root[branches]) are:
  1  1[2]  1[2,3]  1[2,3,4]
     2[1]  2[1,3]  1[2[3,4]]
           3[1,2]  1[3[2,4]]
                   1[4[2,3]]
                   2[1,3,4]
                   2[1[3,4]]
                   2[3[1,4]]
                   2[4[1,3]]
                   3[1,2,4]
                   3[1[2,4]]
                   3[2[1,4]]
                   3[4[1,2]]
                   4[1,2,3]
                   4[1[2,3]]
                   4[2[1,3]]
                   4[3[1,2]]
(End)

Vaclav Kotesovec, Table of n, a(n) for n = 0..200
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Cf. A231797, A052318 (condition is applied only to leaf nodes).
The unlabeled version is A198518
The non-planted case is A060356.
Labeled rooted trees are A000169.
Lone-child-avoiding rooted trees are A001678(n + 1).
Labeled topologically series-reduced rooted trees are A060313.
Labeled lone-child-avoiding unrooted trees are A108919.
Cf. A000014, A000669, A001679, A005512, A291636, A331488, A331578.

nn = 20; b = 1 + Sum[nn = n; n! Coefficient[Series[(Exp[x] - x)^n, {x, 0, nn}], x^n]*x^n/n!, {n,1, nn}]; c = Sum[a[n] x^n/n!, {n, 0, nn}]; sol = SolveAlways[b == Series[1/(1 - (c - x)), {x, 0, nn}], x]; Flatten[Table[a[n], {n, 0, nn}] /. sol]
nn = 30; CoefficientList[Series[1+x-1/Sum[SeriesCoefficient[(E^x-x)^n,{x,0,n}]*x^n,{n,0,nn}],{x,0,nn}],x] * Range[0,nn]! (* Vaclav Kotesovec, Jan 30 2015 *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
lrt[set_]:=If[Length[set]==0,{},Join@@Table[Apply[root,#]&/@Join@@Table[Tuples[lrt/@stn],{stn,sps[DeleteCases[set,root]]}],{root,set}]];
Table[Length[Select[lrt[Range[n]],FreeQ[Z@@#,Integer[]]&]],{n,6}] (* Gus Wiseman, Jan 22 2020 *)

E.g.f.: A(x) satisfies 1/(1 - (A(x) - x)) = B(x) where B(x) is the e.g.f. for A231797.

a(n) ~ (1-exp(-1))^(n-1/2) * n^(n-1). - Vaclav Kotesovec, Jan 30 2015

A241581 Row sums in triangle A241580.

Original entry on oeis.org

1, 1, 8, 54, 584, 7350, 114162, 2053688, 42513984, 991883610, 25807006730, 740614555692, 23250961252752, 792694751381078, 29169262097277330, 1152329533163353680, 48645406703597457152, 2185462919071085059890, 104113841197940277430554, 5242449827954998459195220

Offset: 1

N. J. A. Sloane, Apr 29 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..200
R. K. Guy, Letter to N. J. A. Sloane, Jun 21, 1975

Cf. A241580, A231797, A245687.

M:=20;
T[1,1]:=1:
for n from 2 to M do
   T[n,n]:=(n-1)^(n-1);
   for k from n-1 by -1 to 1 do
      T[n,k]:=T[n,k+1]-(n-1)*T[n-1,k]:
od:
od:
f:=n->(n^n-T[n+1,1])/n;[seq(f(n),n=1..M-1)];

a(n) = (n^n-A241580(n+1,1))/n.

a(n) = A245687(n,1)/n. - Alois P. Heinz, Jul 29 2014

A245496 a(n) = n! * [x^n] (exp(x)+x)^n.

Original entry on oeis.org

1, 2, 10, 87, 1096, 18045, 365796, 8793337, 244327616, 7701562377, 271493172100, 10582453248741, 451909972458000, 20980984760560045, 1052197311966267572, 56683993296812515425, 3264626390205804733696, 200168726219982496336401, 13017989155680578824221060

Offset: 0

Vaclav Kotesovec, Jul 24 2014

a(n) is the number of ways to place n labeled balls (colored red and blue) into n labeled bins so that if a blue ball occupies a bin then there are no other balls with it. - Geoffrey Critzer, Jan 30 2015

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A231797, A245493, A245405, A331726.

Table[n!*SeriesCoefficient[(E^x+x)^n, {x, 0, n}], {n, 0, 20}]
Flatten[{1,Table[n!+Sum[Binomial[n,j]^2*(n-j)^(n-j)*j!,{j,0,n-1}],{n,1,20}]}]

seq(n)={Vec(serlaplace(1/((1 - x) * (1 + lambertw(-x/(1 - x) + O(x*x^n))))), -(n+1))} \\ Andrew Howroyd, Jan 25 2020

a(n) = n!*sum(k=0, n, k^k/k!*binomial(n, k)); \\ Seiichi Manyama, Jul 19 2022

a(n) ~ (1+exp(-1))^(n+1/2) * n^n.
E.g.f.: 1 / ((1 - x) * (1 + LambertW(-x/(1 - x)))). - Ilya Gutkovskiy, Jan 25 2020
a(n) = n! * Sum_{k=0..n} k^k/k! * binomial(n,k). - Seiichi Manyama, Jul 19 2022

A206823 Triangular array read by rows: T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} with exactly k elements x such that |f^(-1)(x)| = 1; n>=0, 0<=k<=n.

Original entry on oeis.org

1, 0, 1, 2, 0, 2, 3, 18, 0, 6, 40, 48, 144, 0, 24, 205, 1000, 600, 1200, 0, 120, 2556, 7380, 18000, 7200, 10800, 0, 720, 24409, 125244, 180810, 294000, 88200, 105840, 0, 5040, 347712, 1562176, 4007808, 3857280, 4704000, 1128960, 1128960, 0, 40320

Offset: 0

Geoffrey Critzer, Feb 12 2012

Row sums = n^n, all functions f:{1,2,...,n}->{1,2,...,n}.

T(n,n)= n!, bijections on {1,2,...,n}.

			Triangle T(n,k) begins:
    1;
    0      1;
    2      0     2;
    3     18     0      6;
   40     48   144      0    24;
  205   1000   600   1200     0     120;
  ...

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

Row sums give: A000312.
Column k=0 gives: A231797.
Cf. A231602.

with(combinat): C:= binomial:
b:= proc(t, i, u) option remember; `if`(t=0, 1,
      `if`(i<2, 0, b(t, i-1, u) +add(multinomial(t, t-i*j, i$j)
      *b(t-i*j, i-1, u-j)*u!/(u-j)!/j!, j=1..t/i)))
    end:
T:= (n, k)-> C(n, k)*C(n, k)*k! *b(n-k$2, n-k):
seq(seq(T(n, k), k=0..n), n=0..10); # Alois P. Heinz, Nov 13 2013

nn = 8; Prepend[CoefficientList[Table[n! Coefficient[Series[(Exp[x] - x + y x)^n, {x, 0, nn}], x^n], {n, 1, nn}], y], {1}] // Flatten

E.g.f.: Sum_{k=0..n} T(n,k) * y^k * x^n / n! = (exp(x) - x + y*x)^n.

A241580 Triangle read by rows: T(n,k) (1 <= k <= n) defined by T(n,n) = (n-1)^(n-1), T(n,k) = T(n,k+1) - (n-1)*T(n-1,k) for k = n-1 .. 1.

Original entry on oeis.org

1, 0, 1, 2, 2, 4, 3, 9, 15, 27, 40, 52, 88, 148, 256, 205, 405, 665, 1105, 1845, 3125, 2556, 3786, 6216, 10206, 16836, 27906, 46656, 24409, 42301, 68803, 112315, 183757, 301609, 496951, 823543, 347712, 542984, 881392, 1431816, 2330336, 3800392, 6213264, 10188872, 16777216

Offset: 1

N. J. A. Sloane, Apr 29 2014

Arises in analysis of game with n players: each person picks a number from 1 to n, and the winner is the largest unique choice (see Guy's letter). T(n,k) is the number out of all possible games (i.e., all n^n sets of choices) which are won by a given player who has chosen k.

			Triangle begins:
      1;
      0,     1;
      2,     2,     4;
      3,     9,    15,     27;
     40,    52,    88,    148,    256;
    205,   405,   665,   1105,   1845,   3125;
   2556,  3786,  6216,  10206,  16836,  27906,  46656;
  24409, 42301, 68803, 112315, 183757, 301609, 496951, 823543;
  ...

R. K. Guy, Letter to N. J. A. Sloane, Jun 21, 1975

T(n,0) is A231797, row sums are A241581.

M:=20;
M2:=10;
T[1,1]:=1:
for n from 2 to M do
   T[n,n]:=(n-1)^(n-1);
   for k from n-1 by -1 to 1 do
      T[n,k]:=T[n,k+1]-(n-1)*T[n-1,k]:
od:
od:
for n from 1 to M2 do lprint([seq(T[n,k],k=1..n)]); od:

A331727 E.g.f.: -LambertW(-x/(1 + x)) / (1 + x).

Original entry on oeis.org

0, 1, -2, 9, -32, 225, -1044, 11515, -53696, 1056321, -2809700, 164953371, 374457744, 42734920657, 415505963068, 17518516958475, 310367497789696, 10529847396874497, 258747727039635132, 8599295530916762779, 258064489282796717200, 9014901067536225062481

Offset: 0

Ilya Gutkovskiy, Jan 25 2020

sign

Vaclav Kotesovec, Table of n, a(n) for n = 0..400

Cf. A000169, A060356, A231797, A277511, A331726.

nmax = 21; CoefficientList[Series[-LambertW[-x/(1 + x)]/(1 + x), {x, 0, nmax}], x] Range[0, nmax]!
Table[Sum[(-1)^k Binomial[n, k]^2 k! (n - k)^(n - k - 1), {k, 0, n - 1}], {n, 0, 21}]

seq(n)={Vec(serlaplace(-lambertw(-x/(1 + x) + O(x*x^n)) / (1 + x)), -(n+1))} \\ Andrew Howroyd, Jan 25 2020

a(n) = Sum_{k=0..n-1} (-1)^k * binomial(n,k)^2 * k! * (n - k)^(n - k - 1).

a(n) ~ (1 - exp(-1))^(n + 3/2) * n^(n-1). - Vaclav Kotesovec, Jan 26 2020

cp's OEIS Frontend

A245405 Number A(n,k) of endofunctions on [n] such that no element has a preimage of cardinality k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A254382 Number of rooted labeled trees on n nodes such that every nonroot node is the child of a branching node or of the root.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A241581 Row sums in triangle A241580.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A245496 a(n) = n! * [x^n] (exp(x)+x)^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A206823 Triangular array read by rows: T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} with exactly k elements x such that |f^(-1)(x)| = 1; n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A241580 Triangle read by rows: T(n,k) (1 <= k <= n) defined by T(n,n) = (n-1)^(n-1), T(n,k) = T(n,k+1) - (n-1)*T(n-1,k) for k = n-1 .. 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A331727 E.g.f.: -LambertW(-x/(1 + x)) / (1 + x).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula