Mark Wildon - cp's OEIS frontend

A261318 Number of set partitions T'_t(n) of {1,2,...,t} into exactly n parts, with an even number of elements in each part distinguished by marks, and such that no part contains both 1 and t with 1 unmarked or both i and i+1 with i+1 unmarked for some i with 1 <= i < t; triangle T'_t(n), t>=0, 0<=n<=t, read by rows.

1, 0, 0, 0, 1, 1, 0, 0, 3, 1, 0, 1, 10, 8, 1, 0, 0, 30, 50, 15, 1, 0, 1, 91, 280, 155, 24, 1, 0, 0, 273, 1491, 1365, 371, 35, 1, 0, 1, 820, 7728, 11046, 4704, 756, 48, 1, 0, 0, 2460, 39460, 85050, 53382, 13020, 1380, 63, 1

Offset: 0

Mark Wildon, Aug 14 2015

T'_t(n) is the number of sequences of t non-identity top-to-random shuffles that leave a deck of n cards invariant, if each shuffle is permitted to flip the orientation of the card it moves and every card must be moved at least once.

			Triangle starts:
1;
0,  0;
0,  1,   1;
0,  0,   3,    1;
0,  1,  10,    8,     1;
0,  0,  30,   50,    15,    1;
0,  1,  91,  280,   155,   24,   1;
0,  0, 273, 1491,  1365,  371,  35,  1;
0,  1, 820, 7728, 11046, 4704, 756, 48,  1;

John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D, arXiv:1507.04803 [math.CO], 2015.

Cf. A261275, A261139, A261137.

TGF[1, x_] := x^2/(1 - x^2); TGF[n_, x_] := x^n/(1 + x)*Product[1/(1 - (2*j - 1)*x), {j, 1, n}];
T[0, 0] := 1; T[, 0] := 0; T[0,]:=0; T[t_, n_] := Coefficient[Series[TGF[n, x], {x, 0, t}], x^t]

T(t, n) = {if ((t==0) && (n==0), return(1)); if (n==0, return(0)); if (n==1, return(1 - t%2)); 1/(2^n*n!)*(sum(k=0,n-1,binomial(n,k)*(-1)^k*(2*(n-k)-1)^t)+(-1)^(n+t));}
tabl(nn) = {for (t=0, nn, for (n=0, t, print1(T(t, n), ", ");); print(););} \\ Michel Marcus, Aug 17 2015

T'_t(n) = 1/2^n n! sum(k=0..n-1,binomial(n,k)*(-1)^k*(2(n-k)-1)^t)+(-1)^(n+t)/2^n! for n > 1.
G.f. for column n>1: x^n/((1+x)*Product_{j=1..n-1} 1/(1-(2*j-1)*x)).
Asymptotically for n > 1: T'_t(n) equals (2n-1)^t/2^n n!

One more row by Michel Marcus, Aug 17 2015

Corrected description in name to agree with section 4.1 in linked paper Mark Wildon, Mar 11 2019

A261319 Number of set partitions C'_t(n) of {1,2,...,t} into at most n parts, with an even number of elements in each part distinguished by marks and such that no part contains both 1 and t (each unmarked) or both i and i+1 (each unmarked) for some i with 1 <= i < t; triangle C'_t(n), t>=0, 0<=n<=t, read by rows.

Original entry on oeis.org

1, 0, 0, 0, 1, 2, 0, 0, 3, 4, 0, 1, 11, 19, 20, 0, 0, 30, 80, 95, 96, 0, 1, 92, 372, 527, 551, 552, 0, 0, 273, 1764, 3129, 3500, 3535, 3536, 0, 1, 821, 8549, 19595, 24299, 25055, 25103, 25104

Offset: 0

Mark Wildon, Aug 14 2015

C'_t(n) is the number of sequences of t non-identity top-to-random shuffles that leave a deck of n cards invariant, if each shuffle is permitted to flip the orientation of the card it moves.
C't(n) = <(pi-1{BSym_n})^t, 1_{BSym_n}> where pi is the permutation character of the hyperoctahedral group BSym_n = C_2 wreath Sym_n given by its imprimitive action on a set of size 2n. This gives a combinatorial interpretation of C'_t(n) using sequences of box moves on pairs of Young diagrams.
C'_t(t) is the number of set partitions of a set of size t with an even number of elements in each part distinguished by marks and such that no part contains both 1 and t (each unmarked) or both i and i+1 (each unmarked) for some i with 1 <= i < t.
C'_t(n) = C'_t(t) if n > t.

			Triangle starts:
1;
0,  0;
0,  1,   2;
0,  0,   3,    4;
0,  1,  11,   19,    20;
0,  0,  30,   80,    95,    96;
0,  1,  92,  372,   527,   551,   552;
0,  0, 273, 1764,  3129,  3500,  3535,  3536;
0,  1, 821, 8549, 19595, 24299, 25055, 25103, 25104;

John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D, arXiv:1507.04803 [math.CO], 2015.

Cf. A261275, A261318, A261139, A261137.

TGF[1, x_] := x^2/(1 - x^2); TGF[n_, x_] := x^n/(1 + x)*Product[1/(1 - (2*j - 1)*x), {j, 1, n}];
T[0, 0] := 1; T[, 0] := 0; T[0, ] := 0; T[t_, n_] := Coefficient[Series[TGF[n, x], {x, 0, t}], x^t];
CC[t_, n_] := Sum[T[t, m], {m, 0, n}]

C't(n) + C'_t(n-1) = Sum{s=0..t-1} binomial(t-1,s)*A261275(s,n-1) for n>=1.
E.g.f.: diagonal is exp(1/2*(exp(2*x)-2*x-1)).
C't(n) = Sum{i=0..n} A261318(t,i).

A261275 Number of set partitions C_t(n) of {1,2,...,t} into at most n parts, with an even number of elements in each part distinguished by marks; triangle C_t(n), t>=0, 0<=n<=t, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 2, 3, 0, 4, 10, 11, 0, 8, 36, 48, 49, 0, 16, 136, 236, 256, 257, 0, 32, 528, 1248, 1508, 1538, 1539, 0, 64, 2080, 6896, 9696, 10256, 10298, 10299, 0, 128, 8256, 39168, 66384, 74784, 75848, 75904, 75905, 0, 256, 32896, 226496, 475136, 586352, 607520, 609368, 609440, 609441

Offset: 0

Mark Wildon, Aug 13 2015

C_t(n) is the number of sequences of t top-to-random shuffles that leave a deck of n cards invariant, if each shuffle is permitted to flip the orientation of the card it moves.
C_t(n) =  where pi is the permutation character of the hyperoctahedral group BSym_n = C_2 wreath Sym_n given by its imprimitive action on a set of size 2n. This gives a combinatorial interpretation of C_t(n) using sequences of box moves on pairs of Young diagrams.
C_t(t) is the number of set partitions of a set of size t with an even number of elements in each part distinguished by marks.
C_t(n) = C_t(t) if n > t.

			Triangle starts:
  1;
  0,  1;
  0,  2,    3;
  0,  4,   10,   11;
  0,  8,   36,   48,   49;
  0, 16,  136,  236,  256,   257;
  0, 32,  528, 1248, 1508,  1538,  1539;
  0, 64, 2080, 6896, 9696, 10256, 10298, 10299;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D, arXiv:1507.04803 [math.CO], 2015.

Columns n=0,1,2,3 give A000007, A000079, A007582, A233162 (proved for n=3 in reference above).
Main diagonal gives A004211.
Cf. A075497.

with(combinat):
b:= proc(n, i) option remember; expand(`if`(n=0, 1,
       `if`(i<1, 0, add(x^j*multinomial(n, n-i*j, i$j)/j!*add(
        binomial(i, 2*k), k=0..i/2)^j*b(n-i*j, i-1), j=0..n/i))))
    end:
T:= n-> (p-> seq(add(coeff(p, x, j), j=0..i), i=0..n))(b(n$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Aug 13 2015

CC[t_, n_] := Sum[2^(t - m)*StirlingS2[t, m], {m, 0, n}];
Table[CC[t, n], {t, 0, 12}, {n, 0, t}] // Flatten
(* Second program: *)
multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[x^j*multinomial[n, Join[{n - i*j}, Table[i, j]]]/j!*Sum[Binomial[i, 2*k], {k, 0, i/2}]^j*b[n - i*j, i - 1], {j, 0, n/i}]]];
T[n_] := Function[p, Table[Sum[Coefficient[p, x, j], {j, 0, i}], {i, 0, n} ] ][b[n, n]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

G.f.: sum(t>=0, n>=0, C_t(n)x^t/t!y^n) = exp(y/2 (exp(2*x)-1))/(1-y).

C_t(n) = Sum_{i=0..n} A075497(t,i).

A261137 Number of set partitions B'_t(n) of {1,2,...,t} into at most n parts, so that no part contains both 1 and t, or both i and i+1 with 1 <= i < t; triangle B'_t(n), t>=0, 0<=n<=t, read by rows.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 3, 4, 0, 0, 0, 5, 10, 11, 0, 0, 1, 11, 31, 40, 41, 0, 0, 0, 21, 91, 147, 161, 162, 0, 0, 1, 43, 274, 568, 694, 714, 715, 0, 0, 0, 85, 820, 2227, 3151, 3397, 3424, 3425, 0, 0, 1, 171, 2461, 8824, 14851, 17251, 17686, 17721, 17722

Offset: 0

Mark Wildon, Aug 10 2015

B'_t(n) is the number of sequences of t non-identity top-to-random shuffles that leave a deck of n cards invariant.
B't(n) = <chi^t, 1{Sym_n}> where chi is the degree n-1 constituent of the natural permutation character of the symmetric group Sym_n. This gives a combinatorial interpretation of B'_t(n) using sequences of box moves on Young diagrams.
B'_t(t) is the number of set partitions of a set of size t into parts of size at least 2 (A000296); this is also the number of cyclically spaced partitions of a set of size t.
B'_t(n) = B'_t(t) if n > t.

			Triangle starts:
  1;
  0, 0;
  0, 0, 1;
  0, 0, 0,  1;
  0, 0, 1,  3,   4;
  0, 0, 0,  5,  10,   11;
  0, 0, 1, 11,  31,   40,   41;
  0, 0, 0, 21,  91,  147,  161,  162;
  0, 0, 1, 43, 274,  568,  694,  714,  715;
  0, 0, 0, 85, 820, 2227, 3151, 3397, 3424, 3425;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D, arXiv:1507.04803 [math.CO], 2015.
D. E. Knuth and O. P. Lossers, Partitions of a circular set, Problem 11151 in Amer. Math. Monthly 114 (3), (2007), p 265, E_4.

Cf. A000296, A261139.

For columns n=3-8 see: A001045, A006342, A214142, A214167, A214188, A214239.

g:= proc(t, l, h) option remember; `if`(t=0, `if`(l=1, 0, x^h),
       add(`if`(j=l, 0, g(t-1, j, max(h,j))), j=1..h+1))
    end:
B:= t-> (p-> seq(add(coeff(p, x, j), j=0..i), i=0..t))(g(t, 0$2)):
seq(B(t), t=0..12);  # Alois P. Heinz, Aug 10 2015

StirPrimedGF[0, x_] := 1; StirPrimedGF[1, x_] := 0;
StirPrimedGF[n_, x_] := x^n/(1 + x)*Product[1/(1 - j*x), {j, 1, n - 1}];
StirPrimed[0, 0] := 1; StirPrimed[0, _] := 0;
StirPrimed[t_, n_] := Coefficient[Series[StirPrimedGF[n, x], {x, 0, t}], x^t];
BPrimed[t_, n_] := Sum[StirPrimed[t, m], {m, 0, n}]
(* Second program: *)
g[t_, l_, h_] := g[t, l, h] = If[t == 0, If[l == 1, 0, x^h], Sum[If[j == l, 0, g[t - 1, j, Max[h, j]]], {j, 1, h + 1}]];
B[t_] := Function[p, Table[Sum[Coefficient[p, x, j], {j, 0, i}], {i, 0, t}] ][g[t, 0, 0]];
Table[B[t], {t, 0, 12}] // Flatten (* Jean-François Alcover, May 20 2016, after Alois P. Heinz *)

B't(n) = Sum{i=0..n} A261139(t,i).

A261139 S'_t(n) is the number of set partitions of {1,2,...,t} into exactly n parts such that no part contains both 1 and t or both i and i+1 for some i with 1 <= i < t; triangle S'_t(n), t >= 0, 0 <= n <= t, read by rows.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 2, 1, 0, 0, 0, 5, 5, 1, 0, 0, 1, 10, 20, 9, 1, 0, 0, 0, 21, 70, 56, 14, 1, 0, 0, 1, 42, 231, 294, 126, 20, 1, 0, 0, 0, 85, 735, 1407, 924, 246, 27, 1, 0, 0, 1, 170, 2290, 6363, 6027, 2400, 435, 35, 1

Offset: 0

Mark Wildon, Aug 10 2015

S'A261137%20may%20be%20defined%20by%20B'_t(n)%20=%20Sum">t(n) is the number of sequences of t non-identity top-to-random shuffles of a deck of n cards that move each card at some time, and overall leave the deck invariant. (See link below.) A261137 may be defined by B'_t(n) = Sum{m=0..n} S'_t(m).

			Triangle starts:
  1;
  0, 0;
  0, 0, 1;
  0, 0, 0,  1;
  0, 0, 1,  2,   1;
  0, 0, 0,  5,   5,    1;
  0, 0, 1, 10,  20,    9,   1;
  0, 0, 0, 21,  70,   56,  14,   1;
  0, 0, 1, 42, 231,  294, 126,  20,  1;
  0, 0, 0, 85, 735, 1407, 924, 246, 27,  1;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D, arXiv:1507.04803 [math.CO], 2015.
D. E. Knuth and O. P. Lossers, Partitions of a circular set, Problem 11151 in Amer. Math. Monthly 114 (3), (2007), p 265, E_4.
Sophie Morier-Genoud, Counting Coxeter's friezes over a finite field via moduli spaces, arXiv:1907.12790 [math.CO], 2019.
Augustine O. Munagi, Two Applications of the Bijection on Fibonacci Set Partitions, Fibonacci Quart. 55 (2017), no. 5, 144-148. See c(n,k) p. 145 giving shifted triangle.

Columns n=3,4 give: A000975, A243869.
Row sums give A000296.
Cf. A261137.
The same as A105794, except for the first two columns.

g:= proc(t, l, h) option remember; `if`(t=0, `if`(l=1, 0, x^h),
       add(`if`(j=l, 0, g(t-1, j, max(h,j))), j=1..h+1))
    end:
S:= t-> (p-> seq(coeff(p, x, i), i=0..t))(g(t, 0$2)):
seq(S(t), t=0..12);  # Alois P. Heinz, Aug 10 2015

StirPrimedGF[n_, x_] := x^n/(1 + x)*Product[1/(1 - j*x), {j, 1, n - 1}]; T[0, 0] = 1; T[, 0] = T[, 1] = 0; T[n_, k_] := SeriesCoefficient[ StirPrimedGF[k, x], {x, 0, n}]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* script completed by Jean-François Alcover, Jan 31 2016 *)

a(n,k)=if(k==0, n==0, sum(j=0, k, binomial(k, j) * (-1)^(k-j) * ((j-1)^n + (-1)^n * (j-1))) / k!);
for(n=0, 10, for(k=0, n, print1( a(n, k), ", "); ); print(); ); \\ Andrew Howroyd, Apr 08 2017

G.f. for column n > 1: x^n/((1+x)*Product_{j=1..n-1} (1-j*x)).
S'_t(n) ~ (n-1)^t/n! as t tends to infinity.
Recurrence: S't(n) = S'{t-1}(n-1) + (n-1)*S'_{t-1}(n) for n >= 3.
S't(n) = (1/n!) * Sum{j=0..n} (-1)^(n-j) * binomial(n, j) * ((j-1)^t + (-1)^t * (j-1)) for t>0. - Andrew Howroyd, Apr 08 2017
Sum_{n=0..t} (n-1)*S'{t-1}(n) + n*S'{t-2}(n) = A000296(t) for t >= 3. - Yuchun Ji, Feb 23 2021
T(m, k) = Sum_{i=k..m} Stirling2(i-1, k-1)*(-1)^(i+m), for k >= 2. (See Peter Bala's original formula at A105794 dated Jul 10 2013.) - Igor Victorovich Statsenko, May 31 2024
T(m, k) = (Sum_{i=0..m} Stirling2(i, k)*binomial(m,i)*(-1)^(m-i))*I(m,k), where I(m,k) = (1-Sum_{i=0..m} Stirling1(k, i))^(m+k) for k >= 0. (See Peter Bala's original formula at A105794 dated Jul 10 2013.) - Igor Victorovich Statsenko, Jun 01 2024

A192983 a(n) is the number of pairs (g, h) of elements of the symmetric group S_n such that g and h have conjugates that commute.

Original entry on oeis.org

1, 4, 24, 264, 5640, 151200, 5722920, 282868992, 18371308032, 1504791561600, 148978034686800, 18007146260231040, 2528615024682544512, 426310052282058252672, 81830910530970671616000, 18305445786667543107072000, 4570435510076312321728158720

Offset: 1

Mark Wildon, Aug 03 2011

nonn

a(n) / n!^2 is the probability that two permutation in S_n, chosen independently and uniformly at random, have conjugates that commute.

Apparently n | a(n), and, for n>1, n*(n-1) | a(n). - Alexander R. Povolotsky, Sep 30 2011

			For n = 3 the probability that two elements of S_3 have conjugates that commute is a(3)/3!^2 = 2/3. Proof: only the transpositions and three cycles fail to have conjugates that commute; the probability of choosing one permutation from each of these classes is 2*1/2*1/3 = 1/3.

Simon R. Blackburn, John R. Britnell, and Mark Wildon, The probability that a pair of elements of a finite group are conjugate, arXiv:1108.1784 [math.GR], 2011-2012.
J. R. Britnell and M. Wildon, Commuting elements in conjugacy classes: an application of Hall's Marriage Theorem to group theory, J. Group Theory, 12 (2009), 795-802.
Mark Wildon, Haskell source code for computing values of the sequence.

Cf. A087132 (the sum of squares of the sizes of the conjugacy classes of S_n).

Haskell
```
-- See links for code.
```

cp's OEIS Frontend

User: Mark Wildon

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A261275 Number of set partitions C_t(n) of {1,2,...,t} into at most n parts, with an even number of elements in each part distinguished by marks; triangle C_t(n), t>=0, 0<=n<=t, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A261137 Number of set partitions B'_t(n) of {1,2,...,t} into at most n parts, so that no part contains both 1 and t, or both i and i+1 with 1 <= i < t; triangle B'_t(n), t>=0, 0<=n<=t, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A261139 S'_t(n) is the number of set partitions of {1,2,...,t} into exactly n parts such that no part contains both 1 and t or both i and i+1 for some i with 1 <= i < t; triangle S'_t(n), t >= 0, 0 <= n <= t, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A192983 a(n) is the number of pairs (g, h) of elements of the symmetric group S_n such that g and h have conjugates that commute.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell