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

%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