A345197 -id:A345197 - cp's OEIS frontend

A344651 Irregular triangle read by rows where T(n,k) is the number of integer partitions of n with alternating sum k, with k ranging from n mod 2 to n in steps of 2.

1, 1, 1, 1, 2, 1, 2, 2, 1, 4, 2, 1, 3, 5, 2, 1, 7, 5, 2, 1, 5, 9, 5, 2, 1, 12, 10, 5, 2, 1, 7, 17, 10, 5, 2, 1, 19, 19, 10, 5, 2, 1, 11, 28, 20, 10, 5, 2, 1, 30, 33, 20, 10, 5, 2, 1, 15, 47, 35, 20, 10, 5, 2, 1, 45, 57, 36, 20, 10, 5, 2, 1, 22, 73, 62, 36, 20, 10, 5, 2, 1

Offset: 0

Gus Wiseman, Jun 05 2021

The alternating sum of a partition (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. This is equal to the number of odd parts in the conjugate partition, so T(n,k) is the number of integer partitions of n with k odd parts in the conjugate partition, which is also the number of partitions of n with k odd parts.

Also the number of integer partitions of n with odd-indexed parts (odd bisection) summing to k, ceiling(n/2) <= k <= n. The even-indexed version is A346633. - Gus Wiseman, Nov 29 2021

			Triangle begins:
   1
   1
   1   1
   2   1
   2   2   1
   4   2   1
   3   5   2   1
   7   5   2   1
   5   9   5   2   1
  12  10   5   2   1
   7  17  10   5   2   1
  19  19  10   5   2   1
  11  28  20  10   5   2   1
  30  33  20  10   5   2   1
  15  47  35  20  10   5   2   1
  45  57  36  20  10   5   2   1
  22  73  62  36  20  10   5   2   1
  67  92  64  36  20  10   5   2   1
  30 114 102  65  36  20  10   5   2   1
  97 147 107  65  36  20  10   5   2   1
Row n = 10 counts the following partitions (A = 10):
  (55)          (64)         (73)       (82)     (91)   (A)
  (3322)        (442)        (433)      (622)    (811)
  (4411)        (541)        (532)      (721)
  (222211)      (3331)       (631)      (7111)
  (331111)      (4222)       (5221)     (61111)
  (22111111)    (4321)       (6211)
  (1111111111)  (5311)       (42211)
                (22222)      (52111)
                (32221)      (511111)
                (33211)      (4111111)
                (43111)
                (322111)
                (421111)
                (2221111)
                (3211111)
                (31111111)
                (211111111)
The conjugate version is:
  (A)      (55)      (3331)     (331111)    (31111111)   (1111111111)
  (64)     (73)      (5311)     (511111)    (211111111)
  (82)     (91)      (7111)     (3211111)
  (442)    (433)     (33211)    (4111111)
  (622)    (532)     (43111)    (22111111)
  (4222)   (541)     (52111)
  (22222)  (631)     (61111)
           (721)     (322111)
           (811)     (421111)
           (3322)    (2221111)
           (4321)
           (4411)
           (5221)
           (6211)
           (32221)
           (42211)
           (222211)

This is A103919 with all zeros removed.
The strict version is A152146 interleaved with A152157.
The rows are those of A239830 interleaved with those of A239829.
The reverse version is the right half of A344612.
The strict reverse version is the right half of A344739.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A027187 counts partitions with rev-alternating sum <= 0, ranked by A028260.
A124754 lists alternating sums of standard compositions (reverse: A344618).
A316524 is the alternating sum of the prime indices of n (reverse: A344616).
A325534/A325535 count separable/inseparable partitions.
A344607 counts partitions with rev-alternating sum >= 0, ranked by A344609.
A344608 counts partitions with rev-alternating sum < 0, ranked by A119899.
A344610 counts partitions of n by positive rev-alternating sum.
A344611 counts partitions of 2n with rev-alternating sum >= 0.
A345197 counts compositions by sum, length, and alternating sum.
A346697 gives the sum of odd-indexed prime indices (reverse: A346699).
A346702 represents the odd bisection of compositions, sums A209281.
Cf. A000070, A000097, A003242, A006330, A025047, A097805, A114121, A116406, A131577, A344617, A344649, A344650, A344654, A346633.

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

A058622 a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).

Original entry on oeis.org

0, 1, 1, 4, 5, 16, 22, 64, 93, 256, 386, 1024, 1586, 4096, 6476, 16384, 26333, 65536, 106762, 262144, 431910, 1048576, 1744436, 4194304, 7036530, 16777216, 28354132, 67108864, 114159428, 268435456, 459312152, 1073741824, 1846943453

Offset: 0

Yong Kong (ykong(AT)curagen.com), Dec 29 2000

a(n) is the number of n-digit binary sequences that have more 1's than 0's. - Geoffrey Critzer, Jul 16 2009
Maps to the number of walks that end above 0 on the number line with steps being 1 or -1. - Benjamin Phillabaum, Mar 06 2011
Chris Godsil observes that a(n) is the independence number of the (n+1)-folded cube graph; proof is by a Cvetkovic's eigenvalue bound to establish an upper bound and a direct construction of the independent set by looking at vertices at an odd (resp., even) distance from a fixed vertex when n is odd (resp., even). - Stan Wagon, Jan 29 2013
Also the number of subsets of {1,2,...,n} that contain more odd than even numbers.  For example, for n=4, a(4)=5 and the 5 subsets are {1}, {3}, {1,3}, {1,2,3}, {1,3,4}. See A014495 when same number of even and odd numbers. - Enrique Navarrete, Feb 10 2018
Also half the number of length-n binary sequences with a different number of zeros than ones. This is also the number of integer compositions of n with nonzero alternating sum, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. Also the number of integer compositions of n+1 with alternating sum <= 0, ranked by A345915 (reverse: A345916). - Gus Wiseman, Jul 19 2021

			G.f. = x + x^2 + 4*x^3 + 5*x^4 + 16*x^5 + 22*x^6 + 64*x^7 + 93*x^8 + ...
From _Gus Wiseman_, Jul 19 2021: (Start)
The a(1) = 1 through a(5) = 16 compositions with nonzero alternating sum:
  (1)  (2)  (3)      (4)      (5)
            (1,2)    (1,3)    (1,4)
            (2,1)    (3,1)    (2,3)
            (1,1,1)  (1,1,2)  (3,2)
                     (2,1,1)  (4,1)
                              (1,1,3)
                              (1,2,2)
                              (1,3,1)
                              (2,1,2)
                              (2,2,1)
                              (3,1,1)
                              (1,1,1,2)
                              (1,1,2,1)
                              (1,2,1,1)
                              (2,1,1,1)
                              (1,1,1,1,1)
(End)

A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.1.7)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Folded Cube Graph
Eric Weisstein's World of Mathematics, Independence Number

The odd bisection is A000302.
The even bisection is A000346.
The following relate to compositions with nonzero alternating sum:
- The complement is counted by A001700 or A138364.
- The version for alternating sum > 0 is A027306.
- The unordered version is A086543 (even bisection: A182616).
- The version for alternating sum < 0 is A294175.
- These compositions are ranked by A345921.
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A345197 counts compositions by length and alternating sum.
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 A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000070, A000097, A007318, A008549, A034871, A114121, A120452, A163493, A210736, A239830, A344611.

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

Table[Sum[Binomial[n, Floor[n/2 + i]], {i, 1, n}], {n, 0, 32}] (* Geoffrey Critzer, Jul 16 2009 *)
a[n_] := If[n < 0, 0, (2^n - Boole[EvenQ @ n] Binomial[n, Quotient[n, 2]])/2]; (* Michael Somos, Nov 22 2014 *)
a[n_] := If[n < 0, 0, n! SeriesCoefficient[(Exp[2 x] - BesselI[0, 2 x])/2, {x, 0, n}]]; (* Michael Somos, Nov 22 2014 *)
Table[2^(n - 1) - (1 + (-1)^n) Binomial[n, n/2]/4, {n, 0, 40}] (* Eric W. Weisstein, Mar 21 2018 *)
CoefficientList[Series[2 x/((1-2x)(1 + 2x + Sqrt[(1+2x)(1-2x)])), {x, 0, 40}], x] (* Eric W. Weisstein, Mar 21 2018 *)
ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],ats[#]!=0&]],{n,0,15}] (* Gus Wiseman, Jul 19 2021 *)

a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n\2); \\ Michel Marcus, Dec 30 2015

my(x='x+O('x^100)); concat(0, Vec(2*x/((1-2*x)*(1+2*x+((1+2*x)*(1-2*x))^(1/2))))) \\ Altug Alkan, Dec 30 2015

from math import comb
def A058622(n): return (1<>1)>>1) if n else 0 # Chai Wah Wu, Aug 25 2025

[(2^n - binomial(n, n//2)*((n+1)%2))/2 for n in (0..40)] # G. C. Greubel, Aug 08 2022

a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).
a(n) = Sum_{i=0..floor((n-1)/2)} binomial(n, i).
G.f.: 2*x/((1-2*x)*(1+2*x+((1+2*x)*(1-2*x))^(1/2))). - Vladeta Jovovic, Apr 27 2003
E.g.f: (e^(2x)-I_0(2x))/2 where I_n is the Modified Bessel Function. - Benjamin Phillabaum, Mar 06 2011
Logarithmic derivative of the g.f. of A210736 is a(n+1). - Michael Somos, Nov 22 2014
Even index: a(2n) = 2^(n-1) - A088218(n). Odd index: a(2n+1) = 2^(2n). - Gus Wiseman, Jul 19 2021
D-finite with recurrence n*a(n) +2*(-n+1)*a(n-1) +4*(-n+1)*a(n-2) +8*(n-2)*a(n-3)=0. - R. J. Mathar, Sep 23 2021
a(n) = 2^n-A027306(n). - R. J. Mathar, Sep 23 2021
A027306(n) - a(n) = A126869(n). - R. J. Mathar, Sep 23 2021

A294175 a(n) = 2^(n-1) + ((1+(-1)^n)/4)*binomial(n, n/2) - binomial(n, floor(n/2)).

Original entry on oeis.org

0, 0, 1, 1, 5, 6, 22, 29, 93, 130, 386, 562, 1586, 2380, 6476, 9949, 26333, 41226, 106762, 169766, 431910, 695860, 1744436, 2842226, 7036530, 11576916, 28354132, 47050564, 114159428, 190876696, 459312152, 773201629, 1846943453, 3128164186, 7423131482

Offset: 0

Enrique Navarrete, Feb 10 2018

nonn

Number of subsets of {1,2,...,n} that contain more even than odd numbers.
Note that A058622 counts the nonempty subsets of {1,2,...,n} that contain more odd than even numbers.
From Gus Wiseman, Jul 22 2021: (Start)
Also the number of integer compositions of n + 1 with alternating sum < 0, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(0) = 0 through a(6) = 6 compositions (empty columns indicated by dots) are:
  .  .  (12)  (13)  (14)    (15)
                    (23)    (24)
                    (131)   (141)
                    (1112)  (1113)
                    (1211)  (1212)
                            (1311)
Also the number of integer compositions of n + 1 with reverse-alternating sum < 0. For a bijection, keep the odd-length compositions and reverse the even-length ones.
Also the number of (n+1)-digit binary numbers with more 0's than 1's. For example, the a(0) = 0 through a(5) = 6 binary numbers are:
  .  .  100  1000  10000  100000
                   10001  100001
                   10010  100010
                   10100  100100
                   11000  101000
                          110000
(End)
2*a(n) is the number of all-positive pinnacle sets that are admissible in the group S_{n+1}^B of signed permutations, but not admissible in S_{n+1}. - Bridget Tenner, Jan 06 2023

			For example, for n=5, a(5)=6 and the 6 subsets are {2}, {4}, {2,4}, {1,2,4}, {2,3,4}, {2,4,5}.

Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO] (2023).

The even bisection is A000346.
The odd bisection is A008549.
The following relate to compositions of n + 1 with alternating sum k < 0.
- The k = 1 version is A000984, ranked by A345909/A345911.
- The opposite (k > 0) version is A027306, ranked by A345917/A345918.
- The weak (k <= 0) version A058622, ranked by A345915/A345916.
- The k != 0 version is also A058622, ranked by A345921.
- The complement (k >= 0) is counted by A116406, ranked by A345913/A345914.
- The k = 0 version is A138364, ranked by A344619.
- The unordered version is A344608, ranked by A119899.
- Ranked by A345919 (reverse: A345920).
A097805 counts compositions by alternating (or reverse-alternating) sum.
A101211 lists run-lengths in binary expansion (reverse: A227736).
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A345197 counts compositions by length and alternating sum.
Cf. A000070, A001700, A007318, A025047, A032443, A034871, A106356, A114121, A126869, A163493, A344743, A345908, A289871, A359066, A359067.

f:= gfun:-rectoproc({(8+8*n)*a(n)+(4*n+16)*a(1+n)+(-20-6*n)*a(n+2)+(-5-n)*a(n+3)+(5+n)*a(n+4), a(0) = 0, a(1) = 0, a(2) = 1, a(3) = 1}, a(n), remember):
map(f, [$0..40]); # Robert Israel, Feb 12 2018

f[n_] := 2^(n - 1) + ((1 + (-1)^n)/4) Binomial[n, n/2] - Binomial[n, Floor[n/2]]; Array[f, 38, 0] (* Robert G. Wilson v, Feb 10 2018 *)
Table[Length[Select[Tuples[{0,1},{n+1}],First[#]==1&&Count[#,0]>Count[#,1]&]],{n,0,10}] (* Gus Wiseman, Jul 22 2021 *)

From Robert Israel, Feb 12 2018: (Start)
G.f.: (x+1)*sqrt(1-4*x^2)/(2*x*(4*x^2-1))+(x-1)/(2*(2*x-1)*x).
D-finite with recurrence: (8+8*n)*a(n)+(4*n+16)*a(1+n)+(-20-6*n)*a(n+2)+(-5-n)*a(n+3)+(5+n)*a(n+4) = 0. (End)

A163493 Number of binary strings of length n which have the same number of 00 and 01 substrings.

Original entry on oeis.org

1, 2, 2, 3, 6, 9, 15, 30, 54, 97, 189, 360, 675, 1304, 2522, 4835, 9358, 18193, 35269, 68568, 133737, 260802, 509132, 995801, 1948931, 3816904, 7483636, 14683721, 28827798, 56637969, 111347879, 219019294, 431043814, 848764585, 1672056525, 3295390800, 6497536449

Offset: 0

Christopher Carl Heckman, Jul 29 2009

nonn

A variation of problem 11424 in the American Mathematical Monthly. Terms were brute-force calculated using Maple 10.
Proposed Problem 11610 in the Dec 2011 A.M.M.
From Gus Wiseman, Jul 27 2021: (Start)
Also the antidiagonal sums of the matrices counting integer compositions by length and alternating sum (A345197). So a(n) is the number of integer compositions of n + 1 of length (n - s + 3)/2, where s is the alternating sum of the composition. For example, the a(0) = 1 through a(6) = 7 compositions are:
  (1)  (2)   (3)   (4)    (5)     (6)     (7)
       (11)  (21)  (31)   (41)    (51)    (61)
                   (121)  (122)   (123)   (124)
                          (221)   (222)   (223)
                          (1112)  (321)   (322)
                          (1211)  (1122)  (421)
                                  (1221)  (1132)
                                  (2112)  (1231)
                                  (2211)  (2122)
                                          (2221)
                                          (3112)
                                          (3211)
                                          (11131)
                                          (12121)
                                          (13111)
For a bijection with the main (binary string) interpretation, take the run-lengths of each binary string of length n + 1 that satisfies the condition and starts with 1.
(End)

			1 + 2*x + 2*x^2 + 3*x^3 + 6*x^4 + 9*x^5 + 15*x^6 + 30*x^7 + 54*x^8 + 97*x^9 + ...
From _Gus Wiseman_, Jul 27 2021: (Start)
The a(0) = 1 though a(6) = 15 binary strings:
  ()  (0)  (1,0)  (0,0,1)  (0,0,1,0)  (0,0,1,1,0)  (0,0,0,1,0,1)
      (1)  (1,1)  (1,1,0)  (0,0,1,1)  (0,0,1,1,1)  (0,0,1,0,0,1)
                  (1,1,1)  (0,1,0,0)  (0,1,1,0,0)  (0,0,1,1,1,0)
                           (1,0,0,1)  (1,0,0,1,0)  (0,0,1,1,1,1)
                           (1,1,1,0)  (1,0,0,1,1)  (0,1,0,0,0,1)
                           (1,1,1,1)  (1,0,1,0,0)  (0,1,1,1,0,0)
                                      (1,1,0,0,1)  (1,0,0,1,1,0)
                                      (1,1,1,1,0)  (1,0,0,1,1,1)
                                      (1,1,1,1,1)  (1,0,1,1,0,0)
                                                   (1,1,0,0,1,0)
                                                   (1,1,0,0,1,1)
                                                   (1,1,0,1,0,0)
                                                   (1,1,1,0,0,1)
                                                   (1,1,1,1,1,0)
                                                   (1,1,1,1,1,1)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..3328 (first 501 terms from R. H. Hardin)
Shalosh B. Ekhad and Doron Zeilberger, Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type, arXiv preprint arXiv:1112.6207 [math.CO], 2011. See subpages for rigorous derivations of g.f., recurrence, asymptotics for this sequence. [From _N. J. A. Sloane_, Apr 07 2012]
R. Stanley, Problem 11610, Amer. Math. Monthly, 118 (2011), 937; 120 (2013), 943-944.

Antidiagonal sums of the matrices A345197.
Row sums of A345907.
Taking diagonal instead of antidiagonal sums gives A345908.
A011782 counts compositions (or binary strings).
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).
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. A000041, A000070, A000096, A000097, A000124, A000346, A007318, A008549, A025047, A131577, A238279.

with(combinat): count := proc(n) local S, matches, A, k, i; S := subsets(\{seq(i, i=1..n)\}): matches := 0: while not S[finished] do A := S[nextvalue](): k := 0: for i from 1 to n-1 do: if not (i in A) and not (i+1 in A) then k := k + 1: fi: if not (i in A) and (i+1 in A) then k := k - 1: fi: od: if (k = 0) then matches := matches + 1: fi: end do; return(matches); end proc:
# second Maple program:
b:= proc(n, l, t) option remember; `if`(n-abs(t)<0, 0, `if`(n=0, 1,
      add(b(n-1, i, t+`if`(l=0, (-1)^i, 0)), i=0..1)))
    end:
a:= n-> b(n, 1, 0):
seq(a(n), n=0..36);  # Alois P. Heinz, Mar 20 2024

a[0] = 1; a[n_] := Sum[Binomial[2*k - 1, k]*Binomial[n - 2*k, k] + Binomial[2*k, k]*Binomial[n - 2*k - 1, k], {k, 0, n/3}];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 28 2017, after Joel B. Lewis *)
Table[Length[Select[Tuples[{0,1},n],Count[Partition[#,2,1],{0,0}]==Count[Partition[#,2,1],{0,1}]&]],{n,0,10}] (* Gus Wiseman, Jul 27 2021 *)
a[0]:=1; a[n_]:=(1 + 3*HypergeometricPFQ[{1/2, 1-3*n/8, (1-n)/3, (2-n)/3, -n/3},{1, (1-n)/2, 1-n/2, -3*n/8}, -27])/2; Array[a,37,0] (* Stefano Spezia, Apr 26 2024 *)

from math import comb
def A163493(n): return 2+sum((x:=comb((k:=m<<1)-1,m)*comb(n-k,m))+(x*(n-3*m)<<1)//(n-k) for m in range(1,n//3+1)) if n else 1 # Chai Wah Wu, May 01 2024

G.f.: 1/2/(1-x) + (1+2*x)/2/sqrt((1-x)*(1-2*x)*(1+x+2*x^2)). - Richard Stanley, corrected Apr 29 2011
G.f.: (1 + sqrt( 1 + 4*x / ((1 - x) * (1 - 2*x) * (1 + x + 2*x^2)))) / (2*(1 - x)). - Michael Somos, Jan 30 2012
a(n) = sum( binomial(2*k-1, k)*binomial(n-2*k,k) + binomial(2*k, k)*binomial(n-2*k-1, k), k=0..floor(n/3)). - Joel B. Lewis, May 21 2011
Conjecture: -n*a(n) +(2+n)*a(n-1) +(3n-12)*a(n-2) +(12-n)*a(n-3) +(2n-18)*a(n-4)+(56-12n)*a(n-5) +(8n-40)*a(n-6)=0. - R. J. Mathar, Nov 28 2011
G.f. y = A(x) satisfies x = (1 - x) * (1 - 2*x) * (1 + x + 2*x^2) * y * (y * (1 - x) - 1). - Michael Somos, Jan 30 2012
Sequence a(n) satisfies 0 = a(n) * (n^2-2*n) + a(n-1) * (-3*n^2+8*n-2) + a(n-2) * (3*n^2-10*n+2) + a(n-3) * (-5*n^2+18*n-6) + a(n-4) * (8*n^2-34*n+22) + a(n-5) * (-4*n^2+20*n-16) except if n=1 or n=2. - Michael Somos, Jan 30 2012
a(n) = (1 + 3*hypergeom([1/2, 1-3*n/8, (1-n)/3, (2-n)/3, -n/3],[1, (1-n)/2, 1-n/2, -3*n/8],-27))/2 for n > 0. - Stefano Spezia, Apr 26 2024
a(n) ~ 2^n / sqrt(Pi*n). - Vaclav Kotesovec, Apr 26 2024

A262977 a(n) = binomial(4*n-1,n).

Original entry on oeis.org

1, 3, 21, 165, 1365, 11628, 100947, 888030, 7888725, 70607460, 635745396, 5752004349, 52251400851, 476260169700, 4353548972850, 39895566894540, 366395202809685, 3371363686069236, 31074067324187580, 286845713747883300, 2651487106659130740, 24539426037817994160

Offset: 0

Vladimir Kruchinin, Oct 06 2015

From Gus Wiseman, Sep 28 2022: (Start)
Also the number of integer compositions of 4n with alternating sum 2n, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. These compositions are ranked by A348614. The a(12) = 21 compositions are:
  (6,2)  (1,2,5)  (1,1,5,1)  (1,1,1,1,4)
         (2,2,4)  (2,1,4,1)  (1,1,2,1,3)
         (3,2,3)  (3,1,3,1)  (1,1,3,1,2)
         (4,2,2)  (4,1,2,1)  (1,1,4,1,1)
         (5,2,1)  (5,1,1,1)  (2,1,1,1,3)
                             (2,1,2,1,2)
                             (2,1,3,1,1)
                             (3,1,1,1,2)
                             (3,1,2,1,1)
                             (4,1,1,1,1)
The following pertain to this interpretation:
- The case of partitions is A000712, reverse A006330.
- Allowing any alternating sum gives A013777 (compositions of 4n).
- A011782 counts compositions of n.
- A034871 counts compositions of 2n with alternating sum 2k.
- A097805 counts compositions by alternating (or reverse-alternating) sum.
- A103919 counts partitions by sum and alternating sum (reverse: A344612).
- A345197 counts compositions by length and alternating sum.
(End)

V. V. Kruchinin and D. V. Kruchinin, A Generating Function for the Diagonal T_{2n,n} in Triangles, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.6.

Cf. A006632, A002293, A004331, A005810, A052203, A224274, A257633.
Cf. A000346, A000984, A001700, A002458, A025047, A058622, A081294, A294175.
Cf. A088218, A163455, A165817.

[Binomial(4*n-1,n): n in [0..20]]; // Vincenzo Librandi, Oct 06 2015

Table[Binomial[4 n - 1, n], {n, 0, 40}] (* Vincenzo Librandi, Oct 06 2015 *)

B(x):=sum(binomial(4*n-1,n-1)*3/(4*n-1)*x^n,n,1,30);
taylor(x*diff(B(x),x,1)/B(x),x,0,20);

a(n) = binomial(4*n-1,n); \\ Michel Marcus, Oct 06 2015

G.f.: A(x)=x*B'(x)/B(x), where B(x) if g.f. of A006632.
a(n) = Sum_{k=0..n}(binomial(n-1,n-k)*binomial(3*n,k)).
a(n) = 3*A224274(n), for n > 0. - Michel Marcus, Oct 12 2015
From Peter Bala, Nov 04 2015: (Start)
The o.g.f. equals f(x)/g(x), where f(x) is the o.g.f. for A005810 and g(x) is the o.g.f. for A002293. More generally, f(x)*g(x)^k is the o.g.f. for the sequence binomial(4*n + k,n). Cf. A005810 (k = 0), A052203 (k = 1), A257633 (k = 2), A224274 (k = 3) and A004331 (k = 4). (End)
a(n) = [x^n] 1/(1 - x)^(3*n). - Ilya Gutkovskiy, Oct 03 2017
a(n) = A071919(3n-1,n+1) = A097805(4n,n+1). - Gus Wiseman, Sep 28 2022
From Peter Bala, Feb 14 2024: (Start)
a(n) = (-1)^n * binomial(-3*n, n).
a(n) = hypergeom([1 - 3*n, -n], [1], 1).
The g.f. A(x) satisfies A(x/(1 + x)^4) = 1/(1 - 3*x). (End)
a(n) = Sum_{k = 0..n} binomial(2*n+k-1, k)*binomial(2*n-k-1, n-k). - Peter Bala, Sep 16 2024
G.f.: 1/(4-3*g) where g = 1+x*g^4 is the g.f. of A002293. - Seiichi Manyama, Aug 17 2025

A345910 Numbers k such that the k-th composition in standard order (row k of A066099) has alternating sum -1.

Original entry on oeis.org

6, 20, 25, 27, 30, 72, 81, 83, 86, 92, 98, 101, 103, 106, 109, 111, 116, 121, 123, 126, 272, 289, 291, 294, 300, 312, 322, 325, 327, 330, 333, 335, 340, 345, 347, 350, 360, 369, 371, 374, 380, 388, 393, 395, 398, 402, 405, 407, 410, 413, 415, 420, 425, 427

Offset: 1

Gus Wiseman, Jul 01 2021

nonn

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

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 sequence of terms together with the corresponding compositions begins:
      6: (1,2)
     20: (2,3)
     25: (1,3,1)
     27: (1,2,1,1)
     30: (1,1,1,2)
     72: (3,4)
     81: (2,4,1)
     83: (2,3,1,1)
     86: (2,2,1,2)
     92: (2,1,1,3)
     98: (1,4,2)
    101: (1,3,2,1)
    103: (1,3,1,1,1)
    106: (1,2,2,2)
    109: (1,2,1,2,1)

These compositions are counted by A001791.
A version using runs of binary digits is A031444.
These are the positions of -1's in A124754.
The opposite (positive 1) version is A345909.
The reverse version is A345912.
The version for alternating sum of prime indices is A345959.
Standard compositions: A000120, A066099, A070939, A124754, A228351, A344618.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A000070 counts partitions of 2n+1 with alternating sum 1, ranked by A001105.
A011782 counts compositions.
A097805 counts compositions by sum and alternating sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
A345197 counts compositions by sum, length, and alternating sum.
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. A000097, A000346, A008549, A025047, A027187, A031443, A031448, A114121, A119899, A126869, A238279, A344617.

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

A345912 Numbers k such that the k-th composition in standard order (row k of A066099) has reverse-alternating sum -1.

Original entry on oeis.org

5, 18, 23, 25, 29, 68, 75, 78, 81, 85, 90, 95, 98, 103, 105, 109, 114, 119, 121, 125, 264, 275, 278, 284, 289, 293, 298, 303, 308, 315, 318, 322, 327, 329, 333, 338, 343, 345, 349, 356, 363, 366, 369, 373, 378, 383, 388, 395, 398, 401, 405, 410, 415, 418, 423

Offset: 1

Gus Wiseman, Jul 01 2021

nonn

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

			The sequence of terms together with the corresponding compositions begins:
      5: (2,1)
     18: (3,2)
     23: (2,1,1,1)
     25: (1,3,1)
     29: (1,1,2,1)
     68: (4,3)
     75: (3,2,1,1)
     78: (3,1,1,2)
     81: (2,4,1)
     85: (2,2,2,1)
     90: (2,1,2,2)
     95: (2,1,1,1,1,1)
     98: (1,4,2)
    103: (1,3,1,1,1)
    105: (1,2,3,1)

These compositions are counted by A001791.
These are the positions of -1's in A344618.
The non-reverse version is A345910.
The opposite (positive 1) version is A345911.
The version for Heinz numbers of partitions is A345959.
Standard compositions: A000120, A066099, A070939, A228351, A124754, A344618.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
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).
A344610 counts partitions by sum and positive reverse-alternating sum.
A344611 counts partitions of 2n with reverse-alternating sum >= 0.
A345197 counts compositions by sum, length, and alternating sum.
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, A001105, A008549, A025047, A031444, A034871, A114121, A126869, A344608, A345958, A345959.

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,100],sats[stc[#]]==-1&]

A345917 Numbers k such that the k-th composition in standard order (row k of A066099) has alternating sum > 0.

Original entry on oeis.org

1, 2, 4, 5, 7, 8, 9, 11, 14, 16, 17, 18, 19, 21, 22, 23, 26, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 42, 44, 45, 47, 52, 56, 57, 59, 62, 64, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 82, 84, 85, 87, 88, 89, 90, 91, 93, 94, 95, 100, 104, 105, 107

Offset: 1

Gus Wiseman, Jul 08 2021

nonn

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

			The initial terms and the corresponding compositions:
     1: (1)
     2: (2)
     4: (3)
     5: (2,1)
     7: (1,1,1)
     8: (4)
     9: (3,1)
    11: (2,1,1)
    14: (1,1,2)
    16: (5)
    17: (4,1)
    18: (3,2)
    19: (3,1,1)
    21: (2,2,1)
    22: (2,1,2)

The version for Heinz numbers of partitions is A026424.
These compositions are counted by A027306.
These are the positions of terms > 0 in A124754.
The weak (k >= 0) version is A345913.
The reverse-alternating version is A345918.
The opposite (k < 0) version is A345919.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
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).
A345197 counts compositions by sum, length, and alternating sum.
Standard compositions: A000120, A066099, A070939, A228351, A124754, A344618.
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, A008549, A025047, A027187, A027193, A032443, A114121, A163493, A344609, A345908.

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

A345911 Numbers k such that the k-th composition in standard order (row k of A066099) has reverse-alternating sum 1.

Original entry on oeis.org

1, 6, 7, 20, 21, 26, 27, 30, 31, 72, 73, 82, 83, 86, 87, 92, 93, 100, 101, 106, 107, 110, 111, 116, 117, 122, 123, 126, 127, 272, 273, 290, 291, 294, 295, 300, 301, 312, 313, 324, 325, 330, 331, 334, 335, 340, 341, 346, 347, 350, 351, 360, 361, 370, 371, 374

Offset: 1

Gus Wiseman, Jul 01 2021

nonn

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

			The sequence of terms together with the corresponding compositions begins:
     1: (1)
     6: (1,2)
     7: (1,1,1)
    20: (2,3)
    21: (2,2,1)
    26: (1,2,2)
    27: (1,2,1,1)
    30: (1,1,1,2)
    31: (1,1,1,1,1)
    72: (3,4)
    73: (3,3,1)
    82: (2,3,2)
    83: (2,3,1,1)
    86: (2,2,1,2)
    87: (2,2,1,1,1)

These compositions are counted by A000984 (bisection of A126869).
The version for Heinz numbers of partitions is A001105.
A version using runs of binary digits is A066879.
These are positions of 1's in A344618.
The non-reverse version is A345909.
The opposite (negative 1) version is A345912.
The version for prime indices is A345958.
Standard compositions: A000120, A066099, A070939, A228351, A124754, A344618.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
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).
A344610 counts partitions by sum and positive reverse-alternating sum.
A344611 counts partitions of 2n with reverse-alternating sum >= 0.
A345197 counts compositions by sum, length, and alternating sum.
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, A000097, A000346, A008549, A025047, A027193, A031448, A034871, A114121, A120452, A344607.

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,100],sats[stc[#]]==1&]

A345913 Numbers k such that the k-th composition in standard order (row k of A066099) has alternating sum >= 0.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 26, 28, 29, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 50, 52, 53, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 82

Offset: 1

Gus Wiseman, Jul 04 2021

nonn

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

			The sequence of terms together with the corresponding compositions begins:
     0: ()           17: (4,1)          37: (3,2,1)
     1: (1)          18: (3,2)          38: (3,1,2)
     2: (2)          19: (3,1,1)        39: (3,1,1,1)
     3: (1,1)        21: (2,2,1)        41: (2,3,1)
     4: (3)          22: (2,1,2)        42: (2,2,2)
     5: (2,1)        23: (2,1,1,1)      43: (2,2,1,1)
     7: (1,1,1)      26: (1,2,2)        44: (2,1,3)
     8: (4)          28: (1,1,3)        45: (2,1,2,1)
     9: (3,1)        29: (1,1,2,1)      46: (2,1,1,2)
    10: (2,2)        31: (1,1,1,1,1)    47: (2,1,1,1,1)
    11: (2,1,1)      32: (6)            50: (1,3,2)
    13: (1,2,1)      33: (5,1)          52: (1,2,3)
    14: (1,1,2)      34: (4,2)          53: (1,2,2,1)
    15: (1,1,1,1)    35: (4,1,1)        55: (1,2,1,1,1)
    16: (5)          36: (3,3)          56: (1,1,4)

These compositions are counted by A116406.
These are the positions of terms >= 0 in A124754.
The version for prime indices is A344609.
The reverse-alternating sum version is A345914.
The opposite (k <= 0) version is A345915.
The strict (k > 0) version is A345917.
The complement is A345919.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
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).
A345197 counts compositions by sum, length, and alternating sum.
Standard compositions: A000120, A066099, A070939, A228351, A124754, A344618.
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, A008549, A025047, A027187, A032443, A034871, A114121, A163493, A236913, A238279, A344607, A344608, A344610, A344611.

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

cp's OEIS Frontend

A344651 Irregular triangle read by rows where T(n,k) is the number of integer partitions of n with alternating sum k, with k ranging from n mod 2 to n in steps of 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A058622 a(n) = 2^(n-1) - ((1+(-1)^n)/4)*binomial(n, n/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Python

SageMath

Formula

A294175 a(n) = 2^(n-1) + ((1+(-1)^n)/4)*binomial(n, n/2) - binomial(n, floor(n/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A163493 Number of binary strings of length n which have the same number of 00 and 01 substrings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A262977 a(n) = binomial(4*n-1,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Formula

A345910 Numbers k such that the k-th composition in standard order (row k of A066099) has alternating sum -1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A345912 Numbers k such that the k-th composition in standard order (row k of A066099) has reverse-alternating sum -1.

Views

Author

Keywords

Comments

Examples