login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A247651 Maximum number of binary strings of length 2n obtained from a partition of n. 1

%I #45 Oct 23 2014 20:54:16

%S 1,2,3,12,30,60,210,840,2520,7560,27720,83160,240240,840840,2702700,

%T 10810800,36756720,122522400,465585120,1551950400,4888643760,

%U 19554575040,74959204320,257002986240,936990054000,3480248772000

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

%C 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:

%C m is the number of partition members (total number of runs of 0's or 1's);

%C and m_j is the multiplicity of runs of length j of 0's (or 1's) (j=positive integer).

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

%C 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).

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

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

%e n=0 gives the empty string.

%e n=1 and the only possible partition generate 01 and 10.

%e 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).

%e 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).

%t nseq[p_]:=FactorialPower[Total[p]+1,Length[p]]/Apply[Times,Map[Factorial[Count[p,#1]]&,Range[Max[Length[p]]]]];

%t a[n_]:=Max[Map[nseq,IntegerPartitions[n]]]

%t Table[a[n],{n,0,20}] (* after A130670 *)

%Y Cf. A025560, A130760.

%K nonn

%O 0,2

%A _Andrei Cretu_ and Yuri Dimitrov, Oct 03 2014

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 08:53 EDT 2024. Contains 371268 sequences. (Running on oeis4.)