login
Integer partitions interpreted as binary numbers.
21

%I #116 Dec 09 2021 12:17:24

%S 0,1,3,5,7,11,15,21,23,27,31,43,47,55,63,85,87,91,95,111,119,127,171,

%T 175,183,191,219,223,239,255,341,343,347,351,367,375,383,439,447,479,

%U 495,511,683,687,695,703,731,735,751,767,879,887,895,959,991,1023,1365,1367,1371,1375,1391

%N Integer partitions interpreted as binary numbers.

%C The 2^(n-1) compositions of n correspond to binary numbers, and the partitions of n can be seen as compositions with addends ordered by size, so they also correspond to binary numbers.

%C The finite sequence for partitions of n (ordered by size) is the beginning of the sequence for partitions of n+1, which leads to an infinite sequence.

%C From _Tilman Piesk_, Jan 30 2016: (Start)

%C It makes sense to regard the positive values as a triangle with row lengths A002865(n) and row numbers n>=2. In this triangle row n contains all partitions of n with non-one addends only. See link "Triangle with Young diagrams".

%C This sequence contains all binary palindromes with m runs of n ones separated by single zeros. They are ordered in the array A249544. All the rows and columns of this array are subsequences of this sequence, notably its top row (A000225, the powers of two minus one).

%C Sequences by _Omar E. Pol_: The "triangle" A210941 defines the same sequence of partitions. Its n-th row shows the non-one addends of the n-th partition. There are A194548(n) of them, and A141285(n) is the largest among them. (The "triangle" A210941 does not actually form a triangle, but A210941 and A141285 do.) Note that the offset of these sequences is 1 and not 0.

%C (End)

%C Numbers whose binary representation has runs of '1's of weakly increasing length (with trailing '0's (introducing a run of length 0) forbidden, i.e., only odd terms beyond 0). - _M. F. Hasler_, May 14 2020

%H Tilman Piesk, <a href="/A194602/b194602.txt">Table of n, a(n) for n = 0..8348</a>

%H Tilman Piesk, <a href="/A194602/a194602.txt">Same table with binary strings and non-one addends</a>

%H Tilman Piesk, <a href="http://paste.watchduck.net/1602/intpart/A194602_fat.html">Triangle with Young diagrams</a> (n = 2..20).

%H Tilman Piesk, <a href="https://en.wikiversity.org/wiki/Integer_partitions">Integer partitions</a> and <a href="https://en.wikiversity.org/wiki/Permutations_and_partitions_in_the_OEIS">Permutations and partitions in the OEIS</a>

%H Tilman Piesk, <a href="http://pastebin.com/78QNvRPr">Python functions</a>, keynum_to_valnum(n) = a(n), valnum_to_keynum(a(n)) = n.

%H Li-yao Xia, <a href="/A194602/a194602_1.txt">Identities for A194602</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a( A000041(n)-1 ) = A000225(n-1) for n>=1. - _Tilman Piesk_, Apr 16 2012

%F a( A000041(2n-1) ) = A002450(n) for n>=1. - _Tilman Piesk_, Apr 16 2012

%F a( A249543 ) = A249544. - _Tilman Piesk_, Oct 31 2014

%F a(n) = A228354(1+n) - 1. - _Antti Karttunen_, Dec 06 2021

%e From _Joerg Arndt_, Nov 17 2012: (Start)

%e With leading zeros included, the first A000041(n) terms correspond to the list of partitions of n as nondecreasing compositions in lexicographic order.

%e For example, the first A000041(10)=42 terms correspond to the partitions of 10 as follows (dots for zeros in the binary expansions):

%e [ n] binary(a(n)) a(n) partition

%e [ 0] .......... 0 [ 1 1 1 1 1 1 1 1 1 1 ]

%e [ 1] .........1 1 [ 1 1 1 1 1 1 1 1 2 ]

%e [ 2] ........11 3 [ 1 1 1 1 1 1 1 3 ]

%e [ 3] .......1.1 5 [ 1 1 1 1 1 1 2 2 ]

%e [ 4] .......111 7 [ 1 1 1 1 1 1 4 ]

%e [ 5] ......1.11 11 [ 1 1 1 1 1 2 3 ]

%e [ 6] ......1111 15 [ 1 1 1 1 1 5 ]

%e [ 7] .....1.1.1 21 [ 1 1 1 1 2 2 2 ]

%e [ 8] .....1.111 23 [ 1 1 1 1 2 4 ]

%e [ 9] .....11.11 27 [ 1 1 1 1 3 3 ]

%e [10] .....11111 31 [ 1 1 1 1 6 ]

%e [11] ....1.1.11 43 [ 1 1 1 2 2 3 ]

%e [12] ....1.1111 47 [ 1 1 1 2 5 ]

%e [13] ....11.111 55 [ 1 1 1 3 4 ]

%e [14] ....111111 63 [ 1 1 1 7 ]

%e [15] ...1.1.1.1 85 [ 1 1 2 2 2 2 ]

%e [16] ...1.1.111 87 [ 1 1 2 2 4 ]

%e [17] ...1.11.11 91 [ 1 1 2 3 3 ]

%e [18] ...1.11111 95 [ 1 1 2 6 ]

%e [19] ...11.1111 111 [ 1 1 3 5 ]

%e [20] ...111.111 119 [ 1 1 4 4 ]

%e [21] ...1111111 127 [ 1 1 8 ]

%e [22] ..1.1.1.11 171 [ 1 2 2 2 3 ]

%e [23] ..1.1.1111 175 [ 1 2 2 5 ]

%e [24] ..1.11.111 183 [ 1 2 3 4 ]

%e [25] ..1.111111 191 [ 1 2 7 ]

%e [26] ..11.11.11 219 [ 1 3 3 3 ]

%e [27] ..11.11111 223 [ 1 3 6 ]

%e [28] ..111.1111 239 [ 1 4 5 ]

%e [29] ..11111111 255 [ 1 9 ]

%e [30] .1.1.1.1.1 341 [ 2 2 2 2 2 ]

%e [31] .1.1.1.111 343 [ 2 2 2 4 ]

%e [32] .1.1.11.11 347 [ 2 2 3 3 ]

%e [33] .1.1.11111 351 [ 2 2 6 ]

%e [34] .1.11.1111 367 [ 2 3 5 ]

%e [35] .1.111.111 375 [ 2 4 4 ]

%e [36] .1.1111111 383 [ 2 8 ]

%e [37] .11.11.111 439 [ 3 3 4 ]

%e [38] .11.111111 447 [ 3 7 ]

%e [39] .111.11111 479 [ 4 6 ]

%e [40] .1111.1111 495 [ 5 5 ]

%e [41] .111111111 511 [ 10 ]

%e (End)

%t lim = 12;

%t Sort[FromDigits[Reverse@ #, 2] & /@

%t Map[If[Length@ # == 0, {0}, Flatten@ Most@ #] &@

%t Riffle[#, Table[0, Length@ #]] &,

%t Map[Table[1, # - 1] &,

%t Sort@ IntegerPartitions@ lim /. 1 -> Nothing, {2}]]]

%t (* _Michael De Vlieger_, Feb 14 2016 *)

%o (PARI) isA194602(n) = if(!n,1,if(!(n%2),0,my(prl=0,rl=0); while(n, if(0==(n%2),if((prl && rl>prl)||0==(n%4), return(0)); prl=rl; rl=0, rl++); n >>= 1); ((0==prl)||(rl<=prl)))); \\ - _Antti Karttunen_, Dec 06 2021

%Y Cf. A000041 (partition numbers).

%Y Cf. A002865 (row lengths).

%Y Cf. A002450, A000225 (subsequences).

%Y Cf. A249544 (rows and columns are subsequences).

%Y Cf. A210941, A194548, A141285, A228354, A326956.

%K nonn,tabf

%O 0,3

%A _Tilman Piesk_, Aug 30 2011

%E Comments edited by _Li-yao Xia_, May 13 2014

%E Incorrect PARI-program removed by _Antti Karttunen_, Dec 09 2021