A126796 - cp's OEIS frontend

A126796 Number of complete partitions of n.

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

Offset: 0

Brian Hopkins, Feb 20 2007

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
For n > 0: a(n) = sum of n-th row in A261036 and also a(floor(n/2)) = A261036(n,floor((n+1)/2)). - Reinhard Zumkeller, Aug 08 2015
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

			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) + ...
From _Gus Wiseman_, Oct 14 2023: (Start)
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)

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 301 terms from David W. Wilson)
George E. Andrews, George Beck, and Brian Hopkins, On a Conjecture of Hanna Connecting Distinct Part and Complete Partitions, Annals of Comb., 24(2020), pp. 217-224.
George Beck and Shane Chern, Reciprocity between partitions and compositions, arXiv:2108.04363 [math.CO], 2021.
Nathaniel Johnston and Sarah Plosker, Laplacian {-1,0,1}- and {-1,1}-diagonalizable graphs, arXiv:2308.15611 [math.CO], 2023.
SeungKyung Park, Complete Partitions, Fibonacci Quarterly, Vol. 36 (1998), pp. 354-360.

Cf. A002033, A003513, A209405, A261036, A286929, A286097.
For parts instead of sums we have A000009 (sc. coverings), ranks A055932.
The strict case is A188431, complement A365831.
These partitions have ranks A325781.
First column k = 0 of A365923.
The complement is counted by A365924, ranks A365830.
Cf. A000041, A018818, A046663, A047967, A276024, A304792, A325799, A365543, A365658, A365918, A365921.

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
-- Reinhard Zumkeller, Aug 07 2015

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

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]];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Apr 11 2017, after Franklin T. Adams-Watters *)
nmz[y_]:=Complement[Range[Total[y]], Total/@Subsets[y]]; Table[Length[Select[IntegerPartitions[n], nmz[#]=={}&]],{n,0,15}] (* Gus Wiseman, Oct 14 2023 *)

{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 */

/* 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 */

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
a(n) = A000041(n) - A365924(n). - Gus Wiseman, Oct 14 2023

More terms from R. J. Mathar, Feb 27 2007
More terms from Emeric Deutsch, Mar 04 2007
Further terms from Franklin T. Adams-Watters and David W. Wilson, Mar 22 2007

cp's OEIS Frontend

A126796 Number of complete partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions