login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A126796 Number of complete partitions of n. 12
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

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 301 terms from David W. Wilson)

SeungKyung Park, Complete Partitions, Fibonacci Quarterly, Vol. 36 (1998), pp. 354-360.

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

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) +...

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]];

Table[a[n], {n, 0, 50}] (* Jean-Fran├žois Alcover, Apr 11 2017, after Franklin T. Adams-Watters *)

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

-- Reinhard Zumkeller, Aug 07 2015

CROSSREFS

Cf. A002033, A188431, A209405.

Cf. A261036.

Cf. A286929, A286097.

Sequence in context: A240486 A237871 A027193 * A240451 A206138 A241545

Adjacent sequences:  A126793 A126794 A126795 * A126797 A126798 A126799

KEYWORD

nonn,nice,changed

AUTHOR

Brian Hopkins, Feb 20 2007

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 23 02:46 EDT 2017. Contains 286909 sequences.