A034008 -id:A034008 - cp's OEIS frontend

A122391 Dimension of 2-variable non-commutative harmonics (Hausdorff derivative). The dimension of the space of non-commutative polynomials in 2 variables which are killed by all symmetric differential operators (where for a monomial w, d_{xi} ( w ) = sum over all subwords of w deleting xi once).

1, 1, 1, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472, 6442450944, 12884901888, 25769803776

Offset: 0

Mike Zabrocki, Aug 31 2006

Except for first couple of terms, series agrees with A003945.
a(n) written in base 2: a(0) = 1, a(1) = 1, a(2) = 1, a(n) for n >= 3: 11, 110, 11000, 110000, ..., i.e.: 2 times 1, (n-3) times 0 (see A003953(n-2)). - Jaroslav Krizek, Aug 17 2009
For n>=2, a(n) equals the numbers of words of length n-2 on alphabet {0,1,2} containing no subwords 00, 11 and 22. - Milan Janjic, Jan 31 2015
Also the number of compositions of n whose first or last part is equal to 1, for n >= 1. - Peter Luschny, Jan 29 2024

			a(1) = 1 because x1 - x2 is killed by d_x1 + d_x2.
a(2) = 1 because x1 x2 - x2 x1 is killed by d_x1+d_x2, d_x1^2 + d_x2^2.
a(3) = 3 because x1 x1 x2 - 2 x1 x2 x1 + x2 x1 x1, x1 x2 x2 - 2 x2 x1 x2 + x2 x2 x1, x1 x1 x2 - x1 x2 x1 - x2 x1 x2 + x2 x2 x1 are all killed by d_x1 + d_x2, d_x1^2 + d_x2^2, d_x1 d_x2, d_x1^3 + d_x2^3 and d_x1^2 d_x2 + d_x1 d_x2^2.
From _Peter Luschny_, Jan 29 2024: (Start)
Compositions of n with 1 in the first or the last slot.
 1: [1];
 2: [1, 1];
 3: [1, 1, 1], [1, 2], [2, 1];
 4: [1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [3, 1];
 5: [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 1, 3], [1, 2, 1, 1], [1, 2, 2], [1, 3, 1], [1, 4], [2, 1, 1, 1], [2, 2, 1], [3, 1, 1], [4, 1].
(End)

C. Reutenauer, Free Lie algebras. London Mathematical Society Monographs. New Series, 7. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1993. xviii+269 pp.

N. Bergeron, C. Reutenauer, M. Rosas, and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005. See also, Canad. J. Math. 60 (2008), no. 2, 266-296.
C. Chevalley, Invariants of finite groups generated by reflections, Amer. J. Math. 77 (1955), 778-782.
Index entries for linear recurrences with constant coefficients, signature (2).

Cf. A003945, A034008, A122367, A122392, A122393, A122394.

coeffs(convert(series((1-q)*(1-q^2)/(1-2*q),q,20),`+`)-O(q^20),q);

Table[Ceiling[2^(n-2)] + Floor[2^(n-3)], {n,0,30}] (* Martin Grymel, Oct 17 2012 *)

G.f.: (1-q)*(1-q^2)/(1-2*q).
a(n) = 2^n - 2^(n-1) - 2^(n-2) + 2^(n-3) (for n > 2).
a(0) = 1, a(1) = 1, a(2) = 1, a(n) = 3*2^(n-3) for n > 2.
a(n) = 3*2^(n-3) = 2^(n-3) + 2^(n-2) for n >= 3. - Jaroslav Krizek, Aug 17 2009
a(n) = ceiling(2^(n-2)) + floor(2^(n-3)). - Martin Grymel, Oct 17 2012
E.g.f.: (5 + 3*exp(2*x) + 2*x - 2*x^2)/8. - Stefano Spezia, Jan 26 2025

More terms from Michel Marcus, Jan 26 2025

A347704 Number of even-length integer partitions of n with integer alternating product.

Original entry on oeis.org

1, 0, 1, 1, 3, 2, 6, 4, 11, 8, 18, 13, 33, 22, 49, 38, 79, 58, 122, 90, 186, 139, 268, 206, 402, 304, 569, 448, 817, 636, 1152, 907, 1612, 1283, 2220, 1791, 3071, 2468, 4162, 3409, 5655, 4634, 7597, 6283, 10171, 8478, 13491, 11336, 17906, 15088, 23513, 20012

Offset: 0

Gus Wiseman, Sep 17 2021

nonn

We define the alternating product of a sequence (y_1,...,y_k) to be Product_i y_i^((-1)^(i-1)).

			The a(2) = 1 through a(9) = 8 partitions:
  (11)  (21)  (22)    (41)    (33)      (61)      (44)        (63)
              (31)    (2111)  (42)      (2221)    (62)        (81)
              (1111)          (51)      (4111)    (71)        (3321)
                              (2211)    (211111)  (2222)      (4221)
                              (3111)              (3221)      (6111)
                              (111111)            (3311)      (222111)
                                                  (4211)      (411111)
                                                  (5111)      (21111111)
                                                  (221111)
                                                  (311111)
                                                  (11111111)

Allowing any alternating product >= 1 gives A000041, reverse A344607.
Allowing any alternating product gives A027187, odd bisection A236914.
The Heinz numbers of these partitions are given by A028260 /\ A347457.
The reverse and reciprocal versions are both A035363.
The multiplicative version (factorizations) is A347438, reverse A347439.
The odd-length instead of even-length version is A347444.
Allowing any length gives A347446.
A034008 counts even-length compositions, ranked by A053754.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A119620 counts partitions with alternating product 1.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
Cf. A000070, A067661, A236913, A304620, A339846, A347437, A347441, A347442, A347445, A347448, A347449, A347454, A347462.

altprod[q_]:=Product[q[[i]]^(-1)^(i-1),{i,Length[q]}];
Table[Length[Select[IntegerPartitions[n],EvenQ[Length[#]]&&IntegerQ[altprod[#]]&]],{n,0,30}]

A342343 Number of strict compositions of n with alternating parts strictly decreasing.

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 8, 10, 13, 18, 27, 32, 44, 55, 73, 97, 121, 151, 194, 240, 299, 384, 465, 576, 706, 869, 1051, 1293, 1572, 1896, 2290, 2761, 3302, 3973, 4732, 5645, 6759, 7995, 9477, 11218, 13258, 15597, 18393, 21565, 25319, 29703, 34701, 40478, 47278, 54985

Offset: 0

Gus Wiseman, Apr 01 2021

nonn

These are finite odd-length sequences q of distinct positive integers summing to n such that q(i) > q(i+2) for all possible i.

			The a(1) = 1 through a(8) = 13 compositions:
  (1)  (2)  (3)    (4)    (5)    (6)      (7)      (8)
            (1,2)  (1,3)  (1,4)  (1,5)    (1,6)    (1,7)
            (2,1)  (3,1)  (2,3)  (2,4)    (2,5)    (2,6)
                          (3,2)  (4,2)    (3,4)    (3,5)
                          (4,1)  (5,1)    (4,3)    (5,3)
                                 (2,3,1)  (5,2)    (6,2)
                                 (3,1,2)  (6,1)    (7,1)
                                 (3,2,1)  (2,4,1)  (2,5,1)
                                          (4,1,2)  (3,4,1)
                                          (4,2,1)  (4,1,3)
                                                   (4,3,1)
                                                   (5,1,2)
                                                   (5,2,1)

Andrew Howroyd, Table of n, a(n) for n = 0..1000

The non-strict case is A000041 (see A342528 for a bijective proof).
The non-strict odd-length case is A001522.
Strict compositions in general are counted by A032020
The non-strict even-length case is A064428.
The case of reversed partitions is A065033.
A000726 counts partitions with alternating parts unequal.
A003242 counts anti-run compositions.
A027193 counts odd-length compositions.
A034008 counts even-length compositions.
A064391 counts partitions by crank.
A064410 counts partitions of crank 0.
A224958 counts compositions with alternating parts unequal.
A257989 gives the crank of the partition with Heinz number n.
A325548 counts compositions with strictly decreasing differences.
A342194 counts strict compositions with equal differences.
A342527 counts compositions with alternating parts equal.
Cf. A000009, A000670, A008965, A062968, A065608, A109613, A114921, A325546, A332304, A332305, A342532.

ici[q_]:=And@@Table[q[[i]]>q[[i+2]],{i,Length[q]-2}];
Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n],UnsameQ@@#&],ici]],{n,0,15}]

seq(n)={my(p=prod(k=1, n, 1 + y*x^k + O(x*x^n))); Vec(sum(k=0, n, binomial(k, k\2) * polcoef(p,k,y)))} \\ Andrew Howroyd, Apr 16 2021

G.f.: Sum_{k>=0} binomial(k,floor(k/2)) * [y^k](Product_{j>=1} 1 + y*x^j). - Andrew Howroyd, Apr 16 2021

A339416 Number of compositions (ordered partitions) of n into an even number of triangular numbers.

Original entry on oeis.org

1, 0, 1, 0, 3, 0, 6, 2, 13, 6, 28, 20, 61, 56, 135, 148, 308, 380, 707, 950, 1654, 2340, 3897, 5714, 9252, 13858, 22055, 33492, 52735, 80744, 126313, 194376, 302906, 467506, 726862, 1123830, 1744947, 2700682, 4190016, 6488824, 10062649, 15588714, 24168232, 37447884

Offset: 0

Ilya Gutkovskiy, Dec 03 2020

nonn

			a(9) = 6 because we have [6, 3], [3, 6], [6, 1, 1, 1], [1, 6, 1, 1], [1, 1, 6, 1] and [1, 1, 1, 6].

Cf. A000217, A023361, A034008, A106507, A339373, A339417.

b:= proc(n, t) option remember; local r, f, g;
      if n=0 then t else r, f, g:=$0..2; while f<=n
      do r, f, g:= r+b(n-f, 1-t), f+g, g+1 od; r fi
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..50);  # Alois P. Heinz, Dec 03 2020

nmax = 43; CoefficientList[Series[(1/2) (1/(1 - Sum[x^(k (k + 1)/2), {k, 1, nmax}]) + 1/Sum[x^(k (k + 1)/2), {k, 0, nmax}]), {x, 0, nmax}], x]

G.f.: (1/2) * (1 / (1 - Sum_{k>=1} x^(k*(k + 1)/2)) + 1 / Sum_{k>=0} x^(k*(k + 1)/2)).
a(n) = (A023361(n) + A106507(n)) / 2.
a(n) = Sum_{k=0..n} A023361(k) * A106507(n-k).

A339418 Number of compositions (ordered partitions) of n into an even number of squares.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 1, 4, 2, 6, 9, 8, 20, 16, 35, 44, 55, 102, 105, 196, 242, 344, 540, 652, 1084, 1380, 2037, 2964, 3912, 6042, 7976, 11776, 16634, 22968, 33963, 46156, 67457, 94510, 133180, 192316, 266514, 385338, 540138, 767008, 1094576, 1534704, 2200821, 3094248

Offset: 0

Ilya Gutkovskiy, Dec 03 2020

nonn

			a(9) = 6 because we have [4, 1, 1, 1, 1, 1], [1, 4, 1, 1, 1, 1], [1, 1, 4, 1, 1, 1], [1, 1, 1, 4, 1, 1], [1, 1, 1, 1, 4, 1] and [1, 1, 1, 1, 1, 4].

Cf. A000290, A006456, A034008, A317665, A339364, A339416, A339419.

b:= proc(n, t) option remember; local r, f, g;
      if n=0 then t else r, f, g:=$0..2; while f<=n
      do r, f, g:= r+b(n-f, 1-t), f+2*g-1, g+1 od; r fi
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..50);  # Alois P. Heinz, Dec 03 2020

nmax = 47; CoefficientList[Series[4/(3 + 2 EllipticTheta[3, 0, x] - EllipticTheta[3, 0, x]^2), {x, 0, nmax}], x]

G.f.: 4 / (3 + 2 * theta_3(x) - theta_3(x)^2), where theta_3() is the Jacobi theta function.
a(n) = (A006456(n) + A317665(n)) / 2.
a(n) = Sum_{k=0..n} A006456(k) * A317665(n-k).

A201863 Let CZ(0,x)=1, CZ(1,x)=0 , CZ(2,x)=x^2-1 and CZ(n,x)=2xCZ(n-1,x) - CZ(n-2,x) for n > 2. This sequence is the triangle of polynomial coefficients in order of decreasing exponents.

Original entry on oeis.org

1, 0, 0, 1, 0, -1, 2, 0, -2, 0, 4, 0, -5, 0, 1, 8, 0, -12, 0, 4, 0, 16, 0, -28, 0, 13, 0, -1, 32, 0, -64, 0, 38, 0, -6, 0, 64, 0, -144, 0, 104, 0, -25, 0, 1, 128, 0, -320, 0, 272, 0, -88, 0, 8, 0, 256, 0, -704, 0, 688, 0, -280, 0, 41, 0, -1

Offset: 0

Paul Curtz, Dec 06 2011

From (A039991 without 0's=) A028297 we wrote in A201509
1,  1,
2,  2,
4,  5, 1,
8, 12, 4.
Hence a(n) first coefficients:
1,
0, 0
1, 0,- 1,   x^2-1,
2, 0, -2, 0,
4, 0, -5, 0, 1
8, 0,-12, 0, 4, 0.
The first 1 is a choice.
Row sums=0.
Absolute value row sums: 1 before A163271.
First vertical:A034008=1 before A131577. Third:-A045623.
Mirror image of triangle in A076626. - Philippe Deléham, Dec 07 2011

Cf. A039991, A201509.

A339408 Number of compositions (ordered partitions) of n into an even number of primes.

Original entry on oeis.org

1, 0, 0, 0, 1, 2, 1, 2, 3, 6, 9, 8, 16, 24, 40, 52, 72, 112, 172, 256, 364, 528, 804, 1188, 1757, 2548, 3782, 5614, 8308, 12214, 17979, 26586, 39352, 58044, 85608, 126248, 186630, 275556, 406737, 600066, 885952, 1308250, 1931473, 2850692, 4207952, 6212110, 9171800, 13538980

Offset: 0

Ilya Gutkovskiy, Dec 03 2020

nonn

			a(8) = 3 because we have [5, 3], [3, 5] and [2, 2, 2, 2].

Index entries for sequences related to compositions

Cf. A000040, A023360, A034008, A184198, A339380, A339409.

b:= proc(n, t) option remember; `if`(n=0, t, add(
      b(n-ithprime(j), 1-t), j=1..numtheory[pi](n)))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..55);  # Alois P. Heinz, Dec 03 2020

nmax = 47; CoefficientList[Series[(1/2) (1/(1 - Sum[x^Prime[k], {k, 1, nmax}]) + 1/(1 + Sum[x^Prime[k], {k, 1, nmax}])), {x, 0, nmax}], x]

G.f.: (1/2) * (1 / (1 - Sum_{k>=1} x^prime(k)) + 1 / (1 + Sum_{k>=1} x^prime(k))).

A339420 Number of compositions (ordered partitions) of n into an even number of cubes.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 1, 4, 1, 6, 1, 8, 2, 10, 7, 12, 16, 14, 29, 16, 46, 22, 67, 40, 94, 78, 125, 144, 161, 246, 214, 394, 312, 602, 499, 878, 835, 1236, 1396, 1722, 2286, 2446, 3637, 3614, 5598, 5560, 8358, 8782, 12226, 14014, 17776, 22278, 26056, 34924

Offset: 0

Ilya Gutkovskiy, Dec 03 2020

nonn

			a(11) = 4 because we have [8, 1, 1, 1], [1, 8, 1, 1], [1, 1, 8, 1] and [1, 1, 1, 8].

Cf. A000578, A023358, A034008, A323633, A339368, A339418, A339421.

b:= proc(n, t) option remember; local r, f, g;
      if n=0 then t else r, f, g:=$0..2; while f<=n
      do r, f, g:= r+b(n-f, 1-t), f+3*g*(g-1)+1, g+1 od; r fi
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..60);  # Alois P. Heinz, Dec 03 2020

nmax = 57; CoefficientList[Series[(1/2) (1/(1 - Sum[x^(k^3), {k, 1, Floor[nmax^(1/3)] + 1}]) + 1/Sum[x^(k^3), {k, 0, Floor[nmax^(1/3)] + 1}]), {x, 0, nmax}], x]

G.f.: (1/2) * (1 / (1 - Sum_{k>=1} x^(k^3)) + 1 / Sum_{k>=0} x^(k^3)).
a(n) = (A023358(n) + A323633(n)) / 2.
a(n) = Sum_{k=0..n} A023358(k) * A323633(n-k).

A368579 Triangle read by rows. T(n, k) is the number of compositions of n where the first part k is the largest part and the last part is not 1.

Original entry on oeis.org

1, -1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 2, 2, 1, 0, 1, 0, 0, 3, 3, 2, 1, 0, 1, 0, 0, 5, 6, 4, 2, 1, 0, 1, 0, 0, 8, 11, 7, 4, 2, 1, 0, 1, 0, 0, 13, 20, 14, 8, 4, 2, 1, 0, 1, 0, 0, 21, 37, 27, 15, 8, 4, 2, 1, 0, 1

Offset: 0

Peter Luschny, Jan 05 2024

			Triangle T(n, k) starts:
  [0] [ 1]
  [1] [-1, 1]
  [2] [ 0, 0, 1]
  [3] [ 0, 0, 0,  1]
  [4] [ 0, 0, 1,  0, 1]
  [5] [ 0, 0, 1,  1, 0, 1]
  [6] [ 0, 0, 2,  2, 1, 0, 1]
  [7] [ 0, 0, 3,  3, 2, 1, 0, 1]
  [8] [ 0, 0, 5,  6, 4, 2, 1, 0, 1]
  [9] [ 0, 0, 8, 11, 7, 4, 2, 1, 0, 1]
For instance, row 6 lists the compositions below:
  0  .
  1  .
  2 [2, 2, 2], [2, 1, 1, 2];
  3 [3, 3], [3, 1, 2];
  4 [4, 2];
  5  .
  6 [6].

Cf. A368279 (row sums), A092921 (generalized Fibonacci), A000045 (Fibonacci column k=2), A034008 (T(2n, n)).

from functools import cache
@cache
def F(k, n):
    return sum(F(k, n-j) for j in range(1, min(k, n))) if n > 1 else n
def Trow(n):
    return list(F(k+1, n+1-k) - F(k+1, n-k) for k in range(n+1))
print(flatten([Trow(n) for n in range(12)]))

T(n, k) = F(k+1, n+1-k) - F(k+1, n-k) where F(k, n) = Sum_{j=1..min(n, k)} F(k, n-j) if n > 1 and otherwise n. F(n, k) refers to the generalized Fibonacci numbers A092921.

A240750 Table where row n contains all compositions of n into an even number of parts.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 3, 1, 2, 2, 1, 3, 1, 1, 1, 1, 4, 1, 3, 2, 2, 3, 2, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 5, 1, 4, 2, 3, 3, 3, 1, 1, 1, 2, 4, 2, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 5, 1, 3, 1, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1

Offset: 2

Franklin T. Adams-Watters, Apr 12 2014

Can also be regarded as a table where row n is the n-th composition into an even number of parts, sorted by sum of composition and then reverse lexicographically.

			The table starts:
{}
(none)
11
21,12
31,22,13,1111
41,32,23,2111,14,1211,1121,1112
51,42,33,3111,24,2211,2121,2112,15,1311,1221,1212,1131,1122,1113,111111

Cf. A066099, A240837, A001969, A034008 (compositions in rows), A087447 (parts in rows for n>2).

evil(n) = local(r=0,m=n);while(m>0,if(m%2==1,r=1-r);m\=2);n*2+r
A066099row(n) = {local(v=vector(n), j=0, k=0);
   while(n>0, k++; if(n%2==1, v[j++]=k; k=0); n\=2);
   vector(j, i, v[j-i+1])}
arow(n)=A066099row(evil(n))

cp's OEIS Frontend

A122391 Dimension of 2-variable non-commutative harmonics (Hausdorff derivative). The dimension of the space of non-commutative polynomials in 2 variables which are killed by all symmetric differential operators (where for a monomial w, d_{xi} ( w ) = sum over all subwords of w deleting xi once).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A347704 Number of even-length integer partitions of n with integer alternating product.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A342343 Number of strict compositions of n with alternating parts strictly decreasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A339416 Number of compositions (ordered partitions) of n into an even number of triangular numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A339418 Number of compositions (ordered partitions) of n into an even number of squares.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A201863 Let CZ(0,x)=1, CZ(1,x)=0 , CZ(2,x)=x^2-1 and CZ(n,x)=2*x*CZ(n-1,x) - CZ(n-2,x) for n > 2. This sequence is the triangle of polynomial coefficients in order of decreasing exponents.

Views

Author

Keywords

Comments

Crossrefs

A339408 Number of compositions (ordered partitions) of n into an even number of primes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A339420 Number of compositions (ordered partitions) of n into an even number of cubes.

Views

Author

Keywords

Examples

A201863 Let CZ(0,x)=1, CZ(1,x)=0 , CZ(2,x)=x^2-1 and CZ(n,x)=2xCZ(n-1,x) - CZ(n-2,x) for n > 2. This sequence is the triangle of polynomial coefficients in order of decreasing exponents.