A362644 -id:A362644 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 4, 4, 3, 1, 1, 1, 5, 7, 10, 3, 1, 1, 1, 6, 11, 29, 13, 4, 1, 1, 1, 7, 16, 74, 63, 27, 4, 1, 1, 1, 8, 23, 173, 315, 258, 36, 5, 1, 1, 1, 9, 31, 383, 1532, 3039, 759, 69, 5, 1, 1, 1, 10, 41, 790, 7093, 38800, 28550, 3263, 92, 6, 1

Offset: 0

Andrew Howroyd, May 01 2023

Isomorphism is up to permutation of the elements of the n-set.

			Array begins:
============================================================
n/k| 0 1  2    3      4        5          6            7 ...
---+--------------------------------------------------------
0  | 1 1  1    1      1        1          1            1 ...
1  | 1 1  1    1      1        1          1            1 ...
2  | 1 2  3    4      5        6          7            8 ...
3  | 1 2  4    7     11       16         23           31 ...
4  | 1 3 10   29     74      173        383          790 ...
5  | 1 3 13   63    315     1532       7093        30499 ...
6  | 1 4 27  258   3039    38800     478902      5414462 ...
7  | 1 4 36  759  28550  1203468   46259693   1561933881 ...
8  | 1 5 69 3263 392641 55494682 7010194951 768995611810 ...
  ...

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

Columns k=0..3 are A000012, A004526, A362649, A362650.
Main diagonal is A362651.
Cf. A000085 (involutions), A362644, A362759.

B(c,k)=sum(j=0, c\2, if(k%2, 1, 2^(c-2*j))*k^j*binomial(c, 2*j)*(2*j)!/(2^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!)}

A362645 Number of nonisomorphic unordered pairs of permutations of an n-set.

Original entry on oeis.org

1, 1, 3, 8, 28, 96, 495, 2919, 22024, 190585, 1876379, 20445393, 244087497, 3161870309, 44155439841, 661065427709, 10561205779056, 179324080365257, 3224650449785570, 61218223893369204, 1223523447160284480, 25679025453032962924, 564657001202726478315

Offset: 0

Andrew Howroyd, May 01 2023

nonn

Isomorphism is up to permutation of the elements of the n-set.

			The a(3)=8 pairs of permutations with permutations shown in cycle notation are:
  {(1)(2)(3), (1)(2)(3)},
  {(1)(2)(3), (1)(23)},
  {(1)(2)(3), (123)},
  {(1)(23), (1)(23)},
  {(1)(23), (12)(3)},
  {(1)(23), (123)},
  {(123), (123)},
  {(123), (132)}.

Andrew Howroyd, Table of n, a(n) for n = 0..50

Column k=2 of A362644.

Cf. A362649.

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

Original entry on oeis.org

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

Andrew Howroyd, May 02 2023

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.

			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 ...
  ...

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

Columns k=0..3 are A000012, A002865, A362760, A362761.
Main diagonal is A362762.
Cf. A000166 (derangements), A320032, A362644, A362648.

\\ 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!)}

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

A362646 Number of nonisomorphic unordered triples of permutations of an n-set.

Original entry on oeis.org

1, 1, 4, 17, 159, 2655, 88885, 4255594, 271455237, 21965858675, 2195840991306, 265649187979346, 38249422682143111, 6463715133421876832, 1266831272565696798499, 285028258254526750598805, 72965650731146278648727481, 21086743012582576506980525584

Offset: 0

Andrew Howroyd, May 01 2023

nonn

Isomorphism is up to permutation of the elements of the n-set.

Andrew Howroyd, Table of n, a(n) for n = 0..50

Column k=3 of A362644.

Cf. A362645, A362650.

A362763 Array read by antidiagonals: T(n,k) is the number of nonisomorphic k-sets of permutations of an n-set.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 0, 2, 1, 0, 0, 1, 3, 1, 0, 0, 0, 5, 5, 1, 0, 0, 0, 6, 23, 7, 1, 0, 0, 0, 5, 116, 89, 11, 1, 0, 0, 0, 3, 521, 2494, 484, 15, 1, 0, 0, 0, 1, 1931, 69366, 87984, 2904, 22, 1, 0, 0, 0, 0, 5906, 1592714, 15456557, 4250015, 22002, 30, 1

Offset: 0

Andrew Howroyd, May 03 2023

Isomorphism is up to permutation of the elements of the n-set. Each permutation can be considered to be a set of disjoint directed cycles whose vertices cover the n-set. Permuting the elements of the n-set permutes each of the permutations in the k-set.

			Array begins:
====================================================================
n/k| 0  1    2       3          4             5                6 ...
---+----------------------------------------------------------------
0  | 1  1    0       0          0             0                0 ...
1  | 1  1    0       0          0             0                0 ...
2  | 1  2    1       0          0             0                0 ...
3  | 1  3    5       6          5             3                1 ...
4  | 1  5   23     116        521          1931             5906 ...
5  | 1  7   89    2494      69366       1592714         30461471 ...
6  | 1 11  484   87984   15456557    2209040882     263190866673 ...
7  | 1 15 2904 4250015 5329123475 5366409944453 4503264576070573 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals).
Aman Kushwaha and Raghavendra Tripathi, A note on Erdős matrices and Marcus-Ree inequality, arXiv:2503.09542 [math.MG], 2025. See p. 12.

Columns k=0..3 are A000012, A000041, A362764, A362765.
Row sums are A362766.
Cf. A362644.

B(n,k) = {n!*k^n}
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, k<=1, my(s=0); forpart(q=n, s+=permcount(q) * polcoef(exp(sum(m=1, k, K(R(q,m))*(x^m-x^(2*m))/m, O(x*x^k))), k)); s/n!)}

T(n,k) = 0 for k > n!.

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

A362647 Number of nonisomorphic multisets of permutations of an n-set with n permutations.

Original entry on oeis.org

1, 1, 3, 17, 888, 1882581, 274390124129, 3265588702832507993, 4299566944915974710190397764, 828675148077869385766758257425030178834, 30068353582978500344223495096836001731261047276252951, 257277650306758464761197063911448586633222894357360550424924677512839

Offset: 0

Andrew Howroyd, May 01 2023

nonn

Isomorphism is up to permutation of the elements of the n-set.

Andrew Howroyd, Table of n, a(n) for n = 0..30

Main diagonal of A362644.

Cf. A362651.

A362899 Array read by antidiagonals: T(n,k) is the number of nonisomorphic multisets of fixed-point-free endofunctions on an n-set with k endofunctions.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 9, 6, 1, 1, 0, 1, 22, 162, 13, 1, 1, 0, 1, 63, 3935, 4527, 40, 1, 1, 0, 1, 136, 81015, 1497568, 172335, 100, 1, 1, 0, 1, 302, 1369101, 384069023, 883538845, 7861940, 291, 1, 1, 0, 1, 580, 19601383, 78954264778, 3450709120355, 725601878962, 416446379, 797, 1

Offset: 0

Andrew Howroyd, May 10 2023

Isomorphism is up to permutation of the elements of the n-set. Each endofunction can be considered to be a loopless digraph where each node has out-degree 1.

			Array begins:
==============================================================
n/k| 0  1      2         3             4                 5 ...
---+----------------------------------------------------------
0  | 1  1      1         1             1                 1 ...
1  | 1  0      0         0             0                 0 ...
2  | 1  1      1         1             1                 1 ...
3  | 1  2      9        22            63               136 ...
4  | 1  6    162      3935         81015           1369101 ...
5  | 1 13   4527   1497568     384069023       78954264778 ...
6  | 1 40 172335 883538845 3450709120355 10786100835304758 ...
  ...

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

Columns k=0..3 are A000012, A001373, A362900, A362901.
Main diagonal is A362902.
Cf. A362644, A362759, A362897.

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}
K(v,m) = {prod(i=1, #v, my(g=gcd(v[i],m), e=v[i]/g); (sum(j=1, #v, my(t=v[j]); if(e%(t/gcd(t,m))==0, t)) - 1)^g)}
T(n,k) = {if(n==0, 1, my(s=0); forpart(q=n, s+=permcount(q) * polcoef(exp(sum(m=1, k, K(q,m)*x^m/m, O(x*x^k))), k)); s/n!)}

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

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 7, 1, 1, 1, 13, 74, 19, 1, 1, 1, 22, 638, 1474, 47, 1, 1, 1, 34, 4663, 118949, 41876, 130, 1, 1, 1, 50, 28529, 7643021, 42483668, 1540696, 343, 1, 1, 1, 70, 151600, 396979499, 33179970333, 23524514635, 68343112, 951, 1

Offset: 0

Andrew Howroyd, May 10 2023

Isomorphism is up to permutations of the elements of the n-set.

			Array begins:
======================================================================
n/k| 0   1       2           3               4                   5 ...
---+------------------------------------------------------------------
0  | 1   1       1           1               1                   1 ...
1  | 1   1       1           1               1                   1 ...
2  | 1   3       7          13              22                  34 ...
3  | 1   7      74         638            4663               28529 ...
4  | 1  19    1474      118949         7643021           396979499 ...
5  | 1  47   41876    42483668     33179970333      20762461502595 ...
6  | 1 130 1540696 23524514635 274252613077267 2559276179593762172 ...
  ...

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

Columns k=0..3 are A000012, A001372, A054745, A362898.
Row n=2 is A002623.
Main diagonal is A277839.
Cf. A362644.

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}
K(v,m) = {prod(i=1, #v, my(g=gcd(v[i],m), e=v[i]/g); sum(j=1, #v, my(t=v[j]); if(e%(t/gcd(t,m))==0, t))^g)}
T(n,k) = {if(n==0, 1, my(s=0); forpart(q=n, s+=permcount(q) * polcoef(exp(sum(m=1, k, K(q,m)*x^m/m, O(x*x^k))), k)); s/n!)}

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A362645 Number of nonisomorphic unordered pairs of permutations of an n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A362646 Number of nonisomorphic unordered triples of permutations of an n-set.

Views

Author

Keywords

Comments

Links

Crossrefs

A362763 Array read by antidiagonals: T(n,k) is the number of nonisomorphic k-sets of permutations of an n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A362647 Number of nonisomorphic multisets of permutations of an n-set with n permutations.

Views

Author

Keywords

Comments

Links

Crossrefs

A362899 Array read by antidiagonals: T(n,k) is the number of nonisomorphic multisets of fixed-point-free endofunctions on an n-set with k endofunctions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula