login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A250029 Maximum number of binary strings with symmetrically partitioned n 1's and n 0's, counted up to isomorphism. 0
1, 1, 1, 4, 9, 16, 36, 144, 400, 900, 3600, 11025, 28224, 78400, 254016, 705600, 2286144, 6350400, 25401600, 85377600, 250905600, 768398400, 3073593600, 10600761600, 32464832400, 129859329600, 456536705625 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

The number of binary strings, counted up to isomorphism, that can be constructed by taking an equal number (n) of 0's and 1's and partitioning both the 0's and the 1's into m runs using the same partition, can be written as:

dualseq[partition[n]]=m!^2/(Prod_j(m_j!))^2

where m_j is the multiplicity of runs of length j.

The numbers satisfy the relations Sum_j(m_j)=m, Sum_j(j*m_j)=n.

The strings obtained in this manner are a subset of those in A247651.

Both the finest and coarsest partitions of n minimize dualseq[partition[n]]. In this sense, dualseq[partition[n]] is another relative measure of the complexity of the partition and the associated binary strings.

a[n] is the number of strings, counted up to isomorphism, that can be generated based on the partition that maximizes dualseq[partition[n]].

LINKS

Table of n, a(n) for n=0..26.

FORMULA

a[n]=Max[m!^2/(Prod_j(m_j!))^2] where Sum_j(m_j)=m, Sum_j(j*m_j)=n, over all partitions of n.

EXAMPLE

n=0 gives the empty string.

n=1 and the only possible partition generate 01 (and the isomorphic 10).

For n=2, both possible partitions generate, up to isomorphism, 1 string, 0011 (1100), and respectively 0101 (1010).

For n=3, the optimal partition is {1,2}, generating, up to isomorphism, 4 strings: 001011 (110100), 001101 (110010), 010011 (101100) and 011001 (100110).

For n=4, the optimal partition is {1,1,2}, generating, up to isomorphism, 9 strings: 00101011 (11010100), 00101101 (11010010), 00110101 (11001010), 01001011 (10110100), 01001101 (10110010), 01010011 (10101100), 01011001 (10100110), 01100101 (10011010) and 01101001 (10010110).

MATHEMATICA

dualseq[p_]:=Factorial[Length[p]]^2/Apply[Times, Map[Factorial[Count[p, #1]]&, Range[Max[Length[p]]]]]^2

a[n_]:=Max[Map[dualseq, IntegerPartitions[n]]]

Table[a[n], {n, 0, 25}] (* after A130670 *)

CROSSREFS

Cf. A247651, A046952, A092266, A136404, A176471, A065886.

Sequence in context: A076967 A233247 A231180 * A111378 A106313 A219355

Adjacent sequences:  A250026 A250027 A250028 * A250030 A250031 A250032

KEYWORD

nonn

AUTHOR

Andrei Cretu, Nov 11 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 23 13:55 EDT 2017. Contains 292358 sequences.