A058622 -id:A058622 - cp's OEIS frontend

A117178 Riordan array (c(x^2)/sqrt(1-4x^2), xc(x^2)), c(x) the g.f. of A000108.

1, 0, 1, 3, 0, 1, 0, 4, 0, 1, 10, 0, 5, 0, 1, 0, 15, 0, 6, 0, 1, 35, 0, 21, 0, 7, 0, 1, 0, 56, 0, 28, 0, 8, 0, 1, 126, 0, 84, 0, 36, 0, 9, 0, 1, 0, 210, 0, 120, 0, 45, 0, 10, 0, 1, 462, 0, 330, 0, 165, 0, 55, 0, 11, 0, 1, 0, 792, 0, 495, 0, 220, 0, 66, 0, 12, 0, 1

Offset: 0

Paul Barry, Mar 01 2006

Row sums are A058622(n+1). Diagonal sums are A001791(n+1), with interpolated zeros. Inverse is A117179.

De-aerated and rows reversed, this matrix apparently becomes A014462. The nonzero antidiagonals are embedded in several entries and apparently contain partial sums of previous nonzero antidiagonals. - Tom Copeland, May 30 2017

			Triangle begins
    1;
    0,  1;
    3,  0,  1;
    0,  4,  0,  1;
   10,  0,  5,  0,  1;
    0, 15,  0,  6,  0,  1;
   35,  0, 21,  0,  7,  0,  1;
    0, 56,  0, 28,  0,  8,  0,  1;
  126,  0, 84,  0, 36,  0,  9,  0,  1;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A001791, A014462, A052203, A058622 (row sums), A117179, A224274.

[(1+(-1)^(n-k))*Binomial(n+1, Floor((n-k)/2))/2: k in [0..n], n in [0..15]]; // G. C. Greubel, Aug 08 2022

T[n_, k_]:= Binomial[n+1, (n-k)/2]*(1+(-1)^(n-k))/2;
Table[T[n, k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Aug 08 2022 *)

def A117178(n,k): return (1 + (-1)^(n-k))*binomial(n+1, (n-k)//2)/2
flatten([[A117178(n,k) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Aug 08 2022

T(n,k) = C(n+1, (n-k)/2) * (1 + (-1)^(n-k))/2.
Column k has e.g.f. Bessel_I(k,2x) + Bessel_I(k+2, 2x).
From G. C. Greubel, Aug 08 2022: (Start)
Sum_{k=0..n} T(n, k) = A058622(n+1).
Sum_{k=0..floor(n/2)} T(n-k, k) = ((1+(-1)^n)/2) * A001791((n+2)/2).
T(2*n, n) = ((1+(-1)^n)/2) * A052203(n/2).
T(2*n+1, n) = ((1-(-1)^n)/2) * A224274((n+1)/2).
T(2*n-1, n-1) = ((1+(-1)^n)/2) * A224274(n/2). (End)

A196021 Number of subsets T of S={0,1,2,...,n-1} such that the closure of T under addition modulo n is S.

Original entry on oeis.org

1, 1, 4, 5, 16, 22, 64, 109, 283, 486, 1189, 2174, 5097, 9528, 21904, 41549, 92022, 177043, 387715, 754910, 1624543, 3174095, 6751375, 13296454, 27962241, 55173405, 115220461, 228121892, 472419049, 937688232, 1930884229, 3840200525, 7867929073, 15660179800

Offset: 1

John W. Layman, Sep 26 2011

nonn

			For n = 3, each of the four subsets {0,1}, {0,2}, {1,2}, and {0,1,2} has closure {0,1,2} under addition modulo 3 (for example, {0,2} + {0,2} = {0,2,4} = {0,1,2} modulo 3).  Thus a(3) = 4.

sums:= (s, n)-> {seq(seq(irem(i+j, n), j=s), i=s)}:
b:= (i, n, s)-> `if`(sums(s, n) = {$0..(n-1)}, 2^(n-i),
                `if`(i=n, 0, b(i+1, n, s) +b(i+1, n, {s[], i}))):
a:= n-> b(0, n, {}):
seq(a(n), n=1..15);  # Alois P. Heinz, Oct 21 2011

def sums(s, n):
    return sorted(set((si+sj)%n for i, si in enumerate(s) for sj in s[i:]))
def b(i, n, s):
    if sums(s, n) == list(range(n)): return 2**(n-i)
    if i == n: return 0
    return b(i+1, n, s) + b(i+1, n, sorted(set(s+[i])))
def a(n): return b(0, n, [])
print([a(n) for n in range(1, 19)]) # Michael S. Branicky, Jan 09 2022 after Alois P. Heinz

a(n) >= A058622(n). - Michael Chu, Oct 27 2023

a(21)-a(28) from Alois P. Heinz, Oct 21 2011

a(29)-a(34) from Michael S. Branicky, Jan 09 2022

A346632 Triangle read by rows giving the main diagonals of the matrices counting integer compositions by length and alternating sum (A345197).

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 2, 0, 0, 0, 1, 2, 3, 0, 0, 0, 1, 2, 6, 6, 0, 0, 0, 1, 2, 9, 12, 0, 0, 0, 0, 1, 2, 12, 18, 10, 0, 0, 0, 0, 1, 2, 15, 24, 30, 20, 0, 0, 0, 0, 1, 2, 18, 30, 60, 60, 0, 0, 0, 0, 0, 1, 2, 21, 36, 100, 120, 35, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Jul 26 2021

The matrices (A345197) count the integer compositions of n of length k with alternating sum i, where 1 <= k <= n, and i ranges from -n + 2 to n in steps of 2. The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i.

			Triangle begins:
   1
   0   0
   0   1   0
   0   1   2   0
   0   1   2   0   0
   0   1   2   3   0   0
   0   1   2   6   6   0   0
   0   1   2   9  12   0   0   0
   0   1   2  12  18  10   0   0   0
   0   1   2  15  24  30  20   0   0   0
   0   1   2  18  30  60  60   0   0   0   0
   0   1   2  21  36 100 120  35   0   0   0   0
   0   1   2  24  42 150 200 140  70   0   0   0   0
   0   1   2  27  48 210 300 350 280   0   0   0   0   0
   0   1   2  30  54 280 420 700 700 126   0   0   0   0   0

The first nonzero element in each column appears to be A001405.
These are the diagonals of the matrices given by A345197.
Antidiagonals of the same matrices are A345907.
Row sums are A345908.
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
Other diagonals are A008277 of A318393 and A055884 of A320808.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000070, A000346, A007318, A008549, A025047, A163493, A344610.

ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
Table[Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{k}],k==(n+ats[#])/2&]],{k,n}],{n,0,15}]

A349153 Numbers k such that the k-th composition in standard order has sum equal to twice its reverse-alternating sum.

Original entry on oeis.org

0, 11, 12, 14, 133, 138, 143, 148, 155, 158, 160, 168, 179, 182, 188, 195, 198, 204, 208, 216, 227, 230, 236, 240, 248, 2057, 2066, 2071, 2077, 2084, 2091, 2094, 2101, 2106, 2111, 2120, 2131, 2134, 2140, 2149, 2154, 2159, 2164, 2171, 2174, 2192, 2211, 2214

Offset: 1

Gus Wiseman, Nov 17 2021

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

The reverse-alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(k-i) y_i.

			The terms and corresponding compositions begin:
    0: ()
   11: (2,1,1)
   12: (1,3)
   14: (1,1,2)
  133: (5,2,1)
  138: (4,2,2)
  143: (4,1,1,1,1)
  148: (3,2,3)
  155: (3,1,2,1,1)
  158: (3,1,1,1,2)
  160: (2,6)
  168: (2,2,4)
  179: (2,1,3,1,1)
  182: (2,1,2,1,2)
  188: (2,1,1,1,3)

These compositions are counted by A262977 up to 0's.
Except for 0, a subset of A345917.
The unreversed version is A348614.
The unreversed negative version is A349154.
The negative version is A349155.
A non-reverse unordered version is A349159, counted by A000712 up to 0's.
An unordered version is A349160, counted by A006330 up to 0's.
A003242 counts Carlitz compositions.
A011782 counts compositions.
A025047 counts alternating or wiggly compositions, complement A345192.
A034871, A097805, and A345197 count compositions by alternating sum.
A103919 counts partitions by alternating sum, reverse A344612.
A116406 counts compositions with alternating sum >=0, ranked by A345913.
A138364 counts compositions with alternating sum 0, ranked by A344619.
Cf. A000070, A000346, A001250, A001700, A008549, A027306, A058622, A088218, A114121, A120452, A294175.
Statistics of standard compositions:
- The compositions themselves are the rows of A066099.
- Number of parts is given by A000120, distinct A334028.
- Sum and product of parts are given by A070939 and A124758.
- Maximum and minimum parts are given by A333766 and A333768.
- Heinz number is given by A333219.
Classes of standard compositions:
- Partitions and strict partitions are ranked by A114994 and A333256.
- Multisets and sets are ranked by A225620 and A333255.
- Strict and constant compositions are ranked by A233564 and A272919.
- Carlitz compositions are ranked by A333489, complement A348612.
- Alternating compositions are ranked by A345167, complement A345168.

stc[n_]:=Differences[ Prepend[Join@@Position[ Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
sats[y_]:=Sum[(-1)^(i-Length[y])*y[[i]],{i,Length[y]}];
Select[Range[0,1000],Total[stc[#]]==2*sats[stc[#]]&]

A117186 Expansion of (1+x)c(x^2)/((1-xc(x^2))*sqrt(1-4x^2)), c(x) the g.f. of A000108.

Original entry on oeis.org

1, 2, 5, 9, 21, 38, 86, 157, 349, 642, 1410, 2610, 5682, 10572, 22860, 42717, 91869, 172298, 368906, 694054, 1480486, 2793012, 5938740, 11230834, 23813746, 45131348, 95462996, 181268292, 382594884, 727747608, 1533053976

Offset: 0

Paul Barry, Mar 01 2006

Row sums of triangle A117184.

G.f.: (1+x)(sqrt(1-4x^2)+2x-1)/(2x(1-2x)*sqrt(1-4x^2)); a(n)=sum{k=0..n, C(n+1,(n+k)/2+1)(1+(-1)^(n-k))/2+C(n,(n+k)/2+1/2)(1-(-1)^(n-k))/2}.
G.f.: (1+x)(1+2x-sqrt(1-4x^2))/(2x(1-4x^2)); a(n)=(3*2^n-binomial(2*floor((n+1)/2),floor((n+1)/2)))/2; - Paul Barry, Jan 20 2008
Conjecture: a(n) = A058622(n) + A058622(n+1). [R. J. Mathar, Nov 21 2008]
Conjecture: -(n+1)*a(n) +(n+1)*a(n-1) +2*(3*n-2)*a(n-2) -4*n*a(n-3) +8*(3-n)*a(n-4)=0. - R. J. Mathar, Nov 15 2011

A290888 Number of independent vertex sets and vertex covers in the n-folded cube graph.

Original entry on oeis.org

3, 5, 31, 393, 177347, 2932100733

Offset: 2

Andrew Howroyd, Aug 15 2017

The independence number of the n-folded cube graphs is given by A058622(n-1).

Eric Weisstein's World of Mathematics, Folded Cube Graph.
Eric Weisstein's World of Mathematics, Independent Vertex Set.
Eric Weisstein's World of Mathematics, Vertex Cover.

Row sums of A355227.

Cf. A027624, A058622, A301460.

A355227 Irregular triangle read by rows where T(n,k) is the number of independent sets of size k in the n-folded cube graph.

Original entry on oeis.org

1, 2, 1, 4, 1, 8, 12, 8, 2, 1, 16, 80, 160, 120, 16, 1, 32, 400, 2560, 9280, 20256, 28960, 31520, 29880, 24320, 16336, 8768, 3640, 1120, 240, 32, 2, 1, 64, 1792, 29120, 307440, 2239552, 11682944, 44769920, 128380880, 279211520, 464621248, 593908224, 582529360, 435648640, 245610720, 102886976, 31658620, 7189056, 1239840, 165760, 17584, 1408, 64

Offset: 2

Christopher Flippen, Jun 24 2022

The independence number alpha(G) of a graph is the cardinality of the largest independent vertex set. The n-folded cube has alpha(G) = A058622(n-1). The independence polynomial for the n-folded cube is given by Sum_{k=0..alpha(G)} T(n,k)*t^k.

Since 0 <= k <= alpha(G), row n has length A058622(n-1) + 1.

			Triangle begins:
    k = 1   2   3    4    5   6
n = 2:  1,  2
n = 3:  1,  4
n = 4:  1,  8, 12,   8,   2
n = 5:  1, 16, 80, 160, 120, 16
The 5-folded cube graph has independence polynomial 1 + 16*t + 80*t^2 + 160*t^3 + 120*t^4 + 16*t^5.

Eric Weisstein's World of Mathematics, Independence polynomial
Eric Weisstein's World of Mathematics, Folded cube graph

Row sums are A290888.

Cf. A058622, A355559.

from sage.graphs.independent_sets import IndependentSets
def row(n):
    g = graphs.FoldedCubeGraph(n)
    if n % 2 == 0:
        setCounts = [0] * (pow(2, n-2) + 1)
    else:
        size = int(pow(2, n-2) - 1/4 * (1-pow(-1,n)) * math.comb(n-1, 1/2 * (n-1)) + 1)
        setCounts = [0] * size
    for Iset in IndependentSets(g):
        setCounts[len(Iset)] += 1
    return setCounts

A355559 The independence polynomial of the n-folded cube graph evaluated at -1.

Original entry on oeis.org

-1, -3, -1, 9, 131, 253, 25607

Offset: 2

Christopher Flippen, Jul 06 2022

The independence number alpha(G) of a graph is the cardinality of the largest independent vertex set. The n-folded cube has alpha(G) = A058622(n-1). The independence polynomial for the n-folded cube is given by Sum_{k=0..alpha(G)} A355227(n,k)*t^k, meaning that a(n) is the alternating sum of row n of A355227.

			Row 5 of A355227 is 1, 16, 80, 160, 120, 16. This means the 5-folded cube graph has independence polynomial 1 + 16*t + 80*t^2 + 160*t^3 + 120*t^4 + 16*t^5. Taking the alternating row sum of row 5, or evaluating the polynomial at -1, gives us 1 - 16 + 80 - 160 + 120 - 16 = 9 = a(5).

Eric Weisstein's World of Mathematics, Independence polynomial
Eric Weisstein's World of Mathematics, Folded cube graph

Cf. A058622, A355227, A290888.

from sage.graphs.independent_sets import IndependentSets
def a(n):
    icount=0
    for Iset in IndependentSets(graphs.FoldedCubeGraph(n)):
        if len(Iset) % 2 == 0:
            icount += 1
        else:
            icount += -1
    return icount

A371570 Number of binary necklaces of length n which have more 01 than 00 substrings.

Original entry on oeis.org

0, 0, 2, 3, 6, 15, 29, 56, 118, 237, 467, 946, 1905, 3796, 7618, 15303, 30614, 61319, 122951, 246202, 492971, 987542, 1977560, 3959289, 7927969, 15873190, 31776708, 63614397, 127346134, 254908115, 510233309, 1021273672, 2044071894, 4091064805, 8187770675

Offset: 0

Robert P. P. McKone, Mar 28 2024

nonn

A necklace may also be referred to as circular or cyclic strings.

			a(3) = 3: 011, 101, 110.
a(4) = 6: 0101, 0111, 1010, 1011, 1101, 1110.
a(5) = 15: 00101, 01001, 01010, 01011, 01101, 01111, 10010, 10100, 10101, 10110, 10111, 11010, 11011, 11101, 11110.

Cf. A217464 (necklaces with equal 00 and 01), A371668 (necklaces with more 00 than 01).
Cf. A126869 (necklaces with equal 00 and 11, for n>=1), A058622 (necklaces with more 00 than 11).
Cf. A163493 (strings with equal 00 and 01), A371358 (strings with more 00 than 01), A371564 (strings with more 01 than 00).

tup[n_] := Tuples[{0, 1}, n];
tupToNec[n_] := Map[Append[#, #[[1]]] &, tup[n]];
cou[lst_List] := Count[lst, {0, 1}] > Count[lst, {0, 0}];
par[lst_List] := Partition[lst, 2, 1];
a[0] = 0;
a[n_] := Map[cou, Map[par, tupToNec[n]]] // Boole // Total;
Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}]

a(n) = 2^n - A217464(n) - A371668(n).

a(n) = -(((n-3)*(n-2) - 8*(n-5)^2*(n-2)*a(n-5) + 4*(n*((3n-34)*n+117)-114)*a(n-4) + 2*(((32-3n)*n-95)*n+62)*a(n-3) + (((5n-52)*n+157)*n-114)*a(n-2) + (((39-4n)*n-103)*n+58)*a(n-1))/((n-6)*(n-3)*n)) for n>=7.

A371668 Number of binary necklaces of length n which have more 00 than 01 substrings.

Original entry on oeis.org

0, 1, 1, 1, 5, 11, 19, 43, 93, 181, 371, 771, 1547, 3121, 6357, 12821, 25805, 52123, 105031, 211243, 425215, 855457, 1719257, 3455153, 6942387, 13942111, 27993317, 56197117, 112785797, 226311535, 454043339, 910778203, 1826666093, 3663122277, 7344953123

Offset: 0

Robert P. P. McKone, Apr 02 2024

nonn

			a(3) = 1: 000.
a(4) = 5: 0000, 0001, 0010, 0100, 1000.
a(5) = 11: 00000, 00001, 00010, 00011, 00100, 00110, 01000, 01100, 10000, 10001, 11000.

Cf. A217464 (necklaces with equal 00 and 01), A371570 (necklaces with more 01 than 00).
Cf. A126869 (necklaces with equal 00 and 11, for n>=1), A058622 (necklaces with more 00 than 11).
Cf. A163493 (strings with equal 00 and 01), A371358 (strings with more 00 than 01), A371564 (strings with more 01 than 00).

tup[n_] := Tuples[{0, 1}, n];
tupToNec[n_] := Map[Append[#, #[[1]]] &, tup[n]];
cou[lst_List] := Count[lst, {0, 0}] > Count[lst, {0, 1}];
par[lst_List] := Partition[lst, 2, 1];
a[0] = 0;
a[n_] := a[n] = Map[cou, Map[par, tupToNec[n]]] // Boole // Total;
Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}]

a(n) = 2^n - A217464(n) - A371570(n).

a(n) = (8*(n-7)*a(n-7) + 4*(29-5*n)*a(n-6) + (26*n-110)*a(n-5) + (77-23*n)*a(n-4) + (15*n-46)*a(n-3) + (22-10*n)*a(n-2) + 5*(n-1)*a(n-1))/n for n>=7.

cp's OEIS Frontend

A117178 Riordan array (c(x^2)/sqrt(1-4*x^2), x*c(x^2)), c(x) the g.f. of A000108.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A196021 Number of subsets T of S={0,1,2,...,n-1} such that the closure of T under addition modulo n is S.

Views

Author

Keywords

Examples

Programs

Maple

Python

Formula

Extensions

A346632 Triangle read by rows giving the main diagonals of the matrices counting integer compositions by length and alternating sum (A345197).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A349153 Numbers k such that the k-th composition in standard order has sum equal to twice its reverse-alternating sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A117186 Expansion of (1+x)c(x^2)/((1-xc(x^2))*sqrt(1-4x^2)), c(x) the g.f. of A000108.

Views

Author

Keywords

Comments

Formula

A290888 Number of independent vertex sets and vertex covers in the n-folded cube graph.

Views

Author

Keywords

Comments

Links

Crossrefs

A355227 Irregular triangle read by rows where T(n,k) is the number of independent sets of size k in the n-folded cube graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

A355559 The independence polynomial of the n-folded cube graph evaluated at -1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

A371570 Number of binary necklaces of length n which have more 01 than 00 substrings.

Views

Author

Keywords

Comments

A117178 Riordan array (c(x^2)/sqrt(1-4x^2), xc(x^2)), c(x) the g.f. of A000108.