A116608 Triangle read by rows: T(n,k) is number of partitions of n having k distinct parts (n>=1, k>=1).

1, 2, 2, 1, 3, 2, 2, 5, 4, 6, 1, 2, 11, 2, 4, 13, 5, 3, 17, 10, 4, 22, 15, 1, 2, 27, 25, 2, 6, 29, 37, 5, 2, 37, 52, 10, 4, 44, 67, 20, 4, 44, 97, 30, 1, 5, 55, 117, 52, 2, 2, 59, 154, 77, 5, 6, 68, 184, 117, 10, 2, 71, 235, 162, 20, 6, 81, 277, 227, 36, 4, 82, 338, 309, 58, 1

Offset: 1

Author

Emeric Deutsch, Feb 19 2006

Keywords

• nonn
• tabf
• look

Comments

Row n has floor([sqrt(1+8n)-1]/2) terms (number of terms increases by one at each triangular number).

Row sums yield the partition numbers (A000041).

Row n has length A003056(n), hence the first element of column k is in row A000217(k). - Omar E. Pol, Jan 19 2014

Examples

			T(6,2) = 6 because we have [5,1], [4,2], [4,1,1], [3,1,1,1], [2,2,1,1] and [2,1,1,1,1,1] ([6], [3,3], [3,2,1], [2,2,2] and [1,1,1,1,1,1] do not qualify).
Triangle starts:
  1;
  2;
  2,  1;
  3,  2;
  2,  5;
  4,  6, 1;
  2, 11, 2;
  4, 13, 5;
  3, 17, 10;
  4, 22, 15, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..500, flattened
• Emmanuel Briand, On partitions with k corners not containing the staircase with one more corner, arXiv:2004.13180 [math.CO], 2020.
• Sang June Lee and Jun Seok Oh, On zero-sum free sequences contained in random subsets of finite cyclic groups, arXiv:2003.02511 [math.CO], 2020.

Crossrefs

Cf. A000041, A000005, A000070, A002133, A002134.

Cf. A060177 (reflected rows). - Alois P. Heinz, Jan 29 2014

Cf. A274174.

Programs

Maple

g:=product(1+t*x^j/(1-x^j),j=1..30)-1: gser:=simplify(series(g,x=0,27)): for n from 1 to 23 do P[n]:=sort(coeff(gser,x^n)) od: for n from 1 to 23 do seq(coeff(P[n],t^j),j=1..floor(sqrt(1+8*n)/2-1/2)) od; # yields sequence in triangular form
# second Maple program:
b:= proc(n, i) option remember; local j; if n=0 then 1
      elif i<1 then 0 else []; for j from 0 to n/i do zip((x, y)
      ->x+y, %, [`if`(j>0, 0, [][]), b(n-i*j, i-1)], 0) od; %[] fi
    end:
T:= n-> subsop(1=NULL, [b(n, n)])[]:
seq(T(n), n=1..30); # Alois P. Heinz, Nov 07 2012
# third program
nDiffParts := proc(L)
        nops(convert(L,set)) ;
end proc:
A116608 := proc(n,k)
        local a,L;
        a :=0 ;
        for L in combinat[partition](n) do
                if nDiffParts(L) = k then
                        a := a+1 ;
                end  if;
        end do:
        a ;
end proc: # R. J. Mathar, Jun 07 2024

Mathematica

p=Product[1+(y x^i)/(1-x^i),{i,1,20}];f[list_]:=Select[list,#>0&];Flatten[Map[f,Drop[CoefficientList[Series[p,{x,0,20}],{x,y}],1]]] (* Geoffrey Critzer, Nov 28 2011 *)
Table[Length /@ Split[Sort[Length /@ Union /@ IntegerPartitions@n]], {n, 22}] // Flatten (* Robert Price, Jun 13 2020 *)

Python

from math import isqrt
from itertools import count, islice
from sympy.utilities.iterables import partitions
def A116608_gen(): # generator of terms
    return (sum(1 for p in partitions(n) if len(p)==k) for n in count(1) for k in range(1,(isqrt((n<<3)+1)-1>>1)+1))
A116608_list = list(islice(A116608_gen(),30)) # Chai Wah Wu, Sep 14 2023

Python

from functools import cache
@cache
def P(n: int, k: int, r: int) -> int:
    if n == 0: return 1 if k == 0 else 0
    if k == 0: return 0
    if r == 0: return 0
    return sum(P(n - r * j, k - 1, r - 1)
               for j in range(1, n // r + 1)) + P(n, k, r - 1)
def A116608triangle(rows: int) -> list[int]:
    return list(filter(None, [P(n, k, n) for n in range(1, rows)
                              for k in range(1, n + 1)]))
print(A116608triangle(22)) # Peter Luschny, Sep 14 2023, courtesy of Amir Livne Bar-on

Formula

G.f.: -1 + Product_{j=1..infinity} 1 + tx^j/(1-x^j).

T(n,1) = A000005(n) (number of divisors of n).

T(n,2) = A002133(n).

T(n,3) = A002134(n).

Sum_{k>=1} k * T(n,k) = A000070(n-1).

Sum_{k>=0} k! * T(n,k) = A274174(n). - Alois P. Heinz, Jun 13 2016

T(n + A000217(k), k) = A000712(n), for 0 <= n <= k [Briand]. - Álvar Ibeas, Nov 04 2020