login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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).

Sequence in context: A240509 A344901 A330619 * A297866 A298133 A298070

Adjacent sequences:  A245690 A245691 A245692 * A245694 A245695 A245696

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jul 29 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 21:27 EDT 2021. Contains 348217 sequences. (Running on oeis4.)