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

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, 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, 200, 14337, 295058, 211600, 3028, 8, 1, 1, 0, 1, 5, 386, 117053, 15730237, 98019999, 13511246, 25431, 12, 1

Offset: 0

Author

Andrew Howroyd, May 02 2023

Keywords

• nonn
• tabl

Comments

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.

Examples

			Array begins:
===========================================================
n/k| 0 1   2      3        4           5              6 ...
---+-------------------------------------------------------
0  | 1 1   1      1        1           1              1 ...
1  | 1 0   0      0        0           0              0 ...
2  | 1 1   1      1        1           1              1 ...
3  | 1 1   2      2        3           3              4 ...
4  | 1 2   7     18       43          93            200 ...
5  | 1 2  16    138     1559       14337         117053 ...
6  | 1 4  84   4642   295058    15730237      706921410 ...
7  | 1 4 403 211600 98019999 36414994209 11282515303088 ...
  ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals).

Crossrefs

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

Main diagonal is A362762.

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

Programs

PARI

\\ here B(n,k) gives A320032(n,k).
B(n,k) = sum(j=0, n, (-1)^(n-j)*binomial(n,j)*k^j*j!)
K(v)=my(S=Set(v)); prod(i=1, #S, my(k=S[i], c=#select(t->t==k, v)); B(c, k))
R(v, m)=concat(vector(#v, i, my(t=v[i], g=gcd(t, m)); vector(g, i, t/g)))
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}
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!)}

Formula

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