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!)
A261762 Triangle read by rows: T(n,k) is the number of subpermutations of an n-set whose orbits are each of size at most k, and without fixed points. Equivalently, T(n,k) is the number of partial derangements of an n-set each of whose orbits is of size at most k. 6
1, 1, 1, 1, 1, 4, 1, 1, 10, 18, 1, 1, 46, 78, 108, 1, 1, 166, 486, 636, 780, 1, 1, 856, 3096, 4896, 5760, 6600, 1, 1, 3844, 21204, 40104, 52200, 58080, 63840, 1, 1, 21820, 167868, 363168, 508320, 602400, 648480, 693840, 1, 1, 114076, 1370268, 3490848, 5450400, 6720480 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

The OEIS values correct the values b(n,k) in the Laradji-Umar Table 2.1 in column k=2. Note that the row sums (meaning: sums up to the diagonal of the triangle) in Table 2.1 in the article are also incorrect.

There were typos in the column (k=2) of the original article. The entry 94 should be 166 and the entry 784 should be 856, which have been corrected. Unlike most triangles the off-diagonal terms are not 0 because T(n, n)= T(n, n+k) for all nonnegative k which is obvious from the definition.

LINKS

Table of n, a(n) for n=0..51.

A. Laradji and A. Umar, On the number of subpermutations with fixed orbit size, Ars Combinatoria, 109 (2013), 447-460.

FORMULA

T(n,k) = T(n-1,k) + 3(n-1)T(n-2,k) + ... +(k+1)(n-1)(n-2)...(n-k+1)T(n-k,k) if k<=n.

T(n,k) = T(n,n) if k>n, not part of the triangle.

T(n,0) = T(n,1) = 1.

T(n,n) = A144085(n). (Diagonal)

G.f.: exp(x+(3x^2)/2+ ... +((k+1)x^k)/k).

EXAMPLE

T(3,2) = 10 because there are 10 subpermutations on {1,2,3}, each of whose orbit is of size at most 2, and without fixed points, namely: Empty map, (1,2) --> (2,1), (1,3) --> (3,1) (2,3) --> (3,2),  1-->2, 1-->3, 2-->1,  2-->3, 3-->1, 3-->2.

Triangle starts:

1;

1, 1;

1, 1, 4;

1, 1, 10, 18;

1, 1, 46, 78, 108;

1, 1, 166, 486, 636, 780;

...

MAPLE

A261762 := proc(n, k)

    if k = 0 then

        1;

    else

        if k < 1 then

            g := 1;

        elif k < 2 then

            g := exp(x) ;

        else

            g := exp(x+add((j+1)*x^j/j, j=2..k)) ;

        fi;

        coeftayl(g, x=0, n) *n! ;

    end if;

end proc:

seq(seq( A261762(n, k), k=0..n), n=0..12) ; # R. J. Mathar, Nov 04 2015

MATHEMATICA

T[n_, k_] := SeriesCoefficient[ Exp[ x + Sum[ (j+1)*x^j/j, {j, 2, k}]], {x, 0, n}] * n!; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-Fran├žois Alcover, Apr 13 2017 *)

CROSSREFS

Cf. A157400, A261763, A261764, A261765, A261766, A261767.

Sequence in context: A164366 A121692 A264614 * A225062 A145271 A232774

Adjacent sequences:  A261759 A261760 A261761 * A261763 A261764 A261765

KEYWORD

nonn,tabl

AUTHOR

Samira Stitou, Sep 21 2015

EXTENSIONS

More terms from Alois P. Heinz, Oct 07 2015

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 20 13:38 EDT 2021. Contains 348108 sequences. (Running on oeis4.)