A106351 -id:A106351 - cp's OEIS frontend

A003242 Number of compositions of n such that no two adjacent parts are equal (these are sometimes called Carlitz compositions).

1, 1, 1, 3, 4, 7, 14, 23, 39, 71, 124, 214, 378, 661, 1152, 2024, 3542, 6189, 10843, 18978, 33202, 58130, 101742, 178045, 311648, 545470, 954658, 1670919, 2924536, 5118559, 8958772, 15680073, 27443763, 48033284, 84069952, 147142465, 257534928, 450748483, 788918212

Offset: 0

E. Rodney Canfield

			From _Joerg Arndt_, Oct 27 2012:  (Start)
The 23 such compositions of n=7 are
[ 1]  1 2 1 2 1
[ 2]  1 2 1 3
[ 3]  1 2 3 1
[ 4]  1 2 4
[ 5]  1 3 1 2
[ 6]  1 3 2 1
[ 7]  1 4 2
[ 8]  1 5 1
[ 9]  1 6
[10]  2 1 3 1
[11]  2 1 4
[12]  2 3 2
[13]  2 4 1
[14]  2 5
[15]  3 1 2 1
[16]  3 1 3
[17]  3 4
[18]  4 1 2
[19]  4 2 1
[20]  4 3
[21]  5 2
[22]  6 1
[23]  7
(End)

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 191.

Alois P. Heinz, Table of n, a(n) for n = 0..4100 (first 501 terms from Christian G. Bower)
L. Carlitz, Restricted Compositions, Fibonacci Quarterly, 14 (1976) 254-264.
Sylvie Corteel, Paweł Hitczenko, Generalizations of Carlitz Compositions, Journal of Integer Sequences, Vol. 10 (2007), Article 07.8.8
Steven R. Finch, Errata and Addenda to Mathematical Constants, arXiv:2001.00578 [math.HO], 2020-2022, p. 42 and 117.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 201
F. Harary & R. W. Robinson, The number of achiral trees, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)
A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.
E. Munarini, M. Poneti, S. Rinaldi, Matrix compositions, JIS 12 (2009) 09.4.8, Chapter 8.

Cf. A106351, A114900, A114902.
Cf. A096568, A011782, A106356. - Franklin T. Adams-Watters, May 27 2010
Row sums of A232396, A241701.
Cf. A241902.
Column k=1 of A261960.
Cf. A048272.
Compositions with adjacent parts coprime are A167606.
The complement is counted by A261983.
Cf. A000740, A005251, A032020, A114901, A178470, A261041, A274174, A329738, A329863.

a003242 n = a003242_list !! n
a003242_list = 1 : f [1] where
   f xs = y : f (y : xs) where
          y = sum $ zipWith (*) xs a048272_list
-- Reinhard Zumkeller, Nov 04 2015

b:= proc(n, i) option remember; `if`(n=0, 1,
      add(`if`(j=i, 0, b(n-j, `if`(j<=n-j, j, 0))), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Mar 27 2014

A048272[n_] := Total[If[OddQ[#], 1, -1]& /@ Divisors[n]]; a[n_] := a[n] = Sum[A048272[k]*a[n-k], {k, 1, n}]; a[0] = 1; Table[a[n], {n, 0, 38}](* Jean-François Alcover, Nov 25 2011, after Vladeta Jovovic *)
nmax = 50; CoefficientList[Series[1/(1 - Sum[x^k/(1 + x^k), {k, 1, nmax}]), {x, 0, nmax}], x] (* Vaclav Kotesovec, Jul 07 2020 *)
Table[Count[Flatten[Permutations/@IntegerPartitions[n],1],?(FreeQ[Differences[#],0]&)],{n,0,20}] (* The program generates the first 21 terms of the sequence. *) (* _Harvey P. Dale, Nov 23 2024 *)

N = 66;  x = 'x + O('x^N);  p=2;
gf = 1/(1-sum(k=1,N, x^k/(1-x^k)-p*x^(k*p)/(1-x^(k*p))));
Vec(gf)  /* Joerg Arndt, Apr 28 2013 */

a(n) = Sum_{k=1..n} A048272(k)*a(n-k), n>1, a(0)=1. - Vladeta Jovovic, Feb 05 2002
G.f.: 1/(1 - Sum_{k>0} x^k/(1+x^k)).
a(n) ~ c r^n where c is approximately 0.456387 and r is approximately 1.750243. (Formula from Knopfmacher and Prodinger reference.) - Franklin T. Adams-Watters, May 27 2010. With better precision: r = 1.7502412917183090312497386246398158787782058181381590561316586... (see A241902), c = 0.4563634740588133495321001859298593318027266156100046548066205... - Vaclav Kotesovec, Apr 30 2014
G.f. is the special case p=2 of 1/(1 - Sum_{k>0} (z^k/(1-z^k) - p*z^(k*p)/(1-z^(k*p)))), see A129922. - Joerg Arndt, Apr 28 2013
G.f.: 1/(1 - x * (d/dx) log(Product_{k>=1} (1 + x^k)^(1/k))). - Ilya Gutkovskiy, Oct 18 2018
Moebius transform of A329738. - Gus Wiseman, Nov 27 2019
For n>=2, a(n) = A128695(n) - A091616(n). - Vaclav Kotesovec, Jul 07 2020

More terms from David W. Wilson

A344604 Number of alternating compositions of n, including twins (x,x).

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 13, 19, 30, 48, 76, 118, 187, 293, 461, 725, 1140, 1789, 2815, 4422, 6950, 10924, 17169, 26979, 42405, 66644, 104738, 164610, 258708, 406588, 639010, 1004287, 1578364, 2480606, 3898600, 6127152, 9629624, 15134213, 23785389, 37381849, 58750469

Offset: 0

Gus Wiseman, May 27 2021

nonn

We define a composition to be alternating including twins (x,x) if there are no adjacent triples (..., x, y, z, ...) where x <= y <= z or x >= y >= z. Except in the case of twins (x,x), all such compositions are anti-runs (A003242). These compositions avoid the weak consecutive patterns (1,2,3) and (3,2,1), the strict version being A344614.

The version without twins (x,x) is A025047 (alternating compositions).

			The a(1) = 1 through a(7) = 19 compositions:
  (1)  (2)   (3)   (4)    (5)    (6)     (7)
       (11)  (12)  (13)   (14)   (15)    (16)
             (21)  (22)   (23)   (24)    (25)
                   (31)   (32)   (33)    (34)
                   (121)  (41)   (42)    (43)
                          (131)  (51)    (52)
                          (212)  (132)   (61)
                                 (141)   (142)
                                 (213)   (151)
                                 (231)   (214)
                                 (312)   (232)
                                 (1212)  (241)
                                 (2121)  (313)
                                         (412)
                                         (1213)
                                         (1312)
                                         (2131)
                                         (3121)
                                         (12121)

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

A001250 counts alternating permutations.
A005649 counts anti-run patterns.
A025047 counts alternating or wiggly compositions, also A025048, A025049.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A325534 counts separable partitions.
A325535 counts inseparable partitions.
A344605 counts alternating patterns including twins.
A344606 counts alternating permutations of prime factors including twins.
Counting compositions by patterns:
- A011782 no conditions.
- A003242 avoiding (1,1) adjacent.
- A102726 avoiding (1,2,3).
- A106351 avoiding (1,1) adjacent by sum and length.
- A128695 avoiding (1,1,1) adjacent.
- A128761 avoiding (1,2,3) adjacent.
- A232432 avoiding (1,1,1).
- A335456 all patterns.
- A335457 all patterns adjacent.
- A335514 matching (1,2,3).
- A344614 avoiding (1,2,3) and (3,2,1) adjacent.
- A344615 weakly avoiding (1,2,3) adjacent.
Cf. A000041, A006330, A008965, A238279, A239830, A333213, A238279/A333755, A344612, A344616, A344617, A344618.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,y_,z_,_}/;x<=y<=z||x>=y>=z]&]],{n,0,15}]

a(n > 0) = A025047(n) + 1 if n is even, otherwise A025047(n). - Gus Wiseman, Nov 03 2021

a(21)-a(40) from Alois P. Heinz, Nov 04 2021

A344614 Number of compositions of n with no adjacent triples (..., x, y, z, ...) where x < y < z or x > y > z.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 30, 58, 110, 209, 397, 753, 1429, 2711, 5143, 9757, 18511, 35117, 66621, 126389, 239781, 454897, 863010, 1637260, 3106138, 5892821, 11179603, 21209446, 40237641, 76337091, 144823431, 274752731, 521249018, 988891100, 1876081530, 3559220898, 6752400377

Offset: 0

Gus Wiseman, May 27 2021

nonn

These compositions avoid the strict consecutive patterns (1,2,3) and (3,2,1), the weak version being A344604.

			The a(6) = 30 compositions are:
  (6)  (15)  (114)  (1113)  (11112)  (111111)
       (24)  (132)  (1122)  (11121)
       (33)  (141)  (1131)  (11211)
       (42)  (213)  (1212)  (12111)
       (51)  (222)  (1221)  (21111)
             (231)  (1311)
             (312)  (2112)
             (411)  (2121)
                    (2211)
                    (3111)
Missing are: (123), (321).

A001250 counts alternating permutations.
A005649 counts anti-run patterns.
A025047 counts wiggly compositions (ascend: A025048, descend: A025049).
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A325534 counts separable partitions.
A325535 counts inseparable partitions.
A344604 counts wiggly compositions with twins.
A344605 counts wiggly patterns with twins.
A344606 counts wiggly permutations of prime factors with twins.
Counting compositions by patterns:
- A003242 avoiding (1,1) adjacent.
- A011782 no conditions.
- A106351 avoiding (1,1) adjacent by sum and length.
- A128695 avoiding (1,1,1) adjacent.
- A128761 avoiding (1,2,3).
- A232432 avoiding (1,1,1).
- A335456 all patterns.
- A335457 all patterns adjacent.
- A335514 matching (1,2,3).
- A344604 weakly avoiding (1,2,3) and (3,2,1) adjacent.
- A344614 avoiding (1,2,3) and (3,2,1) adjacent.
- A344615 weakly avoiding (1,2,3) adjacent.
Cf. A000041, A006330, A008965, A049774, A056986, A238279/A333755, A333213, A335515, A344612, A344652.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,y_,z_,_}/;xy>z]&]],{n,0,15}]

More terms from Bert Dobbelaere, Jun 12 2021

A335126 A multiset whose multiplicities are the prime indices of n is inseparable.

Original entry on oeis.org

3, 5, 7, 10, 11, 13, 14, 17, 19, 21, 22, 23, 26, 28, 29, 31, 33, 34, 37, 38, 39, 41, 43, 44, 46, 47, 51, 52, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 68, 69, 71, 73, 74, 76, 78, 79, 82, 83, 85, 86, 87, 88, 89, 91, 92, 93, 94, 95, 97, 101, 102, 103, 104, 106

Offset: 1

Gus Wiseman, Jul 01 2020

nonn

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.

A multiset whose multiplicities are the prime indices of n (such as row n of A305936) is not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

			The sequence of terms together with the corresponding multisets begins:
   3: {1,1}
   5: {1,1,1}
   7: {1,1,1,1}
  10: {1,1,1,2}
  11: {1,1,1,1,1}
  13: {1,1,1,1,1,1}
  14: {1,1,1,1,2}
  17: {1,1,1,1,1,1,1}
  19: {1,1,1,1,1,1,1,1}
  21: {1,1,1,1,2,2}
  22: {1,1,1,1,1,2}
  23: {1,1,1,1,1,1,1,1,1}
  26: {1,1,1,1,1,1,2}
  28: {1,1,1,1,2,3}
  29: {1,1,1,1,1,1,1,1,1,1}

The complement is A335127.
Anti-run compositions are A003242.
Anti-runs are ranked by A333489.
Separable partitions are A325534.
Inseparable partitions are A325535.
Separable factorizations are A335434.
Inseparable factorizations are A333487.
Separable partitions are ranked by A335433.
Inseparable partitions are ranked by A335448.
Anti-run permutations of prime indices are A335452.
Patterns contiguously matched by compositions are A335457.
Cf. A025487, A056239, A106351, A112798, A114938, A181819, A181821, A278990, A292884, A335407, A335489, A335516, A335838.

nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[100],Select[Permutations[nrmptn[#]],!MatchQ[#,{_,x_,x_,_}]&]=={}&]

A344615 Number of compositions of n with no adjacent triples (..., x, y, z, ...) where x <= y <= z.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 17, 29, 50, 84, 143, 241, 408, 688, 1162, 1959, 3305, 5571, 9393, 15832, 26688, 44980, 75812, 127769, 215338, 362911, 611620, 1030758, 1737131, 2927556, 4933760, 8314754, 14012668, 23615198, 39798098, 67070686, 113032453, 190490542, 321028554

Offset: 0

Gus Wiseman, May 27 2021

nonn

These compositions avoid the weak consecutive pattern (1,2,3), the strict version being A128761.

			The a(1) = 1 through a(6) = 17 compositions:
  (1)  (2)    (3)    (4)      (5)        (6)
       (1,1)  (1,2)  (1,3)    (1,4)      (1,5)
              (2,1)  (2,2)    (2,3)      (2,4)
                     (3,1)    (3,2)      (3,3)
                     (1,2,1)  (4,1)      (4,2)
                     (2,1,1)  (1,3,1)    (5,1)
                              (2,1,2)    (1,3,2)
                              (2,2,1)    (1,4,1)
                              (3,1,1)    (2,1,3)
                              (1,2,1,1)  (2,3,1)
                                         (3,1,2)
                                         (3,2,1)
                                         (4,1,1)
                                         (1,2,1,2)
                                         (1,3,1,1)
                                         (2,1,2,1)
                                         (2,2,1,1)

The case of permutations is A049774.
The strict non-adjacent version is A102726.
The case of permutations of prime indices is A344652.
A001250 counts alternating permutations.
A005649 counts anti-run patterns.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A344604 counts wiggly compositions with twins.
A344605 counts wiggly patterns with twins.
A344606 counts wiggly permutations of prime factors with twins.
Counting compositions by patterns:
- A003242 avoiding (1,1) adjacent.
- A011782 no conditions.
- A106351 avoiding (1,1) adjacent by sum and length.
- A128695 avoiding (1,1,1) adjacent.
- A128761 avoiding (1,2,3).
- A232432 avoiding (1,1,1).
- A335456 all patterns.
- A335457 all patterns adjacent.
- A335514 matching (1,2,3).
- A344604 weakly avoiding (1,2,3) and (3,2,1) adjacent.
- A344614 avoiding (1,2,3) and (3,2,1) adjacent.
- A344615 weakly avoiding (1,2,3) adjacent.
Cf. A000041, A006330, A008965, A027187, A238279/A333755, A333213, A335464, A335515, A344612, A344619.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,y_,z_,_}/;x<=y<=z]&]],{n,0,15}]

More terms from Bert Dobbelaere, Jun 12 2021

A335434 Number of separable factorizations of n into factors > 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 4, 2, 2, 1, 6, 1, 2, 2, 4, 1, 5, 1, 5, 2, 2, 2, 8, 1, 2, 2, 6, 1, 5, 1, 4, 4, 2, 1, 10, 1, 4, 2, 4, 1, 6, 2, 6, 2, 2, 1, 11, 1, 2, 4, 6, 2, 5, 1, 4, 2, 5, 1, 15, 1, 2, 4, 4, 2, 5, 1, 10, 3, 2, 1, 11, 2

Offset: 1

Gus Wiseman, Jul 03 2020

nonn

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.

			The a(n) factorizations for n = 2, 6, 16, 12, 30, 24, 36, 48, 60:
  2  6    16     12     30     24     36       48       60
     2*3  2*8    2*6    5*6    3*8    4*9      6*8      2*30
          2*2*4  3*4    2*15   4*6    2*18     2*24     3*20
                 2*2*3  3*10   2*12   3*12     3*16     4*15
                        2*3*5  2*2*6  2*2*9    4*12     5*12
                               2*3*4  2*3*6    2*3*8    6*10
                                      3*3*4    2*4*6    2*5*6
                                      2*2*3*3  3*4*4    3*4*5
                                               2*2*12   2*2*15
                                               2*2*3*4  2*3*10
                                                        2*2*3*5

The version for partitions is A325534.
The inseparable version is A333487.
The version for multisets with prescribed multiplicities is A335127.
Factorizations are A001055.
Anti-run compositions are A003242.
Inseparable partitions are A325535.
Anti-runs are ranked by A333489.
Separable partitions are ranked by A335433.
Inseparable partitions are ranked by A335448.
Anti-run permutations of prime indices are A335452.
Cf. A106351, A292884, A295370, A333628, A333755, A335463, A335125, A335126, A335407, A335457, A335474, A335516, A335838.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],Select[Permutations[#],!MatchQ[#,{_,x_,x_,_}]&]!={}&]],{n,100}]

A333487(n) + a(n) = A001055(n).

A335127 A multiset whose multiplicities are the prime indices of n is separable.

Original entry on oeis.org

1, 2, 4, 6, 8, 9, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 35, 36, 40, 42, 45, 48, 49, 50, 54, 56, 60, 63, 64, 70, 72, 75, 77, 80, 81, 84, 90, 96, 98, 99, 100, 105, 108, 110, 112, 120, 121, 125, 126, 128, 132, 135, 140, 143, 144, 147, 150, 154, 160, 162, 165

Offset: 1

Gus Wiseman, Jul 02 2020

nonn

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.

A multiset whose multiplicities are the prime indices of n (such as row n of A305936) is not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

			The sequence together with the corresponding multisets begins:
   1: {}
   2: {1}
   4: {1,2}
   6: {1,1,2}
   8: {1,2,3}
   9: {1,1,2,2}
  12: {1,1,2,3}
  15: {1,1,1,2,2}
  16: {1,2,3,4}
  18: {1,1,2,2,3}
  20: {1,1,1,2,3}
  24: {1,1,2,3,4}
  25: {1,1,1,2,2,2}
  27: {1,1,2,2,3,3}
  30: {1,1,1,2,2,3}

The complement is A335126.
Anti-run compositions are A003242.
Anti-runs are ranked by A333489.
Separable partitions are A325534.
Inseparable partitions are A325535.
Separable factorizations are A335434.
Inseparable factorizations are A333487.
Separable partitions are ranked by A335433.
Inseparable partitions are ranked by A335448.
Anti-run permutations of prime indices are A335452.
Patterns contiguously matched by compositions are A335457.
Cf. A056239, A106351, A112798, A114938, A292884, A335489, A335516, A335838.

nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[100],Select[Permutations[nrmptn[#]],!MatchQ[#,{_,x_,x_,_}]&]!={}&]

A336103 Number of separable multisets of size n covering an initial interval of positive integers.

Original entry on oeis.org

1, 1, 1, 3, 5, 13, 24, 56, 108, 236, 464, 976, 1936, 3984, 7936, 16128, 32192, 64960, 129792, 260864, 521472, 1045760, 2091008, 4188160, 8375296, 16763904, 33525760, 67080192, 134156288, 268374016, 536739840, 1073610752, 2147205120, 4294688768, 8589344768, 17179279360, 34358493184

Offset: 0

Gus Wiseman, Jul 09 2020

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.
Alternatively, a multiset is separable if its greatest multiplicity is greater than the sum of its remaining multiplicities plus one. Hence a(n) is the number of compositions of n whose greatest part is at most one more than the sum of its other parts. For example, the a(1) = 1 through a(5) = 13 compositions are:
  (1)  (11)  (12)   (22)    (23)
             (21)   (112)   (32)
             (111)  (121)   (113)
                    (211)   (122)
                    (1111)  (131)
                            (212)
                            (221)
                            (311)
                            (1112)
                            (1121)
                            (1211)
                            (2111)
                            (11111)

			The a(1) = 1 through a(5) = 13 separable multisets:
  {1}  {1,2}  {1,1,2}  {1,1,2,2}  {1,1,1,2,2}
              {1,2,2}  {1,1,2,3}  {1,1,1,2,3}
              {1,2,3}  {1,2,2,3}  {1,1,2,2,2}
                       {1,2,3,3}  {1,1,2,2,3}
                       {1,2,3,4}  {1,1,2,3,3}
                                  {1,1,2,3,4}
                                  {1,2,2,2,3}
                                  {1,2,2,3,3}
                                  {1,2,2,3,4}
                                  {1,2,3,3,3}
                                  {1,2,3,3,4}
                                  {1,2,3,4,4}
                                  {1,2,3,4,5}

Michael De Vlieger, Table of n, a(n) for n = 0..3322
Index entries for linear recurrences with constant coefficients, signature (2,4,-8,-4,8).

The inseparable version is A336102.
The strong (weakly decreasing multiplicities) case is A336106.
Sequences covering an initial interval are A000670.
Anti-run compositions are A003242.
Anti-run patterns are A005649.
Separable partitions are A325534.
Inseparable partitions are A325535.
Inseparable factorizations are A333487.
Anti-run compositions are ranked by A333489.
Heinz numbers of inseparable partitions are A335448.
Cf. A001792, A019472, A025065, A049610, A052841, A106351, A269134, A292884, A335126, A335433, A335452.

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
sepQ[m_]:=Select[Permutations[m],!MatchQ[#,{_,x_,x_,_}]&]!={};
Table[Length[Select[allnorm[n],sepQ]],{n,0,5}]
(* or *)
Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],With[{mx=Max@@#},mx<=1+Total[DeleteCases[#,mx,{1},1]]]&]],{n,0,15}] (* or *)
CoefficientList[Series[(x - 1) (2 x^5 + 7 x^4 - 5 x^2 + 1)/((2 x - 1) (2 x^2 - 1)^2), {x, 0, 36}], x] (* Michael De Vlieger, Apr 07 2021 *)

a(n) = 2^(n-1) - (floor(n/2)+1) * 2^(floor(n/2)-2) for n >= 2. - David A. Corneth, Jul 09 2020
From Chai Wah Wu, Apr 07 2021: (Start)
a(n) = 2*a(n-1) + 4*a(n-2) - 8*a(n-3) - 4*a(n-4) + 8*a(n-5) for n > 6.
G.f.: (x - 1)*(2*x^5 + 7*x^4 - 5*x^2 + 1)/((2*x - 1)*(2*x^2 - 1)^2). (End)

a(26)-a(36) from David A. Corneth, Jul 09 2020

A335125 Number of anti-run permutations of a multiset whose multiplicities are the prime indices of n.

Original entry on oeis.org

1, 1, 0, 2, 0, 1, 0, 6, 2, 0, 0, 6, 0, 0, 1, 24, 0, 12, 0, 2, 0, 0, 0, 36, 2, 0, 30, 0, 0, 10, 0, 120, 0, 0, 1, 84, 0, 0, 0, 24, 0, 3, 0, 0, 38, 0, 0, 240, 2, 18, 0, 0, 0, 246, 0, 6, 0, 0, 0, 96, 0, 0, 24, 720, 0, 0, 0, 0, 0, 14, 0, 660, 0, 0, 74, 0, 1, 0, 0

Offset: 1

Gus Wiseman, Jul 01 2020

nonn

A multiset whose multiplicities are the prime indices of n (such as row n of A305936) is not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

An anti-run is a sequence with no adjacent equal parts.

			The a(n) permutations for n = 2, 4, 42, 8, 30, 18:
  (1)  (12)  (1212131)  (123)  (121213)  (12123)
       (21)  (1213121)  (132)  (121231)  (12132)
             (1312121)  (213)  (121312)  (12312)
                        (231)  (121321)  (12321)
                        (312)  (123121)  (13212)
                        (321)  (131212)  (21213)
                               (132121)  (21231)
                               (212131)  (21312)
                               (213121)  (21321)
                               (312121)  (23121)
                                         (31212)
                                         (32121)

Positions of zeros are A335126.
Positions of nonzeros are A335127.
The version for the prime indices themselves is A335452.
Anti-run compositions are A003242.
Anti-runs are ranked by A333489.
Separable partitions are ranked by A335433.
Separable factorizations are A335434.
Inseparable partitions are ranked by A335448.
Patterns contiguously matched by compositions are A335457.
Strict permutations of prime indices are A335489.
Cf. A019472, A056239, A106351, A112798, A114938, A278990, A292884, A325535, A335407, A335463, A335516, A335838.

nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Table[Length[Select[Permutations[nrmptn[n]],!MatchQ[#,{_,x_,x_,_}]&]],{n,100}]

A336102 Number of inseparable multisets of size n covering an initial interval of positive integers.

Original entry on oeis.org

0, 0, 1, 1, 3, 3, 8, 8, 20, 20, 48, 48, 112, 112, 256, 256, 576, 576, 1280, 1280, 2816, 2816, 6144, 6144, 13312, 13312, 28672, 28672, 61440, 61440, 131072, 131072, 278528, 278528, 589824, 589824, 1245184, 1245184, 2621440, 2621440, 5505024, 5505024, 11534336

Offset: 0

Gus Wiseman, Jul 08 2020

nonn

A multiset is separable if it has a permutation that is an anti-run, meaning there are no adjacent equal parts.
Alternatively, a multiset is separable if its greatest multiplicity is greater than the sum of its remaining multiplicities plus one.
Also the number of compositions of n whose greatest part is greater than the sum of its remaining parts plus one. For example, the a(2) = 1 through a(7) = 8 compositions are:
  (2)  (3)  (4)    (5)    (6)      (7)
            (1,3)  (1,4)  (1,5)    (1,6)
            (3,1)  (4,1)  (2,4)    (2,5)
                          (4,2)    (5,2)
                          (5,1)    (6,1)
                          (1,1,4)  (1,1,5)
                          (1,4,1)  (1,5,1)
                          (4,1,1)  (5,1,1)

			The a(2) = 1 through a(7) = 8 multisets:
  {11}  {111}  {1111}  {11111}  {111111}  {1111111}
               {1112}  {11112}  {111112}  {1111112}
               {1222}  {12222}  {111122}  {1111122}
                                {111123}  {1111123}
                                {112222}  {1122222}
                                {122222}  {1222222}
                                {122223}  {1222223}
                                {123333}  {1233333}

Michael De Vlieger, Table of n, a(n) for n = 0..6625
Index entries for linear recurrences with constant coefficients, signature (0,4,0,-4).

The strong (weakly decreasing multiplicities) case is A025065.
The bisection is A049610.
The separable version is A336103.
Sequences covering an initial interval are A000670.
Anti-run compositions are A003242.
Anti-run patterns are A005649.
Separable partitions are A325534.
Inseparable partitions are A325535.
Inseparable factorizations are A333487.
Anti-run compositions are ranked by A333489.
Heinz numbers of inseparable partitions are A335448.
Cf. A001792, A019472, A052841, A106351, A124767, A269134, A292884, A335433, A335126, A335452, A335548.

Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],With[{mx=Max@@#},mx>1+Total[DeleteCases[#,mx,{1},1]]]&]],{n,0,15}]
(* Second program: *)
CoefficientList[Series[x^2*(1 - x) (x + 1)^2/(2 x^2 - 1)^2, {x, 0, 43}], x] (* Michael De Vlieger, Apr 07 2021 *)

a(2*n) = a(2*n + 1) = A049610(n + 1).
a(n) = 2^(n-1) - A336103(n).
A001792 repeated for n > 1. David A. Corneth, Jul 09 2020
From Chai Wah Wu, Apr 07 2021: (Start)
a(n) = 4*a(n-2) - 4*a(n-4) for n > 5.
G.f.: x^2*(1 - x)*(x + 1)^2/(2*x^2 - 1)^2. (End)

cp's OEIS Frontend

A003242 Number of compositions of n such that no two adjacent parts are equal (these are sometimes called Carlitz compositions).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A344604 Number of alternating compositions of n, including twins (x,x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A344614 Number of compositions of n with no adjacent triples (..., x, y, z, ...) where x < y < z or x > y > z.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A335126 A multiset whose multiplicities are the prime indices of n is inseparable.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A344615 Number of compositions of n with no adjacent triples (..., x, y, z, ...) where x <= y <= z.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A335434 Number of separable factorizations of n into factors > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A335127 A multiset whose multiplicities are the prime indices of n is separable.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A336103 Number of separable multisets of size n covering an initial interval of positive integers.

Views

Author

Keywords