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 strings formed from each 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 the n-th row of the triangle.

Links

John Tyler Rascoe, Rows n = 1..60, flattened

Formula

Sum_{k=0..n-1} 2^(n-k)*T(n,k) = A173871(n).

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.
Triangle begins:
  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:

Prog

(Python)
from sympy .utilities.iterables import ordered_partitions
def A176572(row_n):
    p = [i for i in ordered_partitions(row_n)]
    A = [[j for k in i[::-1] for j in ([1]+[0]*(k-1))] for i in p]
    return [sum(A[i][j] for i in range(len(p))) for j in range(row_n)] # John Tyler Rascoe, Feb 24 2025

Crossrefs

Cf. 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

Extensions

Edited by John Tyler Rascoe, Feb 24 2025

Status

approved