A245692 -id:A245692

Search: a245692 -id:a245692

Displaying 1-3 of 3 results found.

page 1

A076728

a(n) = (n-1)^2 * n^(n-2).

+10
5

0, 1, 12, 144, 2000, 32400, 605052, 12845056, 306110016, 8100000000, 235794769100, 7492001071104, 258071096741328, 9581271191425024, 381454233398437500, 16212958658533785600, 732780301186512843008, 35096024486915738763264, 1775645341922275908244236

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

OFFSET

1,3

COMMENTS

Smallest integer value of the form 1/z(k,n) where z(k,x)=x/(x-1)^2 -sum(i=1,k,i/x^i).

For any x>1 lim k -> infinity z(k,x)=0. More generally if p is an integer >=2, 1/z(u(k),p) is an integer for any k>=2 where u(k)=(p-1)^2*p^((p^k-(p-1)*k-p)/(p-1)). u(k) can also be written : u(k)=(p-1)^2 *p^(1+p+p^2+...+p^(k-2)).

For n>=2, a(n) is equal to the number of functions f:{1,2,...,n}->{1,2,...,n} such that for fixed, different x_1, x_2 in {1,2,...,n} and fixed y_1, y_2 in {1,2,...,n} we have f(x_1)<>y_1 and f(x_2)<> y_2. - Milan Janjic, May 10 2007

a(n+1) = Sum_{k=0...n} binomial(n,k)*n^k*k, which enumerates the total number of elements in the domain of definition over all partial functions on n labeled objects. - Geoffrey Critzer, Feb 08 2012

Also, the number of possible negation tables in the n-valued logics (cf. A262458 and A262459). - Max Alekseyev, Sep 23 2015

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..386

Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets

MATHEMATICA

Table[Sum[Binomial[n, k] n^k k, {k, 0, n}], {n, 1, 20}] (* Geoffrey Critzer, Feb 08 2012 *)

PROG

(PARI) a(n) = (n-1)^2*n^(n-2)

CROSSREFS

Column k=0 of A245692.

KEYWORD

nonn

AUTHOR

Benoit Cloitre, Oct 25 2002

EXTENSIONS

a(1)=0 prepended by Max Alekseyev, Sep 23 2015

Some terms corrected by Alois P. Heinz, May 22 2016

STATUS

approved

A245348

Number T(n,k) of endofunctions f on [n] that are self-inverse on [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

+10
5

1, 1, 1, 4, 3, 2, 27, 15, 8, 4, 256, 112, 50, 22, 10, 3125, 1125, 430, 166, 66, 26, 46656, 14256, 4752, 1626, 576, 206, 76, 823543, 218491, 64484, 19768, 6310, 2054, 688, 232, 16777216, 3932160, 1040384, 288512, 83736, 24952, 7660, 2388, 764

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

OFFSET

0,4

COMMENTS

T(n,k) counts endofunctions f:{1,...,n}-> {1,...,n} with f(f(i))=i for all i in {1,...,k}.

LINKS

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

FORMULA

T(n,k) = Sum_{i=0..min(k,n-k)} C(n-k,i)*C(k,i)*i!*A000085(k-i)*n^(n-k-i).

EXAMPLE

T(3,1) = 15: (1,1,1), (2,1,1), (3,1,1), (1,2,1), (3,2,1), (1,3,1), (3,3,1), (1,1,2), (2,1,2), (1,2,2), (1,3,2), (1,1,3), (2,1,3), (1,2,3), (1,3,3).

T(3,2) = 8: (2,1,1), (1,2,1), (3,2,1), (2,1,2), (1,2,2), (1,3,2), (2,1,3), (1,2,3).

T(3,3) = 4: (3,2,1), (1,3,2), (2,1,3), (1,2,3).

Triangle T(n,k) begins:

0 : 1;

1 : 1, 1;

2 : 4, 3, 2;

3 : 27, 15, 8, 4;

4 : 256, 112, 50, 22, 10;

5 : 3125, 1125, 430, 166, 66, 26;

6 : 46656, 14256, 4752, 1626, 576, 206, 76;

7 : 823543, 218491, 64484, 19768, 6310, 2054, 688, 232;

...

MAPLE

g:= proc(n) g(n):= `if`(n<2, 1, g(n-1)+(n-1)*g(n-2)) end:

T:= (n, k)-> add(binomial(n-k, i)*binomial(k, i)*i!*

g(k-i)*n^(n-k-i), i=0..min(k, n-k)):

seq(seq(T(n, k), k=0..n), n=0..10);

MATHEMATICA

g[n_] := g[n] = If[n<2, 1, g[n-1] + (n-1)*g[n-2]]; T[0, 0] = 1; T[n_, k_] := Sum[Binomial[n-k, i]*Binomial[k, i]*i!*g[k-i]*n^(n-k-i), {i, 0, Min[k, n-k]}]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 19 2017, translated from Maple *)

CROSSREFS

Columns k=0-1 give: A000312, A089945(n-1) for n>0.

Main diagonal gives A000085.

T(2n,n) gives A245141.

Cf. A239771, A245692.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jul 18 2014

STATUS

approved

A245693

Number T(n,k) of permutations on [n] that are self-inverse on [k] but not on [k+1]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

+10
2

1, 0, 1, 0, 0, 2, 2, 0, 0, 4, 12, 2, 0, 0, 10, 72, 18, 4, 0, 0, 26, 480, 120, 36, 8, 0, 0, 76, 3600, 840, 264, 84, 20, 0, 0, 232, 30240, 6480, 1920, 648, 216, 52, 0, 0, 764, 282240, 55440, 15120, 4920, 1776, 612, 152, 0, 0, 2620, 2903040, 524160, 131040, 39600, 13920, 5232, 1848, 464, 0, 0, 9496

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

OFFSET

0,6

COMMENTS

T(n,k) counts permutations p:{1,...,n}-> {1,...,n} with p(p(i))=i for all i in {1,...,k} and p(p(k+1))<>k+1 if k<n.

LINKS

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

FORMULA

T(n,k) = H(n,k) - H(n,k+1) with H(n,k) = Sum_{i=0..min(k,n-k)} C(n-k,i) * C(k,i) * i! * A000085(k-i) * (n-k-i)!.

EXAMPLE

Triangle T(n,k) begins:

0 : 1;

1 : 0, 1;

2 : 0, 0, 2;

3 : 2, 0, 0, 4;

4 : 12, 2, 0, 0, 10;

5 : 72, 18, 4, 0, 0, 26;

6 : 480, 120, 36, 8, 0, 0, 76;

7 : 3600, 840, 264, 84, 20, 0, 0, 232;

8 : 30240, 6480, 1920, 648, 216, 52, 0, 0, 764;

MAPLE

g:= proc(n) g(n):= `if`(n<2, 1, g(n-1)+(n-1)*g(n-2)) end:

H:= (n, k)-> add(binomial(n-k, i)*binomial(k, i)*i!*

g(k-i)*(n-k-i)!, i=0..min(k, n-k)):

T:= (n, k)-> H(n, k) -H(n, k+1):

seq(seq(T(n, k), k=0..n), n=0..10);

MATHEMATICA

g[n_] := g[n] = If[n < 2, 1, g[n - 1] + (n - 1)*g[n - 2]];

H[n_, k_] := Sum[Binomial[n - k, i]*Binomial[k, i]*i!*

g[k - i]*(n - k - i)!, {i, 0, Min[k, n - k]}];

T[n_, k_] := H[n, k] - H[n, k + 1];

Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Feb 10 2021, after Alois P. Heinz *)

CROSSREFS

Column k=0 give A062119(n-1) for n>1.

Row sums give A000142.

Main diagonal gives A000085.

Cf. A245692 (the same for endofunctions).

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jul 29 2014

STATUS

approved

page 1

Search completed in 0.008 seconds