A362759 - OEIS

A362759

Array read by antidiagonals: T(n,k) is the number of nonisomorphic multisets of derangements of an n-set with k derangements.

%I #10 May 03 2023 21:37:02

%S 1,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,1,2,2,1,1,0,1,2,7,2,1,1,0,1,3,18,

%T 16,4,1,1,0,1,3,43,138,84,4,1,1,0,1,4,93,1559,4642,403,7,1,1,0,1,4,

%U 200,14337,295058,211600,3028,8,1,1,0,1,5,386,117053,15730237,98019999,13511246,25431,12,1

%N Array read by antidiagonals: T(n,k) is the number of nonisomorphic multisets of derangements of an n-set with k derangements.

%C Isomorphism is up to permutation of the elements of the n-set. A derangement is a permutation without fixed points. Each derangement can be considered to be a set of disjoint directed cycles excluding singleton loops whose vertices cover the n-set. Permuting the elements of the n-set permutes each of the derangements in the multiset.

%H Andrew Howroyd, <a href="/A362759/b362759.txt">Table of n, a(n) for n = 0..1325</a> (first 51 antidiagonals).

%F T(0,k) = T(2,k) = 1.

%e Array begins:

%e ===========================================================

%e n/k| 0 1 2 3 4 5 6 ...

%e ---+-------------------------------------------------------

%e 0 | 1 1 1 1 1 1 1 ...

%e 1 | 1 0 0 0 0 0 0 ...

%e 2 | 1 1 1 1 1 1 1 ...

%e 3 | 1 1 2 2 3 3 4 ...

%e 4 | 1 2 7 18 43 93 200 ...

%e 5 | 1 2 16 138 1559 14337 117053 ...

%e 6 | 1 4 84 4642 295058 15730237 706921410 ...

%e 7 | 1 4 403 211600 98019999 36414994209 11282515303088 ...

%e ...

%o (PARI) \\ here B(n,k) gives A320032(n,k).

%o B(n,k) = sum(j=0, n, (-1)^(n-j)*binomial(n,j)*k^j*j!)

%o K(v)=my(S=Set(v)); prod(i=1, #S, my(k=S[i], c=#select(t->t==k, v)); B(c, k))

%o R(v, m)=concat(vector(#v, i, my(t=v[i], g=gcd(t, m)); vector(g, i, t/g)))

%o permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}

%o T(n,k) = {if(n==0, 1, my(s=0); forpart(q=n, s += permcount(q) * polcoef(exp(sum(m=1, k, K(R(q,m))*x^m/m, O(x*x^k))), k)); s/n!)}

%Y Columns k=0..3 are A000012, A002865, A362760, A362761.

%Y Main diagonal is A362762.

%Y Cf. A000166 (derangements), A320032, A362644, A362648.

%K nonn,tabl

%O 0,19

%A _Andrew Howroyd_, May 02 2023