A261960 -id:A261960 - 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

A032020 Number of compositions (ordered partitions) of n into distinct parts.

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 11, 13, 19, 27, 57, 65, 101, 133, 193, 351, 435, 617, 851, 1177, 1555, 2751, 3297, 4757, 6293, 8761, 11305, 15603, 24315, 30461, 41867, 55741, 74875, 98043, 130809, 168425, 257405, 315973, 431065, 558327, 751491, 958265, 1277867, 1621273

Offset: 0

Christian G. Bower, Apr 01 1998

Compositions into distinct parts are equivalent to (1,1)-avoiding compositions. - Gus Wiseman, Jun 25 2020

All terms are odd. - Alois P. Heinz, Apr 09 2021

			a(6) = 11 because 6 = 5+1 = 4+2 = 3+2+1 = 3+1+2 = 2+4 = 2+3+1 = 2+1+3 = 1+5 = 1+3+2 = 1+2+3.
From _Gus Wiseman_, Jun 25 2020: (Start)
The a(0) = 1 through a(7) = 13 strict compositions:
  ()  (1)  (2)  (3)    (4)    (5)    (6)      (7)
                (1,2)  (1,3)  (1,4)  (1,5)    (1,6)
                (2,1)  (3,1)  (2,3)  (2,4)    (2,5)
                              (3,2)  (4,2)    (3,4)
                              (4,1)  (5,1)    (4,3)
                                     (1,2,3)  (5,2)
                                     (1,3,2)  (6,1)
                                     (2,1,3)  (1,2,4)
                                     (2,3,1)  (1,4,2)
                                     (3,1,2)  (2,1,4)
                                     (3,2,1)  (2,4,1)
                                              (4,1,2)
                                              (4,2,1)
(End)

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
C. G. Bower, Transforms (2)
Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449 [math.CO], 2018.
B. Richmond and A. Knopfmacher, Compositions with distinct parts, Aequationes Mathematicae 49 (1995), pp. 86-97.
B. Richmond and A. Knopfmacher, Compositions with distinct parts, Aequationes Mathematicae 49 (1995), pp. 86-97. (free access)
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Cf. A008289, A032011.
Row sums of A241719.
Column k=1 of A243081, A242447, A261835, A261836, A327244, A327245.
Main diagonal of A261960.
Dominated by A003242 (anti-run compositions).
These compositions are ranked by A233564.
(1,1)-avoiding patterns are counted by A000142.
Numbers with strict prime signature are A130091.
(1,1,1)-avoiding compositions are counted by A232432.
(1,1)-matching compositions are counted by A261982.
Inseparable partitions are counted by A325535.
Patterns matched by compositions are counted by A335456.
Strict permutations of prime indices are counted by A335489.
Cf. A000009, A011782, A102726, A181796, A261962, A333489, A335457.

b:= proc(n, i) b(n, i):= `if`(n=0, [1], `if`(i<1, [], zip((x, y)
      -> x+y, b(n, i-1), `if`(i>n, [], [0, b(n-i, i-1)[]]), 0))) end:
a:= proc(n) local l; l:=b(n, n): add((i-1)! *l[i], i=1..nops(l)) end:
seq(a(n), n=0..50);  # Alois P. Heinz, Dec 12 2012
# second Maple program:
T:= proc(n, k) option remember; `if`(k<0 or n<0, 0,
      `if`(k=0, `if`(n=0, 1, 0), T(n-k, k) +k*T(n-k, k-1)))
    end:
a:= n-> add(T(n, k), k=0..floor((sqrt(8*n+1)-1)/2)):
seq(a(n), n=0..60);  # Alois P. Heinz, Sep 04 2015

f[list_]:=Length[list]!; Table[Total[Map[f, Select[IntegerPartitions[n], Sort[#] == Union[#] &]]], {n, 0,30}]
T[n_, k_] := T[n, k] = If[k<0 || n<0, 0, If[k==0, If[n==0, 1, 0], T[n-k, k] + k*T[n-k, k-1]]]; a[n_] := Sum[T[n, k], {k, 0, Floor[(Sqrt[8*n + 1] - 1) / 2]}]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Sep 22 2015, after Alois P. Heinz *)

N=66;  q='q+O('q^N);
gf=sum(n=0,N, n!*q^(n*(n+1)/2) / prod(k=1,n, 1-q^k ) );
Vec(gf)
/* Joerg Arndt, Oct 20 2012 */

Q(N) = { \\ A008289
  my(q = vector(N)); q[1] = [1, 0, 0, 0];
  for (n = 2, N,
    my(m = (sqrtint(8*n+1) - 1)\2);
    q[n] = vector((1 + (m>>2)) << 2); q[n][1] = 1;
    for (k = 2, m, q[n][k] = q[n-k][k] + q[n-k][k-1]));
  return(q);
};
seq(N) = concat(1, apply(q -> sum(k = 1, #q, q[k] * k!), Q(N)));
seq(43) \\ Gheorghe Coserea, Sep 09 2018

"AGK" (ordered, elements, unlabeled) transform of 1, 1, 1, 1, ...
G.f.: Sum_{k>=0} k! * x^((k^2+k)/2) / Product_{j=1..k} (1-x^j). - David W. Wilson May 04 2000
a(n) = Sum_{m=1..n} A008289(n,m)*m!. - Geoffrey Critzer, Sep 07 2012

A261959 Number A(n,k) of ordered set partitions of {1,2,...,n} such that no part has the same size as any of its k immediate predecessors; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 1, 13, 1, 1, 1, 7, 75, 1, 1, 1, 7, 21, 541, 1, 1, 1, 7, 9, 81, 4683, 1, 1, 1, 7, 9, 31, 793, 47293, 1, 1, 1, 7, 9, 31, 403, 4929, 545835, 1, 1, 1, 7, 9, 31, 403, 1597, 33029, 7087261, 1, 1, 1, 7, 9, 31, 403, 757, 7913, 388537, 102247563

Offset: 0

Alois P. Heinz, Sep 06 2015

			A(3,1) = 7: 123, 1|23, 23|1, 2|13, 13|2, 3|12, 12|3.
A(4,1) = 21: 1234, 1|234, 234|1, 2|134, 134|2, 3|124, 124|3, 4|123, 123|4, 3|12|4, 4|12|3, 2|13|4, 4|13|2, 2|14|3, 3|14|2, 1|23|4, 4|23|1, 1|24|3, 3|24|1, 1|34|2, 2|34|1.
Square array A(n,k) begins:
:    1,   1,   1,   1,   1,   1,   1, ...
:    1,   1,   1,   1,   1,   1,   1, ...
:    3,   1,   1,   1,   1,   1,   1, ...
:   13,   7,   7,   7,   7,   7,   7, ...
:   75,  21,   9,   9,   9,   9,   9, ...
:  541,  81,  31,  31,  31,  31,  31, ...
: 4683, 793, 403, 403, 403, 403, 403, ...

Alois P. Heinz, Antidiagonals n = 0..50, flattened

Columns k=0..6 give A000670, A114902, A261961, A272431, A272432, A272433, A272434.
Main diagonal gives A032011.
Cf. A261960.

b:= proc(n, l) option remember; `if`(n=0, 1,
       add(`if`(j in l, 0, binomial(n, j)*b(n-j,
      `if`(l=[], [], [subsop(1=NULL, l)[], j]))), j=1..n))
    end:
A:= (n, k)-> b(n, [0$min(n,k)]):
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[n_, l_List] := b[n, l] = If[n == 0, 1, Sum[If[MemberQ[l, j], 0, Binomial[n, j]*b[n-j, If[l == {}, {}, Append[ReplacePart[l, 1 -> Nothing], j]]]], {j, 1, n}]]; A[n_, k_] := b[n, Array[0&, Min[n, k]]];  Table[A[n, d-n], {d, 0, 10} , {n, 0, d}] // Flatten (* Jean-François Alcover, Dec 17 2016, after Alois P. Heinz *)

A261962 Number of compositions of n such that no part equals any of its two immediate predecessors.

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 11, 15, 23, 37, 67, 101, 165, 265, 419, 691, 1123, 1789, 2909, 4657, 7515, 12183, 19657, 31635, 51101, 82449, 132989, 214623, 346485, 558587, 901399, 1454949, 2347157, 3787197, 6111131, 9858931, 15908393, 25669125, 41416849, 66826277

Offset: 0

Alois P. Heinz, Sep 06 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..500

Column k=2 of A261960.

Cf. A261961.

b:= proc(n, i, j) option remember; `if`(n=0, 1, add(
      `if`(k=i or k=j, 0, (t-> b(t, `if`(k>t, 0, k),
      `if`(i>t, 0, i)))(n-k)), k=1..n))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..50);

b[n_, i_, j_] := b[n, i, j] = If[n == 0, 1, Sum[If[k == i || k == j, 0, Function[t, b[t, If[k>t, 0, k], If[i>t, 0, i]]][n - k]], {k, 1, n}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 50] (* Jean-François Alcover, Dec 03 2020, after Alois P. Heinz *)

a(n) ~ c * d^n, where d = 1.61350953985228953675390530863679475666564394885974..., c = 0.5270561325668460003703909484716134447490733801644227... - Vaclav Kotesovec, Sep 21 2019

A261981 Number T(n,k) of compositions of n such that k is the minimal distance between two identical parts; triangle T(n,k), n>=2, 1<=k<=floor((sqrt(8*n-7)-1)/2), read by rows.

Original entry on oeis.org

1, 1, 4, 1, 9, 2, 18, 3, 41, 8, 2, 89, 16, 4, 185, 34, 10, 388, 57, 10, 810, 113, 30, 6, 1670, 213, 52, 12, 3435, 396, 104, 28, 7040, 733, 176, 50, 14360, 1333, 278, 62, 29226, 2419, 512, 152, 24, 59347, 4400, 878, 246, 48, 120229, 7934, 1492, 458, 108

Offset: 2

Alois P. Heinz, Sep 07 2015

			T(5,1) = 9: 311, 113, 221, 122, 2111, 1211, 1121, 1112, 11111.
T(5,2) = 2: 131, 212.
T(7,2) = 8: 151, 313, 232, 3121, 1213, 2131, 1312, 12121.
T(7,3) = 2: 1231, 1321.
Triangle T(n,k) begins:
n\k:     1     2    3    4   5
---+---------------------------
02 :     1;
03 :     1;
04 :     4,    1;
05 :     9,    2;
06 :    18,    3;
07 :    41,    8,   2;
08 :    89,   16,   4;
09 :   185,   34,  10;
10 :   388,   57,  10;
11 :   810,  113,  30,   6;
12 :  1670,  213,  52,  12;
13 :  3435,  396, 104,  28;
14 :  7040,  733, 176,  50;
15 : 14360, 1333, 278,  62;
16 : 29226, 2419, 512, 152, 24;

Alois P. Heinz, Rows n = 2..55, flattened

Columns k=1-2 give: A261983, A261984.
Row sums give A261982.
Cf. A000142, A261960, A262191.

b:= proc(n, l) option remember;
      `if`(n=0, 1, add(`if`(j in l, 0, b(n-j,
      `if`(l=[], [], [subsop(1=NULL, l)[], j]))), j=1..n))
    end:
T:= (n, k)-> b(n, [0$(k-1)])-b(n, [0$k]):
seq(seq(T(n, k), k=1..floor((sqrt(8*n-7)-1)/2)), n=2..20);

b[n_, l_] := b[n, l] = If[n == 0, 1, Sum[If[MemberQ[l, j], 0, b[n-j, If[l == {}, {}, Append[Rest[l], j]]]], {j, 1, n}]];
A[n_, k_] := b[n, Array[0&, Min[n, k]]];
T[n_, k_] := A[n, k-1] - A[n, k];
Table[T[n, k], {n, 2, 20}, {k, 1, Floor[(Sqrt[8*n-7]-1)/2]}] // Flatten (* Jean-François Alcover, Apr 13 2017, after Alois P. Heinz *)

T(n,k) = A261960(n,k-1) - A261960(n,k).

T((n+1)*(n+2)/2+1,n+1) = A000142(n) for n>=0.

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

A032020 Number of compositions (ordered partitions) of n into distinct parts.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A261959 Number A(n,k) of ordered set partitions of {1,2,...,n} such that no part has the same size as any of its k immediate predecessors; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A261962 Number of compositions of n such that no part equals any of its two immediate predecessors.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A261981 Number T(n,k) of compositions of n such that k is the minimal distance between two identical parts; triangle T(n,k), n>=2, 1<=k<=floor((sqrt(8*n-7)-1)/2), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula