|
|
A116608
|
|
Triangle read by rows: T(n,k) is number of partitions of n having k distinct parts (n>=1, k>=1).
|
|
116
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
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).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: -1 + Product_{j=1..infinity} 1 + tx^j/(1-x^j).
T(n,1) = A000005(n) (number of divisors of n).
Sum_{k>=1} k * T(n,k) = A000070(n-1).
|
|
EXAMPLE
|
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;
...
|
|
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)])[]:
|
|
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 *)
|
|
PROG
|
(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))
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|