A126796
Number of complete partitions of n.
Original entry on oeis.org
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
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.
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.
-
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 */
A188431
The number of n-full sets, F(n).
Original entry on oeis.org
1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 1, 2, 1, 2, 3, 4, 5, 7, 7, 8, 9, 11, 10, 13, 14, 17, 20, 25, 28, 34, 40, 46, 54, 62, 69, 80, 90, 102, 115, 131, 144, 167, 186, 213, 239, 273, 304, 349, 388, 441, 495, 563, 625, 710, 790, 890, 990, 1114, 1232, 1387, 1530, 1713, 1894, 2119, 2330, 2605, 2866, 3192, 3512, 3910, 4289, 4774, 5237, 5809, 6377, 7068, 7739
Offset: 0
a(26) = 10, because there are 10 26-full sets: {1,2,4,5,6,8}, {1,2,3,5,7,8}, {1,2,3,5,6,9}, {1,2,3,4,7,9}, {1,2,3,4,6,10}, {1,2,3,4,5,11}, {1,2,4,8,11}, {1,2,4,7,12}, {1,2,4,6,13}, {1,2,3,7,13}.
G.f.: 1 = 1/(1+x) + 1*x/((1+x)*(1+x^2)) + 0*x^2/((1+x)*(1+x^2)*(1+x^3)) + 1*x^3/((1+x)*(1+x^2)*(1+x^3)*(1+x^4)) +...+ a(n)*x^n / Product_{k=1..n+1} (1+x^k) +...
Cf.
A002033,
A103295,
A108917,
A276024,
A325763,
A325765,
A325781,
A325782,
A325788,
A325986,
A325790,
A325791.
-
import Data.MemoCombinators (memo2, integral, Memo)
a188431 n = a188431_list !! (n-1)
a188431_list = map
(\x -> sum [fMemo x i | i <- [a188429 x .. a188430 x]]) [1..] where
fMemo = memo2 integral integral f
f _ 1 = 1
f m i = sum [fMemo (m - i) j |
j <- [a188429 (m - i) .. min (a188430 (m - i)) (i - 1)]]
-- Reinhard Zumkeller, Aug 06 2015
-
sums:= proc(s) local i, m;
m:= max(s[]);
`if`(m<1, {}, {m, seq([i, i+m][], i=sums(s minus {m}))})
end:
a:= proc(n) local b;
b:= proc(i,s) local si;
if i=1 then `if`(sums(s)={$1..n}, 1, 0)
else si:= s union {i};
b(i-1, s)+ `if`(max(sums(si)[])>n, 0, b(i-1, si))
fi
end; b(n, {1})
end:
seq(a(n), n=1..40); # Alois P. Heinz, Apr 03 2011
# second Maple program:
b:= proc(n, i) option remember; `if`(i*(i+1)/2n or i>n-i+1, 0, b(n-i, i-1))))
end:
a:= n-> b(n$2):
seq(a(n), n=0..80); # Alois P. Heinz, May 20 2017
-
Sums[s_] := Sums[s] = With[{m = Max[s]}, If[m < 1, {}, Union @ Flatten @ Join[{m}, Table[{i, i + m}, {i, Sums[s ~Complement~ {m}]}]]]];
a[n_] := Module[{b}, b[i_, s_] := b[i, s] = Module[{si}, If[i == 1, If[Sums[s] == Range[n], 1, 0], si = s ~Union~ {i}; b[i-1, s] + If[Max[ Sums[si]] > n, 0, b[i - 1, si]]]]; b[n, {1}]];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 80}] (* Jean-François Alcover, Apr 12 2017, after Alois P. Heinz *)
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Union[Total/@Union[Subsets[#]]]==Range[0,n]&]],{n,30}] (* Gus Wiseman, May 31 2019 *)
-
/* As coefficients in g.f. */
{a(n)=local(A=[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 */
A326020
Number of complete subsets of {1..n}.
Original entry on oeis.org
1, 2, 3, 4, 6, 9, 15, 27, 50, 95, 185, 365, 724, 1441, 2873, 5735, 11458, 22902, 45789, 91561, 183102, 366180, 732331, 1464626, 2929209, 5858367, 11716674, 23433277, 46866473, 93732852, 187465596, 374931067, 749861989, 1499723808, 2999447418
Offset: 0
The a(0) = 1 through a(6) = 15 subsets:
{} {} {} {} {} {} {}
{1} {1} {1} {1} {1} {1}
{1,2} {1,2} {1,2} {1,2} {1,2}
{1,2,3} {1,2,3} {1,2,3} {1,2,3}
{1,2,4} {1,2,4} {1,2,4}
{1,2,3,4} {1,2,3,4} {1,2,3,4}
{1,2,3,5} {1,2,3,5}
{1,2,4,5} {1,2,3,6}
{1,2,3,4,5} {1,2,4,5}
{1,2,4,6}
{1,2,3,4,5}
{1,2,3,4,6}
{1,2,3,5,6}
{1,2,4,5,6}
{1,2,3,4,5,6}
-
Table[Length[Select[Subsets[Range[n]],Union[Plus@@@Subsets[#]]==Range[0,Total[#]]&]],{n,0,10}]
A365924
Number of incomplete integer partitions of n, meaning not every number from 0 to n is the sum of some submultiset.
Original entry on oeis.org
0, 0, 1, 1, 3, 3, 6, 7, 12, 14, 22, 25, 38, 46, 64, 76, 106, 124, 167, 199, 261, 309, 402, 471, 604, 714, 898, 1053, 1323, 1542, 1911, 2237, 2745, 3201, 3913, 4536, 5506, 6402, 7706, 8918, 10719, 12364, 14760, 17045, 20234, 23296, 27600, 31678, 37365, 42910, 50371, 57695, 67628, 77300, 90242, 103131, 119997
Offset: 0
The a(0) = 0 through a(8) = 12 partitions:
. . (2) (3) (4) (5) (6) (7) (8)
(2,2) (3,2) (3,3) (4,3) (4,4)
(3,1) (4,1) (4,2) (5,2) (5,3)
(5,1) (6,1) (6,2)
(2,2,2) (3,2,2) (7,1)
(4,1,1) (3,3,1) (3,3,2)
(5,1,1) (4,2,2)
(4,3,1)
(5,2,1)
(6,1,1)
(2,2,2,2)
(5,1,1,1)
These partitions have ranks
A365830.
A046663 counts partitions w/o a submultiset summing to k, strict
A365663.
A325799 counts non-subset-sums of prime indices.
A364350 counts combination-free strict partitions.
A365543 counts partitions with a submultiset summing to k, strict
A365661.
-
nmz[y_]:=Complement[Range[Total[y]],Total/@Subsets[y]];
Table[Length[Select[IntegerPartitions[n],Length[nmz[#]]>0&]],{n,0,15}]
A325780
Heinz numbers of perfect integer partitions.
Original entry on oeis.org
1, 2, 4, 6, 8, 16, 18, 20, 32, 42, 54, 56, 64, 100, 128, 162, 176, 234, 256, 260, 294, 392, 416, 486, 500, 512, 798, 1024, 1026, 1064, 1088, 1458, 1936, 2048, 2058, 2300, 2432, 2500, 2744, 3042, 3380, 4096, 4374, 4698, 5104, 5408, 5888, 8192, 8658, 9620, 10878
Offset: 1
The sequence of terms together with their prime indices begins:
1: {}
2: {1}
4: {1,1}
6: {1,2}
8: {1,1,1}
16: {1,1,1,1}
18: {1,2,2}
20: {1,1,3}
32: {1,1,1,1,1}
42: {1,2,4}
54: {1,2,2,2}
56: {1,1,1,4}
64: {1,1,1,1,1,1}
100: {1,1,3,3}
128: {1,1,1,1,1,1,1}
162: {1,2,2,2,2}
176: {1,1,1,1,5}
234: {1,2,2,6}
256: {1,1,1,1,1,1,1,1}
260: {1,1,3,6}
Equals the sorted concatenation of the triangle
A258119.
-
hwt[n_]:=Total[Cases[FactorInteger[n],{p_,k_}:>PrimePi[p]*k]];
Select[Range[1000],Sort[hwt/@Rest[Divisors[#]]]==Range[DivisorSigma[0,#]-1]&]
A365831
Number of incomplete strict integer partitions of n, meaning not every number from 0 to n is the sum of some submultiset.
Original entry on oeis.org
0, 0, 1, 1, 2, 3, 3, 4, 6, 8, 9, 11, 13, 16, 21, 25, 31, 36, 43, 50, 59, 69, 82, 96, 113, 131, 155, 179, 208, 239, 276, 315, 362, 414, 472, 539, 614, 698, 795, 902, 1023, 1158, 1311, 1479, 1672, 1881, 2118, 2377, 2671, 2991, 3354, 3748, 4194, 4679, 5223, 5815
Offset: 0
The strict partition (14,5,4,2,1) has no subset summing to 13 so is counted under a(26).
The a(2) = 1 through a(10) = 9 strict partitions:
(2) (3) (4) (5) (6) (7) (8) (9) (10)
(3,1) (3,2) (4,2) (4,3) (5,3) (5,4) (6,4)
(4,1) (5,1) (5,2) (6,2) (6,3) (7,3)
(6,1) (7,1) (7,2) (8,2)
(4,3,1) (8,1) (9,1)
(5,2,1) (4,3,2) (5,3,2)
(5,3,1) (5,4,1)
(6,2,1) (6,3,1)
(7,2,1)
A046663 counts partitions w/o a submultiset summing to k, strict
A365663.
A325799 counts non-subset-sums of prime indices.
A365543 counts partitions with a submultiset summing to k, strict
A365661.
-
nmz[y_]:=Complement[Range[Total[y]], Total/@Subsets[y]];
Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&Length[nmz[#]]>0&]],{n,0,15}]
A367224
Numbers m with a divisor whose prime indices sum to bigomega(m).
Original entry on oeis.org
1, 2, 4, 6, 8, 9, 12, 15, 16, 18, 20, 21, 24, 30, 32, 33, 36, 39, 40, 42, 45, 48, 50, 51, 54, 56, 57, 60, 64, 66, 69, 70, 72, 75, 78, 80, 81, 84, 87, 90, 93, 96, 100, 102, 105, 108, 110, 111, 112, 114, 120, 123, 125, 126, 128, 129, 130, 132, 135, 138, 140, 141
Offset: 1
The prime indices of 24 are {1,1,1,2} with submultiset {1,1,2} summing to 4, so 24 is in the sequence.
The terms together with their prime indices begin:
1: {}
2: {1}
4: {1,1}
6: {1,2}
8: {1,1,1}
9: {2,2}
12: {1,1,2}
15: {2,3}
16: {1,1,1,1}
18: {1,2,2}
20: {1,1,3}
21: {2,4}
24: {1,1,1,2}
30: {1,2,3}
32: {1,1,1,1,1}
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
Triangles:
A046663 counts partitions of n without a subset-sum k, strict
A365663.
-
prix[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p], {k}]]]];
Select[Range[100], MemberQ[Total/@prix/@Divisors[#], PrimeOmega[#]]&]
A367225
Numbers m without a divisor whose prime indices sum to bigomega(m).
Original entry on oeis.org
3, 5, 7, 10, 11, 13, 14, 17, 19, 22, 23, 25, 26, 27, 28, 29, 31, 34, 35, 37, 38, 41, 43, 44, 46, 47, 49, 52, 53, 55, 58, 59, 61, 62, 63, 65, 67, 68, 71, 73, 74, 76, 77, 79, 82, 83, 85, 86, 88, 89, 91, 92, 94, 95, 97, 98, 99, 101, 103, 104, 106, 107, 109, 113
Offset: 1
The prime indices of 24 are {1,1,1,2} with submultiset {1,1,2} summing to 4, so 24 is not in the sequence.
The terms together with their prime indices begin:
3: {2} 29: {10} 58: {1,10}
5: {3} 31: {11} 59: {17}
7: {4} 34: {1,7} 61: {18}
10: {1,3} 35: {3,4} 62: {1,11}
11: {5} 37: {12} 63: {2,2,4}
13: {6} 38: {1,8} 65: {3,6}
14: {1,4} 41: {13} 67: {19}
17: {7} 43: {14} 68: {1,1,7}
19: {8} 44: {1,1,5} 71: {20}
22: {1,5} 46: {1,9} 73: {21}
23: {9} 47: {15} 74: {1,12}
25: {3,3} 49: {4,4} 76: {1,1,8}
26: {1,6} 52: {1,1,6} 77: {4,5}
27: {2,2,2} 53: {16} 79: {22}
28: {1,1,4} 55: {3,5} 82: {1,13}
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
Triangles:
A046663 counts partitions of n without a subset-sum k, strict
A365663.
-
prix[n_]:=If[n==1,{}, Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100], FreeQ[Total/@prix/@Divisors[#], PrimeOmega[#]]&]
A365925
Number of subset-sums of strict integer partitions of n.
Original entry on oeis.org
1, 2, 2, 6, 6, 10, 17, 22, 29, 42, 59, 74, 102, 130, 171, 226, 281, 356, 454, 566, 699, 896, 1080, 1342, 1637, 2006, 2413, 2962, 3548, 4286, 5114, 6148, 7272, 8738, 10268, 12224, 14387, 16996, 19863, 23450, 27257, 31984, 37187, 43364, 50173, 58428, 67322
Offset: 0
The a(6) = 17 ways, showing each strict partition and its subset-sums:
(6): 0,6
(51): 0,1,5,6
(42): 0,2,4,6
(321): 0,1,2,3,4,5,6
A367226
Numbers m whose prime indices have a nonnegative linear combination equal to bigomega(m).
Original entry on oeis.org
1, 2, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 28, 30, 32, 33, 34, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51, 52, 54, 56, 57, 58, 60, 62, 64, 66, 68, 69, 70, 72, 74, 75, 76, 78, 80, 81, 82, 84, 86, 87, 88, 90, 92, 93, 94, 96, 98, 100, 102, 104
Offset: 1
The prime indices of 24 are {1,1,1,2} with (1+1+1+1) = 4 or (1+1)+(2) = 4 or (2+2) = 4, so 24 is in the sequence.
The terms together with their prime indices begin:
1: {}
2: {1}
4: {1,1}
6: {1,2}
8: {1,1,1}
9: {2,2}
10: {1,3}
12: {1,1,2}
14: {1,4}
15: {2,3}
16: {1,1,1,1}
18: {1,2,2}
20: {1,1,3}
21: {2,4}
22: {1,5}
24: {1,1,1,2}
26: {1,6}
28: {1,1,4}
30: {1,2,3}
32: {1,1,1,1,1}
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free
-------------------------------------------
A046663 counts partitions of n without a subset-sum k, strict
A365663.
-
prix[n_]:=If[n==1,{}, Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
combs[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Select[Range[100], combs[PrimeOmega[#], Union[prix[#]]]!={}&]
Showing 1-10 of 55 results.
Comments