|
| |
|
|
A126796
|
|
Number of complete partitions of n.
|
|
84
|
|
|
|
1, 1, 1, 2, 2, 4, 5, 8, 10, 16, 20, 31, 39, 55, 71, 100, 125, 173, 218, 291, 366, 483, 600, 784, 971, 1244, 1538, 1957, 2395, 3023, 3693, 4605, 5604, 6942, 8397, 10347, 12471, 15235, 18309, 22267, 26619, 32219, 38414, 46216, 54941, 65838, 77958, 93076, 109908
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
A partition of n is complete if every number 1 to n can be represented as a sum of parts of the partition. This generalizes perfect partitions, where the representation for each number must be unique.
A partition is complete iff each part is no more than 1 more than the sum of all smaller parts. (This includes the smallest part, which thus must be 1.) - Franklin T. Adams-Watters, Mar 22 2007
a(n+1) is the number of partitions of n such that each part is no more than 2 more than the sum of all smaller parts (generalizing Adams-Watters's criterion). Bijection: each partition counted by a(n+1) must contain a 1, removing that gives a desired partition of n. - Brian Hopkins, May 16 2017
A partition (x_1, ..., x_k) is complete if and only if 1, x_1, ..., x_k is a "regular sequence" (see A003513 for definition). As a result, the number of complete partitions with n parts is given by A003513(n+1). - Nathaniel Johnston, Jun 29 2023
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: 1 = Sum_{n>=0} a(n)*x^n*Product_{k=1..n+1} (1-x^k). - Paul D. Hanna, Mar 08 2012
a(n) ~ exp(Pi*sqrt(2*n/3)) / (4*sqrt(3)*n) * (1 - (sqrt(3/2)/Pi + 25*Pi/(24*sqrt(6))) / sqrt(n) + (25/16 - 1679*Pi^2/6912)/n). - Vaclav Kotesovec, May 24 2018, extended Nov 02 2019
|
|
|
EXAMPLE
|
There are a(5) = 4 complete partitions of 5:
[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], and [1, 1, 3].
G.f.: 1 = 1*(1-x) + 1*x*(1-x)*(1-x^2) + 1*x^2*(1-x)*(1-x^2)*(1-x^3) + 2*x^3*(1-x)*(1-x^2)*(1-x^3)*(1-x^4) + 2*x^4*(1-x)*(1-x^2)*(1-x^3)*(1-x^4)*(1-x^5) + ...
The a(1) = 1 through a(8) = 10 partitions:
(1) (11) (21) (211) (221) (321) (421) (3221)
(111) (1111) (311) (2211) (2221) (3311)
(2111) (3111) (3211) (4211)
(11111) (21111) (4111) (22211)
(111111) (22111) (32111)
(31111) (41111)
(211111) (221111)
(1111111) (311111)
(2111111)
(11111111)
(End)
|
|
|
MAPLE
|
isCompl := proc(p, n) local m, pers, reps, f, lst, s; reps := {}; pers := combinat[permute](p); for m from 1 to nops(pers) do lst := op(m, pers); for f from 1 to nops(lst) do s := add( op(i, lst), i=1..f); reps := reps union {s}; od; od; for m from 1 to n do if not m in reps then RETURN(false); fi; od; RETURN(true); end: A126796 := proc(n) local prts, res, p; prts := combinat[partition](n); res :=0; for p from 1 to nops(prts) do if isCompl(op(p, prts), n) then res := res+1; fi; od; RETURN(res); end: for n from 1 to 40 do printf("%d %d ", n, A126796(n)); od; # R. J. Mathar, Feb 27 2007
# At the beginning of the 2nd Maple program replace the current 15 by any other positive integer n in order to obtain a(n). - Emeric Deutsch, Mar 04 2007
with(combinat): a:=proc(n) local P, b, k, p, S, j: P:=partition(n): b:=0: for k from 1 to numbpart(n) do p:=powerset(P[k]): S:={}: for j from 1 to nops(p) do S:=S union {add(p[j][i], i=1..nops(p[j]))} od: if nops(S)=n+1 then b:=b+1 else b:=b: fi: od: end: seq(a(n), n=1..30); # Emeric Deutsch, Mar 04 2007
with(combinat): n:=15: P:=partition(n): b:=0: for k from 1 to numbpart(n) do p:=powerset(P[k]): S:={}: for j from 1 to nops(p) do S:=S union {add(p[j][i], i=1..nops(p[j]))} od: if nops(S)=n+1 then b:=b+1 else b:=b: fi: od: b; # Emeric Deutsch, Mar 04 2007
|
|
|
MATHEMATICA
|
T[n_, k_] := T[n, k] = If[k <= 1, 1, If[n < 2k-1, T[n, Floor[(n+1)/2]], T[n, k-1] + T[n-k, k]]];
a[n_] := T[n, Floor[(n+1)/2]];
nmz[y_]:=Complement[Range[Total[y]], Total/@Subsets[y]]; Table[Length[Select[IntegerPartitions[n], nmz[#]=={}&]], {n, 0, 15}] (* Gus Wiseman, Oct 14 2023 *)
|
|
|
PROG
|
(PARI) {T(n, k)=if(k<=1, 1, if(n<2*k-1, T(n, floor((n+1)/2)), T(n, k-1)+T(n-k, k)))}
{a(n)=T(n, floor((n+1)/2))} /* If modified to save earlier results, this would be efficient. */ /* Franklin T. Adams-Watters, Mar 22 2007 */
(PARI) /* As coefficients in g.f.: */
{a(n)=local(A=[1, 1]); for(i=1, n+1, A=concat(A, 0); A[#A]=polcoeff(1-sum(m=1, #A, A[m]*x^m*prod(k=1, m, 1-x^k +x*O(x^#A))), #A) ); A[n+1]}
for(n=0, 50, print1(a(n), ", ")) /* Paul D. Hanna, Mar 06 2012 */
(Haskell)
import Data.MemoCombinators (memo3, integral, Memo)
a126796 n = a126796_list !! n
a126796_list = map (pMemo 1 1) [0..] where
pMemo = memo3 integral integral integral p
p _ _ 0 = 1
p s k m
| k > min m s = 0
| otherwise = pMemo (s + k) k (m - k) + pMemo s (k + 1) m
|
|
|
CROSSREFS
|
For parts instead of sums we have A000009 (sc. coverings), ranks A055932.
These partitions have ranks A325781.
Cf. A000041, A018818, A046663, A047967, A276024, A304792, A325799, A365543, A365658, A365918, A365921.
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
