A318396 -id:A318396 - cp's OEIS frontend

A269134 Number of combinatory separations of normal multisets of weight n.

1, 4, 14, 57, 223, 948, 3940, 16994, 72964, 317959, 1385592, 6085763, 26738139, 117939291, 520553999, 2301781692, 10181786176, 45074744448, 199558036891, 883670342156, 3912320450786

Offset: 1

Gus Wiseman, Feb 20 2016

A multiset is normal if it spans an initial interval of positive integers. The type of a multiset of integers is the unique normal multiset that has the same sequence of multiplicities when its entries are taken in increasing order. For example the type of 335556 is 112223.
If and only if there exists a multiset partition p whose multiset union has type h and where g = {g_1,...,g_n} is the multiset of types of the blocks of p, there exists a *combinatory separation* which is regarded as a multi-arrow p:h<=g. For example 1122<={12,11} is *not* a combinatory separation because one cannot partition a multiset of type 1122 into two blocks where one block has two distinct elements and the other block has two equal elements. Normal multisets N and combinatory separations S comprise a multi-order (N,S). The value of a(n) is the total number of *distinct* combinatory separations h<=g where h has weight n.
The term "combinatory separation" is inspired by MacMahon's inscrutable "Combinatory Analysis" (1915) which states: "A partition of any number is "separated" into "separates" by writing down a set [sic] of partitions, each partition in its own brackets, from left to right so that when all of the parts of these partitions are assembled in a single bracket, the partition separated is reproduced."

			For a(3) the 14 distinct combinatory separations grouped according to head are: 111<={111}, 111<={1,11}, 111<={1,1,1}; 112<={112}, 112<={1,11}, 112<={1,12}, 112<={1,1,1}; 122<={122}, 122<={1,11}, 122<={1,12}, 122<={1,1,1}; 123<={123}, 123<={1,12}, 123<={1,1,1}.
Note that in this enumeration the two multiset partitions {{1},{2,3}}:123<={1,12} and {{1,2},{3}}:123<={1,12} do not represent distinct multi-arrows and consequently are counted only once, whereas the two multiset partitions {{1},{1,2}}:112<={1,12} and {{1,2},{2}}:122<={1,12} are counted separately even though they have the same multiset of block-types.

Martin Fuller, C++ program
Gus Wiseman, Comcategories and Multiorders (pdf version)

Cf. A255906 (multiset partitions of normal multisets of weight n), A096443 (multiset partitions of multiset class representatives), A007716 (non-isomorphic multiset partitions of weight n).

Cf. A034691, A318396, A318559, A318560, A318562, A318563, A318567.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
normize[m_]:=m/.Rule@@@Table[{Union[m][[i]],i},{i,Length[Union[m]]}];
Table[Length[Union@@Table[{m,Sort[normize/@#]}&/@mps[m],{m,allnorm[n]}]],{n,7}] (* Gus Wiseman, Aug 29 2018 *)

a(9) from Gus Wiseman, Aug 29 2018
a(10) from Robert Price, Sep 14 2018
a(11)-a(21) from Martin Fuller, Mar 22 2025

A321854 Irregular triangle where T(H(u),H(v)) is the number of ways to partition the Young diagram of u into vertical sections whose sizes are the parts of v, where H is Heinz number.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 2, 1, 0, 0, 0, 0, 1, 1, 3, 1, 0, 2, 0, 4, 1, 0, 0, 0, 3, 1, 0, 0, 0, 0, 0, 0, 1, 0, 2, 2, 5, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 4, 1, 0, 0, 0, 6, 0, 6, 1, 1, 3, 4, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Gus Wiseman, Nov 19 2018

Row n has length A000041(A056239(n)).

A vertical section is a partial Young diagram with at most one square in each row.

			Triangle begins:
  1
  1
  0  1
  1  1
  0  0  1
  0  2  1
  0  0  0  0  1
  1  3  1
  0  2  0  4  1
  0  0  0  3  1
  0  0  0  0  0  0  1
  0  2  2  5  1
  0  0  0  0  0  0  0  0  0  0  1
  0  0  0  0  0  4  1
  0  0  0  6  0  6  1
  1  3  4  6  1
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
  0  0  4 10  4  8  1
The 12th row counts the following partitions of the Young diagram of (211) into vertical sections (shown as colorings by positive integers):
  T(12,7) = 0:
.
  T(12,9) = 2:    1 2   1 2
                  1     2
                  2     1
.
  T(12,10) = 2:   1 2   1 2
                  2     1
                  2     1
.
  T(12,12) = 5:   1 2   1 2   1 2   1 2   1 2
                  3     2     3     1     3
                  3     3     2     3     1
.
  T(12,16) = 1:   1 2
                  3
                  4

Cf. A000085, A000110, A007016, A056239, A122111, A153452, A215366, A296188, A300121, A318396, A321719-A321731, A321737, A321738, A321742-A321765.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
ptnpos[y_]:=Position[Table[1,{#}]&/@y,1];
ptnverts[y_]:=Select[Rest[Subsets[ptnpos[y]]],UnsameQ@@First/@#&];
Table[With[{y=Reverse[primeMS[n]]},Table[Length[Select[spsu[ptnverts[y],ptnpos[y]],Sort[Length/@#]==primeMS[k]&]],{k,Sort[Times@@Prime/@#&/@IntegerPartitions[Total[primeMS[n]]]]}]],{n,18}]

A318559 Number of combinatory separations of the multiset of prime factors of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 3, 1, 7, 2, 2, 2, 8, 1, 2, 2, 7, 1, 3, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 8, 1, 2, 4, 11, 2, 3, 1, 4, 2, 3, 1, 15, 1, 2, 4, 4, 2, 3, 1, 12, 5, 2, 1, 8, 2, 2

Offset: 1

Gus Wiseman, Aug 28 2018

nonn

A multiset is normal if it spans an initial interval of positive integers. The type of a multiset is the unique normal multiset that has the same sequence of multiplicities when its entries are taken in increasing order. For example the type of 335556 is 112223. A (headless) combinatory separation of a multiset m is a multiset of normal multisets {t_1,...,t_k} such that there exist multisets {s_1,...,s_k} with multiset union m and such that s_i has type t_i for each i = 1...k.

			The a(60) = 8 combinatory separations of {2,2,3,5}:
  {1123},
  {1,112}, {1,123}, {11,12}, {12,12},
  {1,1,11}, {1,1,12},
  {1,1,1,1}.

Cf. A007716, A056239, A112798, A255906, A265947, A269134, A317533, A317791.

Cf. A318393, A318396, A318560, A318562, A318565, A318566, A318567.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
normize[m_]:=m/.Rule@@@Table[{Union[m][[i]],i},{i,Length[Union[m]]}];
Table[Length[Union[Sort/@Map[normize,mps[primeMS[n]],{2}]]],{n,100}]

A321737 Number of ways to partition the Young diagram of an integer partition of n into vertical sections.

Original entry on oeis.org

1, 1, 3, 9, 37, 152, 780, 3965, 23460, 141471, 944217, 6445643, 48075092, 364921557, 2974423953, 24847873439, 219611194148, 1987556951714, 18930298888792, 184244039718755, 1874490999743203, 19510832177784098, 210941659716920257, 2331530519337226199, 26692555830628617358

Offset: 0

Gus Wiseman, Nov 19 2018

nonn

A vertical section is a partial Young diagram with at most one square in each row. For example, a partition (shown as a coloring by positive integers) into vertical sections of the Young diagram of (322) is:
2 3
2
3

			The a(4) = 37 partitions into vertical sections of integer partitions of 4:
  1 2 3 4
.
  1 2 3   1 2 3   1 2 3   1 2 3
  4       3       2       1
.
  1 2   1 2   1 2   1 2   1 2   1 2   1 2
  3 4   2 3   3 2   1 3   1 2   3 1   2 1
.
  1 2   1 2   1 2   1 2   1 2   1 2   1 2   1 2   1 2   1 2
  3     3     2     3     2     1     1     3     2     1
  4     3     3     2     2     3     2     1     1     1
.
  1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
  2   2   2   2   2   1   1   2   2   2   2   1   1   2   1
  3   3   2   3   2   2   2   1   1   3   2   1   2   1   1
  4   3   3   2   2   3   2   3   2   1   1   2   1   1   1

Cf. A000110, A000258, A008277, A046682, A122111, A318396, A321728, A321729, A321730, A321731, A321738, A321854.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
ptnpos[y_]:=Position[Table[1,{#}]&/@y,1];
ptnverts[y_]:=Select[Rest[Subsets[ptnpos[y]]],UnsameQ@@First/@#&];
Table[Sum[Length[spsu[ptnverts[y],ptnpos[y]]],{y,IntegerPartitions[n]}],{n,6}]

a(11)-a(24) from Ludovic Schwob, Aug 28 2023

A318562 Number of combinatory separations of strongly normal multisets of weight n with strongly normal parts.

Original entry on oeis.org

1, 4, 10, 32, 80, 239, 605, 1670, 4251

Offset: 1

Gus Wiseman, Aug 29 2018

A multiset is normal if it spans an initial interval of positive integers, and strongly normal if in addition it has weakly decreasing multiplicities. The type of a multiset of integers is the unique normal multiset that has the same sequence of multiplicities when its entries are taken in increasing order. For example the type of 335556 is 112223.

A pair h<={g_1,...,g_k} is a combinatory separation iff there exists a multiset partition of h whose multiset of block-types is {g_1,...,g_k}. For example, the (headless) combinatory separations of the multiset 1122 are {1122}, {1,112}, {1,122}, {11,11}, {12,12}, {1,1,11}, {1,1,12}, {1,1,1,1}. This list excludes {12,11} because one cannot partition 1122 into two blocks where one block has two distinct elements and the other block has two equal elements.

			The a(3) = 10 combinatory separations:
  111<={111}
  111<={1,11}
  111<={1,1,1}
  112<={112}
  112<={1,11}
  112<={1,12}
  112<={1,1,1}
  123<={123}
  123<={1,12}
  123<={1,1,1}

Cf. A000041, A007716, A255906, A265947, A269134.

Cf. A317533, A317791, A318396, A318559, A318563, A318564, A318565, A318566.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
normize[m_]:=m/.Rule@@@Table[{Union[m][[i]],i},{i,Length[Union[m]]}];
strnormQ[m_]:=OrderedQ[Length/@Split[m],GreaterEqual];
Table[Length[Select[Union@@Table[{m,Sort[normize/@#]}&/@mps[m],{m,strnorm[n]}],And@@strnormQ/@#[[2]]&]],{n,6}]

A318563 Number of combinatory separations of strongly normal multisets of weight n.

Original entry on oeis.org

1, 4, 10, 33, 85, 272, 730, 2197, 6133

Offset: 1

Gus Wiseman, Aug 29 2018

A multiset is normal if it spans an initial interval of positive integers, and strongly normal if in addition it has weakly decreasing multiplicities. The type of a multiset of integers is the unique normal multiset that has the same sequence of multiplicities when its entries are taken in increasing order. For example the type of 335556 is 112223.

A pair h<={g_1,...,g_k} is a combinatory separation iff there exists a multiset partition of h whose multiset of block-types is {g_1,...,g_k}. For example, the (headless) combinatory separations of the multiset 1122 are {1122}, {1,112}, {1,122}, {11,11}, {12,12}, {1,1,11}, {1,1,12}, {1,1,1,1}. This list excludes {12,11} because one cannot partition 1122 into two blocks where one block has two distinct elements and the other block has two equal elements.

			The a(3) = 10 combinatory separations:
  111<={111}
  111<={1,11}
  111<={1,1,1}
  112<={112}
  112<={1,11}
  112<={1,12}
  112<={1,1,1}
  123<={123}
  123<={1,12}
  123<={1,1,1}

Cf. A000041, A007716, A255906, A265947, A269134.

Cf. A317533, A317791, A318396, A318559, A318562, A318564, A318565, A318566.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
normize[m_]:=m/.Rule@@@Table[{Union[m][[i]],i},{i,Length[Union[m]]}];
Table[Length[Union@@Table[{m,Sort[normize/@#]}&/@mps[m],{m,strnorm[n]}]],{n,7}]

A029894 Number of directed (or Gale-Ryser) graphical partitions: degree-vector pairs (in-degree, out-degree) for directed graphs (loops allowed) with n vertices; or possible ordered pair (row-sum, column-sum) vectors for a 0-1 matrix.

Original entry on oeis.org

1, 2, 7, 34, 221, 1736, 15584, 153228, 1611189, 17826202, 205282376, 2441437708, 29816628471, 372314544202, 4737438631001, 61264426341926, 803488037899349, 10668478221202710, 143203795004873285, 1940953294927992976, 26536578116407809962, 365653739580163294032

Offset: 0

torsten.sillke(AT)lhsystems.com

nonn

R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.

Andrew Howroyd, Table of n, a(n) for n = 0..30
Peter L. Erdos, I Miklós, Z Toroczkai, New classes of degree sequences with fast mixing swap Markov chain sampling, arXiv preprint arXiv:1601.08224 [math.CO], 2016.
Index entries for sequences related to graphical partitions

Main diagonal of A327913.

Cf. A000569, A004250, A004251, A029889, A318396.

\\ see A327913 for T(n,m)
for(n=0, 15, print1(T(n,n), ", ")) \\ Andrew Howroyd, Nov 01 2019

Calculated using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser.

a(n) = F(n, n, 0, n) where F(b, c, t, w) = Sum_{i=0..b} Sum_{j=ceiling((t+i)/w)..min(t+i, c)} F(i, j, t+i-j, w-1) for w > 0, F(b, c, 0, 0) = 1 and F(b, c, t, 0) = 0 for t > 0. - Andrew Howroyd, Nov 01 2019

"Loops allowed" added to the definition by Brendan McKay, Oct 20 2015

a(0)=1 prepended and terms a(12) and beyond from Andrew Howroyd, Oct 31 2019

A318567 Number of pairs (c, y) where c is an integer composition and y is an integer partition and y can be obtained from c by choosing a partition of each part, flattening, and sorting.

Original entry on oeis.org

1, 3, 8, 21, 54, 137, 343, 847, 2075, 5031, 12109, 28921, 68633, 161865, 379655

Offset: 1

Gus Wiseman, Aug 29 2018

Also the number of combinatory separations of normal multisets of weight n with constant parts. A multiset is normal if it spans an initial interval of positive integers. The type of a multiset is the unique normal multiset that has the same sequence of multiplicities when its entries are taken in increasing order. For example the type of 335556 is 112223. A pair h<={g_1,...,g_k} is a combinatory separation iff there exists a multiset partition of h whose multiset of block-types is {g_1,...,g_k}.

			The a(3) = 8 combinatory separations:
  111<={111}
  111<={1,11}
  111<={1,1,1}
  112<={1,11}
  112<={1,1,1}
  122<={1,11}
  122<={1,1,1}
  123<={1,1,1}

Cf. A000041, A007716, A011782, A034691, A255906, A265947, A269134.

Cf. A317533, A317791, A318396, A318559, A318560, A318562, A318565.

Table[Sum[Length[Union[Sort/@Join@@@Tuples[IntegerPartitions/@c]]],{c,Join@@Permutations/@IntegerPartitions[n]}],{n,30}]

A327913 Array read by antidiagonals: T(n,m) is the number of distinct unordered row and column sums of n X m binary matrices.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 7, 4, 1, 1, 5, 13, 13, 5, 1, 1, 6, 22, 34, 22, 6, 1, 1, 7, 34, 76, 76, 34, 7, 1, 1, 8, 50, 152, 221, 152, 50, 8, 1, 1, 9, 70, 280, 557, 557, 280, 70, 9, 1, 1, 10, 95, 482, 1264, 1736, 1264, 482, 95, 10, 1, 1, 11, 125, 787, 2630, 4766, 4766, 2630, 787, 125, 11, 1

Offset: 0

Andrew Howroyd, Oct 30 2019

Only matrices in which both row and columns sums are weakly increasing need to be considered. If order is also considered then the number of possibilities is given by A328887(n, m).

			Array begins:
=============================================
n\m | 0 1  2   3    4     5     6      7
----+----------------------------------------
  0 | 1 1  1   1    1     1     1      1 ...
  1 | 1 2  3   4    5     6     7      8 ...
  2 | 1 3  7  13   22    34    50     70 ...
  3 | 1 4 13  34   76   152   280    482 ...
  4 | 1 5 22  76  221   557  1264   2630 ...
  5 | 1 6 34 152  557  1736  4766  11812 ...
  6 | 1 7 50 280 1264  4766 15584  45356 ...
  7 | 1 8 70 482 2630 11812 45356 153228 ...
  ...
T(2,2) = 7. The following 7 matrices each have different row/column sums.
  [0 0]  [0 0]  [0 1]  [0 0]  [0 1]  [0 1]  [1 1]
  [0 0]  [0 1]  [1 0]  [1 1]  [0 1]  [1 1]  [1 1]

Andrew Howroyd, Table of n, a(n) for n = 0..1325
Manfred Krause, A simple proof of the Gale-Ryser theorem, American Mathematical Monthly, 1996.
Wikipedia, Gale-Ryser theorem

Main diagonal is A029894.
Cf. A028657 (nonequivalent binary n X m matrices).
Cf. A318396, A328887.

T(n,m)={local(Cache=Map());
  my(F(b, c, t, w)=my(hk=Vecsmall([b, c, t, w]), z);
     if(!mapisdefined(Cache, hk, &z),
       z = if(w&&c, sum(i=0, b, sum(j=ceil((t+i)/w), min(t+i, c), self()(i, j, t+i-j, w-1))), !t);
     mapput(Cache, hk, z)); z);
   F(n, n, 0, m)
}

# After PARI implementation.
from functools import cache
@cache
def F(b, c, t, w):
    if w == 0:
        return 1 if t == 0 else 0
    return sum(
        sum(
            F(i, j, t + i - j, w - 1)
            for j in range((t + i - 1) // w, min(t + i, c) + 1)
        )
        for i in range(b + 1)
    )
A327913 = lambda n, m: F(n, n, 0, m)
for n in range(10):
    print([A327913(n, m) for m in range(0, 8)]) # Peter Luschny, Apr 09 2021

cp's OEIS Frontend

A269134 Number of combinatory separations of normal multisets of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A321854 Irregular triangle where T(H(u),H(v)) is the number of ways to partition the Young diagram of u into vertical sections whose sizes are the parts of v, where H is Heinz number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A318559 Number of combinatory separations of the multiset of prime factors of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A321737 Number of ways to partition the Young diagram of an integer partition of n into vertical sections.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A318562 Number of combinatory separations of strongly normal multisets of weight n with strongly normal parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A318563 Number of combinatory separations of strongly normal multisets of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A029894 Number of directed (or Gale-Ryser) graphical partitions: degree-vector pairs (in-degree, out-degree) for directed graphs (loops allowed) with n vertices; or possible ordered pair (row-sum, column-sum) vectors for a 0-1 matrix.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A318567 Number of pairs (c, y) where c is an integer composition and y is an integer partition and y can be obtained from c by choosing a partition of each part, flattening, and sorting.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327913 Array read by antidiagonals: T(n,m) is the number of distinct unordered row and column sums of n X m binary matrices.

Views