A362648 -id:A362648 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 1, 4, 8, 5, 1, 1, 1, 5, 17, 28, 7, 1, 1, 1, 6, 34, 159, 96, 11, 1, 1, 1, 7, 61, 888, 2655, 495, 15, 1, 1, 1, 8, 105, 4521, 76854, 88885, 2919, 22, 1, 1, 1, 9, 170, 20916, 1882581, 15719714, 4255594, 22024, 30, 1

Offset: 0

Andrew Howroyd, May 01 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 multiset.

			Array begins:
====================================================================
n/k| 0  1    2       3          4             5                6 ...
---+----------------------------------------------------------------
0  | 1  1    1       1          1             1                1 ...
1  | 1  1    1       1          1             1                1 ...
2  | 1  2    3       4          5             6                7 ...
3  | 1  3    8      17         34            61              105 ...
4  | 1  5   28     159        888          4521            20916 ...
5  | 1  7   96    2655      76854       1882581         39122096 ...
6  | 1 11  495   88885   15719714    2271328951     274390124129 ...
7  | 1 15 2919 4255594 5341866647 5387750530872 4530149870111873 ...
  ...

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

Columns k=0..3 are A000012, A000041, A362645, A362646.
Rows n=3 is A002626.
Main diagonal is A362647.
Cf. A362648.

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, 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(1,k) = 1.

A362824 Array read by antidiagonals: T(n,k) is the number of k-tuples of involutions on [n] that pairwise commute.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 4, 1, 1, 1, 8, 10, 10, 1, 1, 1, 16, 22, 52, 26, 1, 1, 1, 32, 46, 232, 196, 76, 1, 1, 1, 64, 94, 976, 1016, 1216, 232, 1, 1, 1, 128, 190, 4000, 4576, 12496, 5944, 764, 1, 1, 1, 256, 382, 16192, 19376, 111376, 73648, 42400, 2620, 1

Offset: 0

Andrew Howroyd, May 06 2023

Two involutions x,y on [n] commute if x*y = y*x.

			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    4     8     16      32       64       128 ...
3  | 1   4   10    22     46      94      190       382 ...
4  | 1  10   52   232    976    4000    16192     65152 ...
5  | 1  26  196  1016   4576   19376    79696    323216 ...
6  | 1  76 1216 12496 111376  936976  7680016  62177296 ...
7  | 1 232 5944 73648 716416 6289312 52647904 430723168 ...
  ...

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

Columns k=0..3 are A000012, A000085, A362819, A362825.
Rows n=2..3 are A000079, A033484.
Main diagonal is A362823.
Cf. A022166, A362648.

\\ B(n,k) is A022166.
B(n,k)={polcoef(x^k/prod(j=0, k, 1-2^j*x + O(x*x^n)), n)}
T(n,k)={if(n==0, 1, n!*polcoef(exp(sum(j=0, min(k,logint(n,2)), B(k,j)*x^(2^j)/2^j, O(x*x^n))), n))}

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

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.

A362649 Number of nonisomorphic unordered pairs of involutions on an n-set.

Original entry on oeis.org

1, 1, 3, 4, 10, 13, 27, 36, 69, 92, 162, 217, 365, 487, 782, 1043, 1622, 2154, 3253, 4306, 6355, 8376, 12107, 15893, 22582, 29512, 41285, 53729, 74164, 96100, 131054, 169110, 228165, 293202, 391752, 501406, 664093, 846642, 1112363, 1412768, 1842620

Offset: 0

Andrew Howroyd, May 01 2023

nonn

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

			The a(4)=10 pairs of involutions are:
  {(), ()},
  {(), (34)},
  {(), (12)(34)},
  {(34), (34)},
  {(34), (23)},
  {(34), (12)},
  {(34), (12)(34)},
  {(34), (13)(24)},
  {(12)(34), (12)(34)},
  {(12)(34), (13)(24)}.

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

Column k=2 of A362648.

Cf. A000085, A362645.

A362650 Number of nonisomorphic unordered triples of involutions on an n-set.

Original entry on oeis.org

1, 1, 4, 7, 29, 63, 258, 759, 3263, 12250, 56330, 250841, 1235205, 6113154, 31941407, 169613842, 932670975, 5223815423, 30040926830, 175918987173, 1053086891249, 6413469553076, 39818396779256, 251251607202822, 1613056058498375, 10514730684539068

Offset: 0

Andrew Howroyd, May 01 2023

nonn

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

			The a(3) = 7 nonisomorphic triples of involutions are:
  {(), (), ()},
  {(), (), (23)},
  {(), (23), (23)},
  {(), (23), (12)},
  {(23), (23), (23)},
  {(23), (23), (12)},
  {(23), (12), (13)}.

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

Column k=3 of A362648.

Cf. A362646, A362649.

A362651 Number of nonisomorphic multisets of involutions on an n-set with n involutions.

Original entry on oeis.org

1, 1, 3, 7, 74, 1532, 478902, 1561933881, 74069769621942, 44786847731274624558, 454923769422460614413179958, 75365529411732671264995255795387368, 250450659464630320300793563353757730632329596, 16712244262184960007363857016489055045260380508520606142

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

Main diagonal of A362648.

Cf. A362382, A362647.

A362903 Array read by antidiagonals: T(n,k) is the number of nonisomorphic k-tuples of involutions on a (2n)-set that pairwise commute.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 8, 11, 4, 1, 1, 16, 43, 24, 5, 1, 1, 32, 171, 176, 46, 6, 1, 1, 64, 683, 1376, 611, 80, 7, 1, 1, 128, 2731, 10944, 9281, 1864, 130, 8, 1, 1, 256, 10923, 87424, 146445, 54384, 5161, 200, 9, 1, 1, 512, 43691, 699136, 2334181, 1696352, 285939, 13184, 295, 10, 1

Offset: 0

Andrew Howroyd, May 11 2023

Two involutions x,y commute if x*y = y*x. Isomorphism is up to permutation of the elements of the (2n)-set. T(n,k) also gives the values for a (2n+1)-set.

			Array begins:
======================================================
n/k| 0 1   2     3       4          5            6 ...
---+--------------------------------------------------
0  | 1 1   1     1       1          1            1 ...
1  | 1 2   4     8      16         32           64 ...
2  | 1 3  11    43     171        683         2731 ...
3  | 1 4  24   176    1376      10944        87424 ...
4  | 1 5  46   611    9281     146445      2334181 ...
5  | 1 6  80  1864   54384    1696352     53885632 ...
6  | 1 7 130  5161  285939   17562679   1110290303 ...
7  | 1 8 200 13184 1372224  165343616  20774749952 ...
8  | 1 9 295 31532 6101080 1436647664 358238974304 ...
  ...

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

Columns k=0..3 are A000012, A000027(n-1), A001752, A362904.
Rows n=1..3 are A000079, A007583, A103334(n+1).
Cf. A022166, A362648, A362824, A362826.

\\ B(n, k) is A022166.
B(n, k)={polcoef(x^k/prod(j=0, k, 1-2^j*x + O(x*x^n)), n)}
C(k,n) = Vec(1/prod(j=0, min(k-1, logint(n, 2)), (1 - x^(2^j) + O(x*x^n))^B(k,j+1), 1 - x + O(x*x^n)))
M(n,m=n) = Mat(vector(m+1, k, C(k-1, n)~))
{ my(A=M(7)); for(i=1, #A, print(A[i,])) }

G.f. of column k: 1/((1 - x)*Product_{j=0..k-1} (1 - x^(2^j))^A022166(k,j+1)).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A362824 Array read by antidiagonals: T(n,k) is the number of k-tuples of involutions on [n] that pairwise commute.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

A362649 Number of nonisomorphic unordered pairs of involutions on an n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A362650 Number of nonisomorphic unordered triples of involutions on an n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A362651 Number of nonisomorphic multisets of involutions on an n-set with n involutions.

Views

Author

Keywords

Comments

Links

Crossrefs

A362903 Array read by antidiagonals: T(n,k) is the number of nonisomorphic k-tuples of involutions on a (2n)-set that pairwise commute.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula