%I #66 Jun 07 2024 04:45:10
%S 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,
%T 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,
%U 6,68,184,117,10,2,71,235,162,20,6,81,277,227,36,4,82,338,309,58,1
%N Triangle read by rows: T(n,k) is number of partitions of n having k distinct parts (n>=1, k>=1).
%C Row n has floor([sqrt(1+8n)-1]/2) terms (number of terms increases by one at each triangular number).
%C Row sums yield the partition numbers (A000041).
%C Row n has length A003056(n), hence the first element of column k is in row A000217(k). - _Omar E. Pol_, Jan 19 2014
%H Alois P. Heinz, <a href="/A116608/b116608.txt">Rows n = 1..500, flattened</a>
%H Emmanuel Briand, <a href="https://arxiv.org/abs/2004.13180">On partitions with k corners not containing the staircase with one more corner</a>, arXiv:2004.13180 [math.CO], 2020.
%H Sang June Lee and Jun Seok Oh, <a href="https://arxiv.org/abs/2003.02511">On zero-sum free sequences contained in random subsets of finite cyclic groups</a>, arXiv:2003.02511 [math.CO], 2020.
%F G.f.: -1 + Product_{j=1..infinity} 1 + tx^j/(1-x^j).
%F T(n,1) = A000005(n) (number of divisors of n).
%F T(n,2) = A002133(n).
%F T(n,3) = A002134(n).
%F Sum_{k>=1} k * T(n,k) = A000070(n-1).
%F Sum_{k>=0} k! * T(n,k) = A274174(n). - _Alois P. Heinz_, Jun 13 2016
%F T(n + A000217(k), k) = A000712(n), for 0 <= n <= k [Briand]. - _Álvar Ibeas_, Nov 04 2020
%e 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).
%e Triangle starts:
%e 1;
%e 2;
%e 2, 1;
%e 3, 2;
%e 2, 5;
%e 4, 6, 1;
%e 2, 11, 2;
%e 4, 13, 5;
%e 3, 17, 10;
%e 4, 22, 15, 1;
%e ...
%p 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
%p # second Maple program:
%p b:= proc(n, i) option remember; local j; if n=0 then 1
%p elif i<1 then 0 else []; for j from 0 to n/i do zip((x, y)
%p ->x+y, %, [`if`(j>0, 0, [][]), b(n-i*j, i-1)], 0) od; %[] fi
%p end:
%p T:= n-> subsop(1=NULL, [b(n, n)])[]:
%p seq(T(n), n=1..30); # _Alois P. Heinz_, Nov 07 2012
%p # third program
%p nDiffParts := proc(L)
%p nops(convert(L,set)) ;
%p end proc:
%p A116608 := proc(n,k)
%p local a,L;
%p a :=0 ;
%p for L in combinat[partition](n) do
%p if nDiffParts(L) = k then
%p a := a+1 ;
%p end if;
%p end do:
%p a ;
%p end proc: # _R. J. Mathar_, Jun 07 2024
%t 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 *)
%t Table[Length /@ Split[Sort[Length /@ Union /@ IntegerPartitions@n]], {n, 22}] // Flatten (* _Robert Price_, Jun 13 2020 *)
%o (Python)
%o from math import isqrt
%o from itertools import count, islice
%o from sympy.utilities.iterables import partitions
%o def A116608_gen(): # generator of terms
%o 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))
%o A116608_list = list(islice(A116608_gen(),30)) # _Chai Wah Wu_, Sep 14 2023
%o (Python)
%o from functools import cache
%o @cache
%o def P(n: int, k: int, r: int) -> int:
%o if n == 0: return 1 if k == 0 else 0
%o if k == 0: return 0
%o if r == 0: return 0
%o return sum(P(n - r * j, k - 1, r - 1)
%o for j in range(1, n // r + 1)) + P(n, k, r - 1)
%o def A116608triangle(rows: int) -> list[int]:
%o return list(filter(None, [P(n, k, n) for n in range(1, rows)
%o for k in range(1, n + 1)]))
%o print(A116608triangle(22)) # _Peter Luschny_, Sep 14 2023, courtesy of Amir Livne Bar-on
%Y Cf. A000041, A000005, A000070, A002133, A002134.
%Y Cf. A060177 (reflected rows). - _Alois P. Heinz_, Jan 29 2014
%Y Cf. A274174.
%K nonn,tabf,look
%O 1,2
%A _Emeric Deutsch_, Feb 19 2006