A124506
Number of numerical semigroups with Frobenius number n; that is, numerical semigroups for which the largest integer not belonging to them is n.
Original entry on oeis.org
1, 1, 2, 2, 5, 4, 11, 10, 21, 22, 51, 40, 106, 103, 200, 205, 465, 405, 961, 900, 1828, 1913, 4096, 3578, 8273, 8175, 16132, 16267, 34903, 31822, 70854, 68681, 137391, 140661, 292081, 270258, 591443, 582453, 1156012
Offset: 1
P. A. Garcia-Sanchez (pedro(AT)ugr.es), Dec 18 2006
a(1) = 1 via <2,3> = {0,2,3,4,...}; the largest missing number is 1.
a(2) = 1 via <3,4,5> = {0,3,4,5,...}; the largest missing number is 2.
a(3) = 2 via <2,5> = {0,2,4,5,...}; and <4,5,6,7> = {0,4,5,6,7,...} where in both the largest missing number is 3.
a(4) = 2 via <3,5,7> = {0,3,5,6,7,...} and <5,6,7,8,9> = {5,6,7,8,9,...} where in both the largest missing number is 4.
- S. R. Finch, Monoids of natural numbers
- Manuel Delgado, Neeraj Kumar, and Claude Marion, On counting numerical semigroups by maximum primitive and Wilf's conjecture, arXiv:2501.04417 [math.CO], 2025. See p. 22.
- S. R. Finch, Monoids of natural numbers, March 17, 2009. [Cached copy, with permission of the author]
- J. C. Rosales, P. A. Garcia-Sanchez, J. I. Garcia-Garcia, and J. A. Jimenez-Madrid, Fundamental gaps in numerical semigroups, Journal of Pure and Applied Algebra 189 (2004) 301-313.
- Clayton Cristiano Silva, Irreducible Numerical Semigroups, University of Campinas, São Paulo, Brazil (2019).
Cf.
A085489,
A088809,
A093971,
A103580,
A116861,
A151897,
A237668,
A308546,
A326020,
A326083,
A364349,
A365069.
A068911
Number of n-step walks (each step +-1 starting from 0) which are never more than 2 or less than -2.
Original entry on oeis.org
1, 2, 4, 6, 12, 18, 36, 54, 108, 162, 324, 486, 972, 1458, 2916, 4374, 8748, 13122, 26244, 39366, 78732, 118098, 236196, 354294, 708588, 1062882, 2125764, 3188646, 6377292, 9565938, 19131876, 28697814, 57395628, 86093442, 172186884, 258280326, 516560652
Offset: 0
The a(3) = 6 walks: (0,-1,-2,-1), (0,-1,0,-1), (0,-1,0,1), (0,1,0,-1), (0,1,0,1), (0,1,2,1). - _Gus Wiseman_, Oct 10 2023
- Alois P. Heinz, Table of n, a(n) for n = 0..4191
- F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
- Stoyan Dimitrov, Sorting by shuffling methods and a queue, arXiv:2103.04332 [math.CO], 2021.
- Robert Dorward et al., A Generalization of Zeckendorf's Theorem via Circumscribed m-gons, arXiv:1508.07531 [math.NT], 2015. See Example 1.3 p. 4.
- Noam D. Elkies, New Directions in Enumerative Chess Problems, arXiv:math/0508645 [math.CO], 2005; The Electronic Journal of Combinatorics, 11 (2), 2004-2005.
- Sean A. Irvine, Walks on Graphs.
- D. Panario, M. Sahin, Q. Wang, and W. Webb, General conditional recurrences, Applied Mathematics and Computation, Volume 243, Sep 15 2014, Pages 220-231.
- Noriaki Sannomiya, H. Katsura, and Y. Nakayama, Supersymmetry breaking and Nambu-Goldstone fermions with cubic dispersion, arXiv preprint arXiv:1612.02285 [cond-mat.str-el], 2016-2017. See Table I, line 3.
- Index entries for linear recurrences with constant coefficients, signature (0,3).
Cf.
A004526,
A004737,
A008967,
A046663,
A088809,
A365376,
A365377,
A365381,
A365541,
A365544,
A366130.
-
[Floor((5-(-1)^n)*3^Floor(n/2)/3): n in [0..40]]; // Bruno Berselli, Feb 26 2016, after Charles R Greathouse IV
-
with(GraphTheory): G:= PathGraph(5): A:=AdjacencyMatrix(G): nmax:=34; for n from 0 to nmax do B(n):=A^n; a(n):=add(B(n)[3,k], k=1..5) od: seq(a(n), n=0..nmax); # Johannes W. Meijer, May 29 2010
# second Maple program:
a:= proc(n) a(n):= `if`(n<2, n+1, (4-irem(n, 2))/2*a(n-1)) end:
seq(a(n), n=0..40); # Alois P. Heinz, Feb 03 2019
-
Join[{1},Transpose[NestList[{Last[#],3First[#]}&,{2,4},40]][[1]]] (* Harvey P. Dale, Oct 24 2011 *)
Table[Length[Select[Subsets[Range[n]],FreeQ[Total/@Subsets[#,{2}],n]&]],{n,0,15}] (* Gus Wiseman, Oct 06 2023 *)
-
a(n)=[4,6][n%2+1]*3^(n\2)\3 \\ Charles R Greathouse IV, Feb 26 2016
-
def A068911(n): return 3**(n>>1)<<1 if n&1 else (3**(n-1>>1)<<2 if n else 1) # Chai Wah Wu, Aug 30 2024
A088314
Cardinality of set of sets of parts of all partitions of n.
Original entry on oeis.org
1, 1, 2, 3, 5, 6, 10, 12, 18, 22, 30, 37, 51, 61, 79, 96, 124, 148, 186, 222, 275, 326, 400, 473, 575, 673, 811, 946, 1132, 1317, 1558, 1813, 2138, 2463, 2893, 3323, 3882, 4461, 5177, 5917, 6847, 7818, 8994, 10251, 11766, 13334, 15281, 17309, 19732, 22307
Offset: 0
The 7 partitions of 5 and their sets of parts are
[ #] partition set of parts
[ 1] [ 1 1 1 1 1 ] {1}
[ 2] [ 2 1 1 1 ] {1, 2}
[ 3] [ 2 2 1 ] {1, 2} (same as before)
[ 4] [ 3 1 1 ] {1, 3}
[ 5] [ 3 2 ] {2, 3}
[ 6] [ 4 1 ] {1, 4}
[ 7] [ 5 ] {5}
so we have a(5) = |{{1}, {1, 2}, {1, 3}, {2, 3}, {1, 4}, {5}}| = 6.
-
a066186 = sum . concat . ps 1 where
ps _ 0 = [[]]
ps i j = [t:ts | t <- [i..j], ts <- ps t (j - t)]
-- Reinhard Zumkeller, Jul 13 2013
-
list2set := L -> {op(L)};
a:= N -> list2set(map( list2set, combinat[partition](N) ));
seq(nops(a(n)), n=0..30);
# Yogy Namara (yogy.namara(AT)gmail.com), Jan 13 2010
b:= proc(n, i) option remember; `if`(n=0, {{}}, `if`(i<1, {},
{b(n, i-1)[], seq(map(x->{x[],i}, b(n-i*j, i-1))[], j=1..n/i)}))
end:
a:= n-> nops(b(n, n)):
seq(a(n), n=0..40);
# Alois P. Heinz, Aug 09 2012
-
Table[Length[Union[Map[Union,IntegerPartitions[n]]]],{n,1,30}] (* Geoffrey Critzer, Feb 19 2013 *)
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, {{}}, If[i < 1, {},
Union@Flatten@{b[n, i - 1], Table[If[Head[#] == List,
Append[#, i]]& /@ b[n - i*j, i - 1], {j, 1, n/i}]}]];
a[n_] := Length[b[n, n]];
a /@ Range[0, 40] (* Jean-François Alcover, Jun 04 2021, after Alois P. Heinz *)
combp[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,1,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Join@@Array[IntegerPartitions,n], UnsameQ@@#&&combp[n,#]!={}&]], {n,0,15}] (* Gus Wiseman, Sep 11 2023 *)
-
from sympy.utilities.iterables import partitions
def A088314(n): return len({tuple(sorted(set(p))) for p in partitions(n)}) # Chai Wah Wu, Sep 10 2023
A365046
Number of subsets of {1..n} containing n such that some element can be written as a nonnegative linear combination of the others.
Original entry on oeis.org
0, 0, 1, 2, 6, 11, 28, 53, 118, 235, 490, 973, 2008, 3990, 8089, 16184, 32563, 65071, 130667, 261183, 523388, 1046748, 2095239, 4190208, 8385030, 16768943, 33546257, 67092732, 134201461, 268400553, 536839090, 1073670970, 2147414967, 4294829905, 8589793931
Offset: 0
The subset {3,4,10} has 10 = 2*3 + 1*4 so is counted under a(10).
The a(0) = 0 through a(5) = 11 subsets:
. . {1,2} {1,3} {1,4} {1,5}
{1,2,3} {2,4} {1,2,5}
{1,2,4} {1,3,5}
{1,3,4} {1,4,5}
{2,3,4} {2,3,5}
{1,2,3,4} {2,4,5}
{1,2,3,5}
{1,2,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
The positive complement is counted by
A365045, first differences of
A365044.
Without re-usable parts we have
A365069, first differences of
A364534.
A364350 counts combination-free strict partitions, complement
A364839.
A085489 and
A364755 count subsets without the sum of two distinct elements.
A088809 and
A364756 count subsets with the sum of two distinct elements.
A364913 counts combination-full partitions.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&Or@@Table[combs[#[[k]],Union[Delete[#,k]]]!={},{k,Length[#]}]&]],{n,0,10}]
A365073
Number of subsets of {1..n} that can be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
1, 1, 3, 6, 14, 26, 60, 112, 244, 480, 992, 1944, 4048, 7936, 16176, 32320, 65088, 129504, 261248, 520448, 1046208, 2090240, 4186624, 8365696, 16766464, 33503744, 67064064, 134113280, 268347392, 536546816, 1073575936, 2146703360, 4294425600, 8588476416, 17178349568
Offset: 0
The subset {2,3,6} has 7 = 2*2 + 1*3 + 0*6 so is counted under a(7).
The a(1) = 1 through a(4) = 14 subsets:
{1} {1} {1} {1}
{2} {3} {2}
{1,2} {1,2} {4}
{1,3} {1,2}
{2,3} {1,3}
{1,2,3} {1,4}
{2,3}
{2,4}
{3,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The case of positive coefficients is
A088314.
The case of subsets containing n is
A131577.
The positive complement is counted by
A365322.
The complement is counted by
A365380.
The case of subsets without n is
A365542.
A364350 counts combination-free strict partitions.
Cf.
A007865,
A088809,
A093971,
A151897,
A237668,
A308546,
A326020,
A364534,
A364839,
A365043,
A365381.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],combs[n,#]!={}&]],{n,0,5}]
-
a(n)={
my(comb(k,b)=while(b>>k, b=bitor(b, b>>k); k*=2); b);
my(recurse(k,b)=
if(bittest(b,0), 2^(n+1-k),
if(2*k>n, 2^(n+1-k) - 2^sum(j=k, n, !bittest(b,j)),
self()(k+1, b) + self()(k+1, comb(k,b)) )));
recurse(1, 1<Andrew Howroyd, Sep 04 2023
A365541
Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} containing two distinct elements summing to k = 3..2n-1.
Original entry on oeis.org
1, 2, 2, 2, 4, 4, 7, 4, 4, 8, 8, 14, 14, 14, 8, 8, 16, 16, 28, 28, 37, 28, 28, 16, 16, 32, 32, 56, 56, 74, 74, 74, 56, 56, 32, 32, 64, 64, 112, 112, 148, 148, 175, 148, 148, 112, 112, 64, 64, 128, 128, 224, 224, 296, 296, 350, 350, 350, 296, 296, 224, 224, 128, 128
Offset: 2
Triangle begins:
1
2 2 2
4 4 7 4 4
8 8 14 14 14 8 8
16 16 28 28 37 28 28 16 16
32 32 56 56 74 74 74 56 56 32 32
Row n = 4 counts the following subsets:
{1,2} {1,3} {1,4} {2,4} {3,4}
{1,2,3} {1,2,3} {2,3} {1,2,4} {1,3,4}
{1,2,4} {1,3,4} {1,2,3} {2,3,4} {2,3,4}
{1,2,3,4} {1,2,3,4} {1,2,4} {1,2,3,4} {1,2,3,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The case counting only length-2 subsets is
A008967.
Column k = n + 1 appears to be
A167762.
The version for all subsets (instead of just pairs) is
A365381.
A000009 counts subsets summing to n.
A046663 counts partitions with no submultiset summing to k, strict
A365663.
A365543 counts partitions with a submultiset summing to k, strict
A365661.
-
Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#,{2}],k]&]], {n,2,11}, {k,3,2n-1}]
A288728
Number of sum-free sets that can be created by adding n to all sum-free sets [1..n-1].
Original entry on oeis.org
1, 1, 3, 3, 7, 8, 18, 19, 47, 43, 102, 116, 238, 240, 553, 554, 1185, 1259, 2578, 2607, 5873, 5526, 11834, 12601, 24692, 24390, 53735, 52534, 107445, 107330, 218727, 215607, 461367, 427778, 891039, 910294, 1804606, 1706828, 3695418, 3411513, 7136850, 6892950
Offset: 1
1 can be added to {};
2 can be added to {} but not {1};
3 can be added to {},{1},{2};
4 can be added to {},{1},{3} but not {2},{1,3},{2,3}.
From _Gus Wiseman_, Aug 12 2023: (Start)
The a(1) = 1 through a(7) = 18 sum-free sets with maximum n:
{1} {2} {3} {4} {5} {6} {7}
{1,3} {1,4} {1,5} {1,6} {1,7}
{2,3} {3,4} {2,5} {2,6} {2,7}
{3,5} {4,6} {3,7}
{4,5} {5,6} {4,7}
{1,3,5} {1,4,6} {5,7}
{3,4,5} {2,5,6} {6,7}
{4,5,6} {1,3,7}
{1,4,7}
{1,5,7}
{2,3,7}
{2,6,7}
{3,5,7}
{4,5,7}
{4,6,7}
{5,6,7}
{1,3,5,7}
{4,5,6,7}
(End)
For non-binary sum-free subsets of {1..n} we have
A237667.
For sum-free partitions we have
A364345, without re-using parts
A236912.
The complement without re-using parts is
A364756, differences of
A088809.
-
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&Intersection[#,Total/@Tuples[#,2]]=={}&]],{n,10}] (* Gus Wiseman, Aug 12 2023 *)
A365380
Number of subsets of {1..n} that cannot be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
1, 1, 2, 2, 6, 4, 16, 12, 32, 32, 104, 48, 256, 208, 448, 448, 1568, 896, 3840, 2368, 6912, 7680, 22912, 10752, 50688, 44800, 104448, 88064, 324096, 165888, 780288, 541696, 1458176, 1519616, 4044800, 2220032, 10838016, 8744960, 20250624, 16433152, 62267392, 34865152
Offset: 1
The set {4,5,6} cannot be linearly combined to obtain 7 so is counted under a(7), but we have 8 = 2*4 + 0*5 + 0*6, so it is not counted under a(8).
The a(1) = 1 through a(8) = 12 subsets:
{} {} {} {} {} {} {} {}
{2} {3} {2} {4} {2} {3}
{3} {5} {3} {5}
{4} {4,5} {4} {6}
{2,4} {5} {7}
{3,4} {6} {3,6}
{2,4} {3,7}
{2,6} {5,6}
{3,5} {5,7}
{3,6} {6,7}
{4,5} {3,6,7}
{4,6} {5,6,7}
{5,6}
{2,4,6}
{3,5,6}
{4,5,6}
A124506 appears to count combination-free subsets, differences of
A326083.
A365046 counts combination-full subsets, first differences of
A364914.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n-1]],combs[n,#]=={}&]],{n,5}]
A367212
Number of integer partitions of n whose length (number of parts) is equal to the sum of some submultiset.
Original entry on oeis.org
1, 1, 1, 2, 3, 5, 6, 11, 15, 22, 30, 43, 58, 80, 106, 143, 186, 248, 318, 417, 530, 684, 863, 1103, 1379, 1741, 2162, 2707, 3339, 4145, 5081, 6263, 7640, 9357, 11350, 13822, 16692, 20214, 24301, 29300, 35073, 42085, 50208, 59981, 71294, 84866, 100509, 119206
Offset: 0
The partition (3,2,1,1) has submultisets (3,1) or (2,1,1) with sum 4, so is counted under a(7).
The a(1) = 1 through a(8) = 15 partitions:
(1) (11) (21) (22) (32) (42) (52) (62)
(111) (211) (221) (321) (322) (332)
(1111) (311) (2211) (331) (431)
(2111) (3111) (421) (521)
(11111) (21111) (2221) (2222)
(111111) (3211) (3221)
(4111) (3311)
(22111) (4211)
(31111) (22211)
(211111) (32111)
(1111111) (41111)
(221111)
(311111)
(2111111)
(11111111)
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:
-
Table[Length[Select[IntegerPartitions[n], MemberQ[Total/@Subsets[#], Length[#]]&]], {n,0,10}]
A367214
Number of strict integer partitions of n whose length (number of parts) is equal to the sum of some submultiset.
Original entry on oeis.org
1, 1, 0, 1, 0, 1, 2, 2, 3, 4, 5, 5, 7, 8, 10, 12, 14, 17, 21, 25, 30, 36, 43, 51, 60, 71, 83, 97, 113, 132, 153, 178, 205, 238, 272, 315, 360, 413, 471, 539, 613, 698, 792, 899, 1018, 1153, 1302, 1470, 1658, 1867, 2100, 2362, 2652, 2974, 3335, 3734, 4178, 4672
Offset: 0
The strict partition (6,4,3,2,1) has submultisets {1,4} and {2,3} with sum 5 so is counted under a(16).
The a(1) = 1 through a(10) = 5 strict partitions:
(1) . (2,1) . (3,2) (4,2) (5,2) (6,2) (7,2) (8,2)
(3,2,1) (4,2,1) (4,3,1) (4,3,2) (5,3,2)
(5,2,1) (5,3,1) (6,3,1)
(6,2,1) (7,2,1)
(4,3,2,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
-------------------------------------------
A240855 counts strict partitions whose length is a part, complement
A240861.
Triangles:
A365661 counts strict partitions with a subset-sum k, non-strict
A365543.
Cf.
A002865,
A126796,
A237113,
A237668,
A238628,
A363225,
A364346,
A364350,
A364533,
A365311,
A365922.
-
Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&MemberQ[Total/@Subsets[#], Length[#]]&]], {n,0,30}]
Comments