A327913 -id:A327913 - cp's OEIS frontend

A318396 Number of pairs of integer partitions (y, v) of n such that there exists a pair of set partitions of {1,...,n} with meet {{1},...,{n}}, the first having block sizes y and the second v.

1, 1, 3, 6, 15, 28, 64, 116, 238, 430, 818, 1426, 2618, 4439, 7775, 12993, 22025, 35946, 59507, 95319, 154073, 243226, 385192, 598531, 933096, 1429794, 2193699, 3322171, 5027995, 7524245, 11253557, 16661211, 24637859, 36130242, 52879638, 76830503, 111422013, 160505622

Offset: 0

Gus Wiseman, Aug 25 2018

nonn

A multiset is normal if it spans an initial interval of positive integers, and strongly normal if in addition it has weakly decreasing multiplicities. a(n) is also the number of combinatory separations (see A269134 for definition) of strongly normal multisets of size n into normal sets.
From Andrew Howroyd, Oct 31 2019: (Start)
Also, the number of distinct unordered row and column sums of binary matrices without empty columns or rows and with a total of n ones. Only matrices in which both row and columns sums are weakly increasing need to be considered.
By the Gale-Ryser theorem this is equivalent to the number of pairs of integer partitions (y,v) of n with y dominating v. (End)

			The a(4) = 15 pairs of integer partitions:
     4, 1111
    22, 22
    22, 211
    22, 1111
    31, 211
    31, 1111
   211, 22
   211, 31
   211, 211
   211, 1111
  1111, 4
  1111, 22
  1111, 31
  1111, 211
  1111, 1111
The a(4) = 15 combinatory separations:
  1111<={1,1,1,1}
  1112<={1,1,12}
  1112<={1,1,1,1}
  1122<={12,12}
  1122<={1,1,12}
  1122<={1,1,1,1}
  1123<={1,123}
  1123<={12,12}
  1123<={1,1,12}
  1123<={1,1,1,1}
  1234<={1234}
  1234<={1,123}
  1234<={12,12}
  1234<={1,1,12}
  1234<={1,1,1,1}

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

Cf. A000041, A000110, A001247, A007716, A008277, A029894, A049311, A059849, A116540, A181939, A265947, A269134, A318393, A318394, A327913.

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[Select[Union@@Table[{m,Sort[normize/@#]}&/@mps[m],{m,strnorm[n]}],And@@UnsameQ@@@#[[2]]&]],{n,6}]

IsDom(p,q)=if(#q<#p, 0, my(s=0,t=0); for(i=0, #p-1, s+=p[#p-i]; t+=q[#q-i]; if(t>s, return(0))); 1)
a(n)={if(n<1, n==0, my(s=0); forpart(p=n, forpart(q=n, s+=IsDom(p,q), [1, p[#p]], [#p, n])); s)} \\ Andrew Howroyd, Oct 31 2019

\\ faster version.
a(n)={local(Cache=Map());
  my(recurse(b, c, s, t)=my(hk=Vecsmall([b, c, s, t]), z);
     if(!mapisdefined(Cache, hk, &z),
       z = if(s, sum(i=1, min(s, b), sum(j=1, min(t-s+i, c), self()(i, j, s-i, t-j))),
           if(t, sum(j=1, min(t, c), self()(b, j, s, t-j)), 1));
       mapput(Cache, hk, z)); z);
  recurse(n, n, n, n)
} \\ Andrew Howroyd, Oct 31 2019

Terms a(9) and beyond from Andrew Howroyd, Oct 31 2019

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

cp's OEIS Frontend

A318396 Number of pairs of integer partitions (y, v) of n such that there exists a pair of set partitions of {1,...,n} with meet {{1},...,{n}}, the first having block sizes y and the second v.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

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