A274310 -id:A274310 - cp's OEIS frontend

A124419 Number of partitions of the set {1,2,...n} having no blocks that contain both odd and even entries.

1, 1, 1, 2, 4, 10, 25, 75, 225, 780, 2704, 10556, 41209, 178031, 769129, 3630780, 17139600, 87548580, 447195609, 2452523325, 13450200625, 78697155750, 460457244900, 2859220516290, 17754399678409, 116482516809889, 764214897046969, 5277304280371714

Offset: 0

Emeric Deutsch, Oct 31 2006

nonn

			a(4) = 4 because we have 13|24, 1|24|3, 13|2|4 and 1|2|3|4.

Alois P. Heinz, Table of n, a(n) for n = 0..500
A. Dzhumadil’daev and D. Yeliussizov, Path decompositions of digraphs and their applications to Weyl algebra, arXiv preprint arXiv:1408.6764v1, 2014. [Version 1 contained many references to the OEIS, which were removed in Version 2. - _N. J. A. Sloane_, Mar 28 2015]
Askar Dzhumadil’daev and Damir Yeliussizov, Walks, partitions, and normal ordering, Electronic Journal of Combinatorics, 22(4) (2015), #P4.10.

Cf. A000110, A088911, A124418, A124420, A124421, A124422, A124423, A152875, A274310.
Column k=0 of A124418 and of A363493.
Column k=2 of A275069.

Q[0]:=1: for n from 1 to 30 do if n mod 2 = 1 then Q[n]:=expand(t*diff(Q[n-1],t)+x*diff(Q[n-1],s)+x*diff(Q[n-1],x)+t*Q[n-1]) else Q[n]:=expand(x*diff(Q[n-1],t)+s*diff(Q[n-1],s)+x*diff(Q[n-1],x)+s*Q[n-1]) fi od: for n from 0 to 30 do Q[n]:=Q[n] od: seq(subs({t=1,s=1,x=0},Q[n]),n=0..30);
# second Maple program:
with(combinat):
a:= n-> bell(floor(n/2))*bell(ceil(n/2)):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 23 2013

a[n_] := BellB[Floor[n/2]]*BellB[Ceiling[n/2]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 20 2015, after Alois P. Heinz *)

a(n) = Q[n](1,1,0), where the polynomials Q[n]=Q[n](t,s,x) are defined by Q[0]=1; Q[n]=t*dQ[n-1]/dt + x*dQ[n-1]/ds + x*dQ[n-1]/dx + t*Q[n-1] if n is odd and Q[n]=x*dQ[n-1]/dt + s*dQ[n-1]/ds + x*dQ[n-1]/dx + s*Q[n-1] if n is even.
a(n) = A000110(floor(n/2)) * A000110(ceiling(n/2)). - Alois P. Heinz, Oct 23 2013
a(n) mod 2 = A088911(n). - Alois P. Heinz, Jun 06 2023

A274581 Number T(n,k) of set partitions of [n] with alternating parity of elements and exactly k blocks; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 5, 7, 4, 1, 0, 1, 7, 14, 12, 5, 1, 0, 1, 11, 30, 33, 19, 6, 1, 0, 1, 15, 57, 84, 62, 27, 7, 1, 0, 1, 23, 119, 222, 204, 108, 37, 8, 1, 0, 1, 31, 224, 545, 627, 409, 169, 48, 9, 1, 0, 1, 47, 460, 1425, 2006, 1558, 763, 254, 61, 10, 1

Offset: 0

Alois P. Heinz, Jun 29 2016

			T(5,1) = 1: 12345.
T(5,2) = 5: 1234|5, 123|45, 12|345, 145|23, 1|2345.
T(5,3) = 7: 123|4|5, 12|34|5, 12|3|45, 1|234|5, 145|2|3, 1|2|345, 1|23|45.
T(5,4) = 4: 12|3|4|5, 1|23|4|5, 1|2|34|5, 1|2|3|45.
T(5,5) = 1: 1|2|3|4|5.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,  1;
  0, 1,  2,   1;
  0, 1,  3,   3,   1;
  0, 1,  5,   7,   4,   1;
  0, 1,  7,  14,  12,   5,   1;
  0, 1, 11,  30,  33,  19,   6,   1;
  0, 1, 15,  57,  84,  62,  27,   7,  1;
  0, 1, 23, 119, 222, 204, 108,  37,  8, 1;
  0, 1, 31, 224, 545, 627, 409, 169, 48, 9, 1;
  ...

Alois P. Heinz, Rows n = 0..35, flattened
Wikipedia, Partition of a set

Columns k=0-10 give: A000007, A057427, A052955(n-2) for n>1, A305777, A305778, A305779, A305780, A305781, A305782, A305783, A305784.
Diagonals include A000012, A001477, A077043.
Row sums give A274547.
T(n,ceiling(n/2)) gives A305785.
Cf. A124419, A274310 (parities alternate within blocks), A305823.

b:= proc(l, i, t) option remember; `if`(l=[], x,
     `if`(l[1]=t, 0, expand(x*b(subsop(1=[][], l), 1, 1-t)
       ))+add(`if`(l[j]=t, 0, b(subsop(j=[][], l), j, 1-t)
       ), j=i..nops(l)))
    end:
T:= n-> `if`(n=0, 1, (p-> seq(coeff(p, x, j), j=0..n))(
         b([seq(irem(i, 2), i=2..n)], 1$2))):
seq(T(n), n=0..12);

b[l_, i_, t_] := b[l, i, t] = If[l == {}, x, If[l[[1]] == t, 0, Expand[x*b[Rest[l], 1, 1 - t]]] + Sum[If[l[[j]] == t, 0, b[Delete[l, j], j, 1 - t]], {j, i, Length[l]}]];
T[n_] := If[n==0, {1}, Function[p, Table[Coefficient[p, x, j], {j, 0, n}]][ b[Table[Mod[i, 2], {i, 2, n}], 1, 1]]];
Flatten[Table[T[n], {n, 0, 12}]] (* Jean-François Alcover, May 27 2018, from Maple *)

Sum_{k=0..n} k * T(n,k) = A305823(n).

A246117 Number of parity preserving permutations of the set {1,2,...,n} with exactly k cycles.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 2, 5, 4, 1, 0, 4, 12, 13, 6, 1, 0, 12, 40, 51, 31, 9, 1, 0, 36, 132, 193, 144, 58, 12, 1, 0, 144, 564, 904, 769, 376, 106, 16, 1, 0, 576, 2400, 4180, 3980, 2273, 800, 170, 20, 1, 0, 2880, 12576, 23300, 24080, 15345, 6273, 1650, 270, 25, 1

Offset: 1

Peter Bala, Aug 14 2014

An analog of the Stirling numbers of the first kind, A008275.
A permutation p of the set {1,2,...,n} is called a parity-preserving permutation if p(i) = i (mod 2) for i = 1,2,...,n. The set of all such permutations forms a subgroup of order A010551 of the symmetric group on n letters. This triangle gives the number of parity preserving permutations of the set {1,2,...,n} with exactly k cycles. An example is given below.
If we write a parity-preserving permutation p in one line notation as ( p(1) p(2) p(3)... p(n) ) then the first entry p(1) is odd and thereafter the entries alternate in parity. Thus the permutation p belongs to the set of parity-alternate permutations studied by Tanimoto.
The row generating polynomials form the polynomial sequence x, x^2, x^2*(x + 1), x^2*(x + 1)^2, x^2*(x + 1)^2*(x + 2), x^2*(x + 1)^2*(x + 2)^2, .... Except for differences in offset, this triangle is the Galton array G(floor(n/2),1) in the notation of Neuwirth with inverse array G(-floor(k/2),1). See A246118 for the unsigned version of the inverse array.
From Peter Bala, Apr 12 2018: (Start)
In the cycle decomposition of a parity preserving permutation, the entries in a given cycle are either all even or all odd. Define T(n,k,i), 1 <= i <= k-1, (a refinement of the table number T(n,k)) to be the number of parity preserving permutations of the set {1,2,...,n} with exactly k cycles and with i of the cycles having all even entries. Clearly, T(n,k) = Sum_{i = 1..k-1} T(n,k,i).
A simple combinatorial argument (cf. Dzhumadil'daev and Yeliussizov, Proposition 5.3) gives the recurrences
T(2*n,k,i) = T(2n-1,k-1,i-1) + (n-1)*T(2*n-1,k,i) and
T(2*n+1,k,i) = T(2*n,k-1,i) + n*T(2*n,k,i).
The solution to these recurrences for n >= 1 is T(2*n,k,i) = S1(n,i)*S1(n,k-i) and T(2*n+1,k,i) = S1(n,i)*S1(n+1,k-i), where S1(n,k) = |A008275(n,k)| denotes the (unsigned) Stirling cycle numbers of the first kind. Kotesovec's formula for T(n,k) below follows immediately from this. Cf. A274310. (End)
Triangle of allowable Stirling numbers of the first kind (with a different offset). See Cai and Readdy, Table 4. - Peter Bala, Apr 14 2018

			Triangle begins
n\k| 1   2    3    4    5   6   7   8
= = = = = = = = = = = = = = = = = = =
1  | 1
2  | 0   1
3  | 0   1    1
4  | 0   1    2    1
5  | 0   2    5    4    1
6  | 0   4   12   13    6   1
7  | 0  12   40   51   31   9   1
8  | 0  36  132  193  144  58  12  1
...
n = 5: The 12 parity-preserving permutations of S_5 and their cycle structure are shown in the table below.
= = = = = = = = = = = = = = = = = = = = = = = = = =
Parity-preserving      Cycle structure     # cycles
permutation
= = = = = = = = = = = = = = = = = = = = = = = = = =
54123                   (153)(24)              2
34521                   (135)(24)              2
34125                   (13)(24)(5)            3
14523                   (1)(24)(35)            3
32541                   (135)(2)(4)            3
52143                   (153)(2)(4)            3
54321                   (15)(24)(3)            3
32145                   (13)(2)(4)(5)          4
14325                   (1)(24)(3)(5)          4
12543                   (1)(2)(35)(4)          4
52341                   (15)(2)(3)(4)          4
12345                   (1)(2)(3)(4)(5)        5
= = = = = = = = = = = = = = = = = = = = = = = = = =
This gives row 5 as [2, 5, 4, 1] with generating function 2*x^2 + 5*x^3 + 4*x^4 + x^5 = ( x*(x + 1) )^2 * (x + 2).

Y. Cai and M. Readdy, Negative q-Stirling numbers, arXiv:1506.03249 [math.CO], 2015.
A. Dzhumadil'daev and D. Yeliussizov, Walks, partitions, and normal ordering, Electronic Journal of Combinatorics, 22(4) (2015), #P4.10.
E. Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 (2001) 33-51.
Shinji Tanimoto, Alternate Permutations and Signed Eulerian Numbers, arXiv:math/0612135 [math.CO], 2006; Ann. Comb. 14 (2010), 355.

A002620 (1st subdiagonal), A008275, A010551 (row sums and column k = 2), A125300, A203151 (column k = 3), A203246 (2nd subdiagonal), A246118 (unsigned matrix inverse).

Cf. A129256, A187235, A274310.

A246117 := proc(n,k)
    if n = k then
        1;
    elif k <= 1 or k > n then
        0;
    else
        floor((n-1)/2)*procname(n-1,k)+procname(n-1,k-1) ;
    end if;
end proc:
seq(seq(A246117(n,k),k=1..n),n=1..8) ; # R. J. Mathar, Oct 01 2016

Flatten[{1,Rest[Table[Table[(-1)^(n-k) * Sum[StirlingS1[Floor[(n+1)/2],j] * StirlingS1[Floor[n/2],k-j],{j,1,k-1}],{k,1,n}],{n,1,12}]]}] (* Vaclav Kotesovec, Feb 09 2015 *)

Recurrence equations: T(1,1) = 1, T(n,1) = 0 for n >= 2; T(n,k) = 0 for k > n; otherwise T(n+1,k) = floor(n/2)*T(n,k) + T(n,k-1).
Row generating polynomials R(n,x): R(2*n,x) = ( x*(x + 1)*...*(x + n - 1) )^2; R(2*n + 1,x) = R(2*n,x)*(x + n) with the convention R(0,x) = 1.
Row sums: A010551; Column 3: A203151;
First subdiagonal: A002620; 2nd subdiagonal: A203246.
T(n,k) = (-1)^(n-k) * Sum_{j=1..k-1} Stirling1(floor((n+1)/2),j) * Stirling1(floor(n/2),k-j), for k>1. - Vaclav Kotesovec, Feb 09 2015

A274547 Number of set partitions of [n] with alternating parity of elements.

Original entry on oeis.org

1, 1, 2, 4, 8, 18, 40, 101, 254, 723, 2064, 6586, 21143, 74752, 266078, 1029983, 4013425, 16843526, 71136112, 321150717, 1458636308, 7038678613, 34161890155, 175261038904, 904125989974, 4909033438008, 26795600521492, 153376337926066, 882391616100249

Offset: 0

Alois P. Heinz, Jun 27 2016

nonn

			a(5) = 18: 12345, 1234|5, 123|45, 123|4|5, 12|345, 12|34|5, 12|3|45, 12|3|4|5, 145|23, 1|2345, 1|234|5, 1|23|45, 1|23|4|5, 145|2|3, 1|2|345, 1|2|34|5, 1|2|3|45, 1|2|3|4|5.
a(6) = 40: 123456, 12345|6, 1234|56, 1234|5|6, 123|456, 123|45|6, 123|4|56, 123|4|5|6, 1256|34, 12|3456, 12|345|6, 12|34|56, 12|34|5|6, 1256|3|4, 12|3|456, 12|3|45|6, 12|3|4|56, 12|3|4|5|6, 145|236, 145|23|6, 1|23456, 1|2345|6, 1|234|56, 1|234|5|6, 1|23|456, 1|23|45|6, 1|23|4|56, 1|23|4|5|6, 145|2|36, 145|2|3|6, 1|256|34, 1|2|3456, 1|2|345|6, 1|2|34|56, 1|2|34|5|6, 1|256|3|4, 1|2|3|456, 1|2|3|45|6, 1|2|3|4|56, 1|2|3|4|5|6.

Alois P. Heinz, Table of n, a(n) for n = 0..36
Wikipedia, Partition of a set

Row sums of A274581.
Cf. A124419, A274310 (parities alternate within blocks), A363519.
Column k=2 of A274859.

b:= proc(l, i, t) option remember; `if`(l=[], 1, add(`if`(l[j]=t,
       b(subsop(j=[][], l), j, 1-t), 0), j=[1, $i..nops(l)]))
    end:
a:= n-> b([seq(irem(i, 2), i=2..n)], 1, 0):
seq(a(n), n=0..25);

b[l_, i_, t_] := b[l, i, t] = If[l == {}, 1, Sum[If[l[[j]] == t, b[ReplacePart[l, j -> Sequence[]], j, 1-t], 0], {j, Prepend[Range[i, Length[l]], 1]}]]; a[n_] := b[Table[Mod[i, 2], {i, 2, n}], 1, 0]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 15 2017, translated from Maple *)

a(n) = Sum_{k=0..n} A274581(n,k).

a(n) = A363519(n,max(0,n-1)). - Alois P. Heinz, Jun 07 2023

A384968 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete bipartite graph using exactly k interchangeable colors, 2 <= k <= 2*n.

Original entry on oeis.org

1, 1, 2, 1, 1, 6, 11, 6, 1, 1, 14, 61, 86, 50, 12, 1, 1, 30, 275, 770, 927, 530, 150, 20, 1, 1, 62, 1141, 5710, 12160, 12632, 6987, 2130, 355, 30, 1, 1, 126, 4571, 38626, 134981, 228382, 209428, 110768, 34902, 6580, 721, 42, 1, 1, 254, 18061, 248766, 1367310, 3553564, 4989621, 4093126, 2061782, 655788, 132958, 16996, 1316, 56, 1

Offset: 1

Andrew Howroyd, Jun 18 2025

Permuting the colors does not change the coloring. T(n,k) is the number of ways to partition the vertices into k independent sets.

			Triangle begins (n >= 1, k >= 2):
  1;
  1,  2,    1;
  1,  6,   11,    6,     1;
  1, 14,   61,   86,    50,    12,    1;
  1, 30,  275,  770,   927,   530,  150,   20,   1;
  1, 62, 1141, 5710, 12160, 12632, 6987, 2130, 355, 30, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..2500 (rows 1..50)
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Eric Weisstein's World of Mathematics, Vertex Coloring.

Row sums are A001247.
Columns k=2..5 are A000012, A000918, A384980, A384981.
Cf. A008277, A212084, A274310.

T(n,k) = sum(j=1, k-1, stirling(n,j,2)*stirling(n,k-j,2))
for(n=1, 7, print(vector(2*n-1,k,T(n,k+1))))

T(n,k) = Sum_{j=1..k-1} Stirling2(n,j)*Stirling2(n,k-j).

T(n,k) = A274310(2*n-1, k-1).

cp's OEIS Frontend

A124419 Number of partitions of the set {1,2,...n} having no blocks that contain both odd and even entries.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A274581 Number T(n,k) of set partitions of [n] with alternating parity of elements and exactly k blocks; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246117 Number of parity preserving permutations of the set {1,2,...,n} with exactly k cycles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A274547 Number of set partitions of [n] with alternating parity of elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A384968 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete bipartite graph using exactly k interchangeable colors, 2 <= k <= 2*n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula