login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A293211 Triangle T(n,k) is the number of permutations on n elements with at least one k-cycle for 1 <= k <= n. 12
1, 1, 1, 4, 3, 2, 15, 9, 8, 6, 76, 45, 40, 30, 24, 455, 285, 200, 180, 144, 120, 3186, 1995, 1400, 1260, 1008, 840, 720, 25487, 15855, 11200, 8820, 8064, 6720, 5760, 5040, 229384, 142695, 103040, 79380, 72576, 60480, 51840, 45360, 40320, 2293839, 1427895, 1030400, 793800, 653184, 604800, 518400, 453600, 403200, 362880 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

T(n,k) is equivalent to n! minus the number of permutations on n elements with zero k-cycles (sequence A122974).

LINKS

Table of n, a(n) for n=1..55.

Dennis P. Walsh, The number of permutations with no k-cycles

FORMULA

T(n,k) = n! * Sum_{j=1..floor(n/k)} (-1)^(j+1)*(1/k)^j/j!.

T(n,k) = n! - A122974(n,k).

E.g.f. of column k: (1-exp(-x^k/k))/(1-x). - Alois P. Heinz, Oct 11 2017

EXAMPLE

T(n,k) (the first 8 rows):

:     1;

:     1,     1;

:     4,     3,     2;

:    15,     9,     8,    6;

:    76,    45,    40,   30,   24;

:   455,   285,   200,  180,  144,  120;

:  3186,  1995,  1400, 1260, 1008,  840,  720;

: 25487, 15855, 11200, 8820, 8064, 6720, 5760, 5040;

  ...

T(4,3)=8 since there are exactly 8 permutations on {1,2,3,4} with at least one 3-cycle: (1)(234), (1)(243), (2)(134), (2)(143), (3)(124), (3)(142), (4)(123), and (4)(132).

MAPLE

T:=(n, k)->n!*sum((-1)^(j+1)*(1/k)^j/j!, j=1..floor(n/k)); seq(seq(T(n, k), k=1..n), n=1..10);

MATHEMATICA

Table[n!*Sum[(-1)^(j + 1)*(1/k)^j/j!, {j, Floor[n/k]}], {n, 10}, {k, n}] // Flatten (* Michael De Vlieger, Oct 02 2017 *)

CROSSREFS

Columns k=1-10 give: A002467, A027616, A027617, A029571, A029572, A029573, A029574, A029575, A029576, A029577.

Row sums give A132961.

T(n,n) gives A000142(n-1) for n>0.

T(2n,n) gives A052145.

Cf. A122974, A126074.

Sequence in context: A202696 A319541 A239020 * A061312 A019130 A245348

Adjacent sequences:  A293208 A293209 A293210 * A293212 A293213 A293214

KEYWORD

easy,nonn,tabl

AUTHOR

Dennis P. Walsh, Oct 02 2017

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 November 17 23:26 EST 2019. Contains 329242 sequences. (Running on oeis4.)