A247651 Maximum number of binary strings of length 2n obtained from a partition of n.

1, 2, 3, 12, 30, 60, 210, 840, 2520, 7560, 27720, 83160, 240240, 840840, 2702700, 10810800, 36756720, 122522400, 465585120, 1551950400, 4888643760, 19554575040, 74959204320, 257002986240, 936990054000, 3480248772000, 11745839605500, 40477970332800, 146732642456400, 524045151630000

Offset: 0

Author

Andrei Cretu and Yuri Dimitrov, Oct 03 2014

Keywords

• nonn

Comments

The number of different binary strings of length 2n that can be constructed with an equal number (n) of 0's and 1's, based on a given partition of the 0's (or 1's) into uninterrupted runs, can be written as Nseq(n,partition)=(n+1)!/(Prod_j(m_j!)(n-m+1)!) where m is the number of partition members (total number of runs of 0's or 1's); and m_j is the multiplicity of runs of length j of 0's (or 1's) (j=positive integer).

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

Prod_j(m_j!)(n-m+1)! becomes n! at the extremes (finest partition of n, m=n -- coarsest partition of n, m=1). Nseq (n,partition) is in that sense a relative measure of the complexity of the partition and the associated binary strings. a(n) is the number of strings obtained based on the partition of n that maximizes Nseq(n,partition).

Examples

			n=0 gives the empty string.
n=1 and the only possible partition generate 01 and 10.
For n=2, both possible partitions generate 3 strings (0011,0110 and 1100, and respectively 0101, 1001 and 1010, based on runs of 1's).
For n=3, the optimal partition is {1,2}, generating 12 strings (based on runs of 1's: 001011, 001101, 010011, 010110, 011001, 011010, 100011, 100110, 101100, 110001, 110010, 110100).
		

Crossrefs

Cf. A025560, A130760.

Programs

Mathematica

nseq[p_]:=FactorialPower[Total[p]+1,Length[p]]/Apply[Times,Map[Factorial[Count[p,#1]]&,Range[Max[Length[p]]]]];
a[n_]:=Max[Map[nseq,IntegerPartitions[n]]]
Table[a[n],{n,0,20}] (* after A130670 *)

Formula

a(n) = (n+1)*A130760(n).

a(n) = Max[(n+1)!/(Prod_j(m_j!)(n-m+1)!)] over all partitions of n.

Extensions

More terms from Michel Marcus, May 19 2025