A176572 Count the ones in the binary representation of the partitions of n; then add vertically yielding a triangular array T(n,k).

1, 2, 1, 3, 1, 2, 5, 1, 3, 3, 7, 1, 3, 4, 5, 11, 1, 4, 5, 7, 7, 15, 1, 4, 6, 8, 9, 11, 22, 1, 5, 7, 11, 10, 15, 15, 30, 1, 5, 9, 12, 13, 17, 19, 22, 42, 1, 6, 10, 16, 15, 22, 21, 29, 30, 56, 1, 6, 12, 18, 19, 25, 26, 32, 38, 42, 77, 1, 7, 14, 23, 22, 33, 29, 41, 42, 54, 56, 101, 1, 7, 16, 26, 28, 37, 37, 45, 52, 59, 70, 77, 135, 1, 8, 18, 32, 33, 47, 42, 58, 57, 74, 76, 98, 101

Offset

1,2

Comments

Each partition of n is converted into a binary representation with n bits by concatenating binary representations of the parts p_1(n)+p_2(n)+p_3(n)+..., p_1(n)>=p_2(n)>=p_3(n),

larger parts contributing the higher significant bits, the individual part p_i(n) represented by a 1 followed by p_i(n)-1 zeros.

These A000041(n) binary representations are stacked, and the total count of 1's in each column is one entry T(n,k).

Together with table A130321, T(n,k) can be used to generate the check sequence

A173871: sum_{k=0..n-1} 2^(n-k)*T(n,k) = A173871(n). For example, multiplying the terms on the fifth row by 16 8 4 2 1

yields

7 1 3 4 5 by 16 8 4 2 1 yielding 112+8+12+8+5 = 145 which is A173871(5).

Links

Table of n, a(n) for n=1..105.

Example

Consider the seven partitions of Five, 5=(10000), 41=(1000)(1), 32=(100)(10), 311=(100)(1)(1), 221=(10)(10)(1), 2111=(10)(1)(1)(1) and 11111=(1)(1)(1)(1)(1),
the corresponding seven concatenated binary representations are
1 0 0 0 0
1 0 0 0 1
1 0 0 1 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 1 1 1
summing by column yields
7 1 3 4 5 the fifth row of the table. The table starts
1;
2,1;
3,1,2;
5,1,3,3;
7,1,3,4,5;
11,1,4,5,7,7;
15,1,4,6,8,9,11;

Maple

A176572row := proc(n) L := array(1..n, [seq(0, i=1..n)]) ; for pi in combinat[partition](n) do p := sort(pi) ;       p2 := [] ; for i from 1 to nops(p) do p2 := [op(p2), op(convert(2^(op(i, p)-1), base, 2))] ; end do: for i from 1 to n do L[i] := L[i]+ op(n-i+1, p2) ; end do: end do: L ; end proc:
for n from 1 to 14 do A176572row(n) ; print(%) ; end do:

Crossrefs

A006128 (row sums) A114994 A130321 A173871

Sequence in context: A036262 A080521 A169613 * A168017 A293980 A365785

Adjacent sequences: A176569 A176570 A176571 * A176573 A176574 A176575

Keyword

easy,nonn,tabl,base

Author

Alford Arnold, Apr 22 2010

Status

approved