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

A032011 Partition n labeled elements into sets of different sizes and order the sets.

Original entry on oeis.org

1, 1, 1, 7, 9, 31, 403, 757, 2873, 12607, 333051, 761377, 3699435, 16383121, 108710085, 4855474267, 13594184793, 76375572751, 388660153867, 2504206435681, 20148774553859, 1556349601444477, 5050276538344665, 33326552998257031, 186169293932977115, 1305062351972825281, 9600936552132048553, 106019265737746665727, 12708226588208611056333, 47376365554715905155127

Offset: 0

Christian G. Bower, Apr 01 1998

nonn

From Alois P. Heinz, Sep 02 2015: (Start)
Also the number of matrices with n rows of nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n and the column sums are distinct.  Equivalently, the number of compositions of n into distinct parts where each part i is marked with a word of length i over an n-ary alphabet whose letters appear in alphabetical order and all n letters occur exactly once.
a(3) = 7:
[1]   [1 0]  [0 1]  [1 0]  [0 1]  [0 1]  [1 0]
[1]   [1 0]  [0 1]  [0 1]  [1 0]  [1 0]  [0 1]
[1]   [0 1]  [1 0]  [1 0]  [0 1]  [1 0]  [0 1].
3abc, 2ab1c, 1c2ab, 2ac1b, 1b2ac, 2bc1a, 1a2bc.  (End)

Alois P. Heinz, Table of n, a(n) for n = 0..670
C. G. Bower, Transforms (2)

Cf. A000670, A007837, A032020, A114902, A120774, A131632.

Main diagonal of A261836 and A261959.

b:= proc(n, i, p) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1)*binomial(n,i))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 02 2015

f[list_]:=Apply[Multinomial,list]*Length[list]!; Table[Total[Map[f, Select[IntegerPartitions[n], Sort[#] == Union[#] &]]], {n, 1, 30}]
b[n_, i_, p_] := b[n, i, p] = If[i*(i+1)/2n, 0, b[n-i, i-1, p+1]*Binomial[n, i]]]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 16 2015, after Alois P. Heinz *)

seq(n)=[subst(serlaplace(y^0*p),y,1) | p <- Vec(serlaplace(prod(k=1, n, 1 + x^k*y/k! + O(x*x^n))))] \\ Andrew Howroyd, Sep 13 2018

"AGJ" (ordered, elements, labeled) transform of 1, 1, 1, 1, ...

a(n) = Sum_{k>=0} k! * A131632(n,k). - Alois P. Heinz, Sep 09 2015

a(0)=1 prepended by Alois P. Heinz, Sep 02 2015

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 *)

A114903 Number of compositions of {1,..,n} such that no two adjacent parts are of equal size (labeled Carlitz compositions), allowing parts to be of size 0.

Original entry on oeis.org

2, 4, 12, 76, 572, 5204, 59340, 782996, 11707324, 197988340, 3720933092, 76811352116, 1730660689580, 42251140165108, 1110607948991028, 31279537587370916, 939737174809843644, 29996522608581396788, 1013814287146517455812, 36168456215193554061044

Offset: 0

Christian G. Bower, Jan 05 2006

nonn

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

Cf. A114900, A114902.

b:= proc(n, i) option remember;
      `if`(n=0, `if`(i=0, 1, 2), add(`if`(i=j, 0, b(n-j,
      `if`(j>n-j, -1, j))*binomial(n, j)), j=0..n))
    end:
a:= n-> b(n, -1):
seq(a(n), n=0..25);  # Alois P. Heinz, Sep 04 2015

b[n_, i_] := b[n, i] = If[n == 0, If[i == 0, 1, 2], Sum[If[i == j, 0, b[n - j, If[j > n - j, -1, j]]*Binomial[n, j]], {j, 0, n}]]; a[n_] := b[n, -1]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 25 2017, after Alois P. Heinz *)

E.g.f.: 2*B(x)/(2-B(x)) where B(x) is e.g.f. of A114902.

a(n) ~ c * d^n * n^(n + 1/2), where d = 0.6907524084725166379194613015033714490019226066943600905783847741049876032..., c = 4.71633079866926561049991146534865892961540468329142429184529629611133729... - Vaclav Kotesovec, Sep 21 2019

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

A032011 Partition n labeled elements into sets of different sizes and order the sets.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

A114903 Number of compositions of {1,..,n} such that no two adjacent parts are of equal size (labeled Carlitz compositions), allowing parts to be of size 0.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula