A212322 -id:A212322 - cp's OEIS frontend

A351018 Number of integer compositions of n with all distinct even-indexed parts and all distinct odd-indexed parts.

1, 1, 2, 3, 6, 9, 18, 27, 46, 77, 122, 191, 326, 497, 786, 1207, 1942, 2905, 4498, 6703, 10574, 15597, 23754, 35043, 52422, 78369, 115522, 169499, 248150, 360521, 532466, 768275, 1116126, 1606669, 2314426, 3301879, 4777078, 6772657, 9677138, 13688079, 19406214

Offset: 0

Gus Wiseman, Feb 09 2022

nonn

Also the number of binary words of length n starting with 1 and having all distinct runs (ranked by A175413, counted by A351016).

			The a(1) = 1 through a(6) = 18 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,1,2)  (4,1)    (4,2)
                     (2,1,1)  (1,1,3)  (5,1)
                              (1,2,2)  (1,1,4)
                              (2,2,1)  (1,2,3)
                              (3,1,1)  (1,3,2)
                                       (2,1,3)
                                       (2,3,1)
                                       (3,1,2)
                                       (3,2,1)
                                       (4,1,1)
                                       (1,1,2,2)
                                       (1,2,2,1)
                                       (2,1,1,2)
                                       (2,2,1,1)

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

The case of partitions is A000726.
The version for run-lengths instead of runs is A032020.
These words are ranked by A175413.
A005811 counts runs in binary expansion.
A011782 counts integer compositions.
A044813 lists numbers whose binary expansion has distinct run-lengths.
A059966 counts Lyndon compositions, necklaces A008965, aperiodic A000740.
A116608 counts compositions by number of distinct parts.
A238130 and A238279 count compositions by number of runs.
A242882 counts compositions with distinct multiplicities.
A297770 counts distinct runs in binary expansion.
A325545 counts compositions with distinct differences.
A329738 counts compositions with equal run-lengths.
A329744 counts compositions by runs-resistance.
A351014 counts distinct runs in standard compositions.
Counting words with all distinct runs:
- A351013 = compositions, for run-lengths A329739, ranked by A351290.
- A351016 = binary words, for run-lengths A351017.
- A351200 = patterns, for run-lengths A351292.
- A351202 = permutations of prime factors.
Cf. A003242, A025047, A098504, A098859, A106356, A212322, A328592, A329740, A334028, A349054, A350952, A351205.

Table[Length[Select[Tuples[{0,1},n],#=={}||First[#]==1&&UnsameQ@@Split[#]&]],{n,0,10}]

P(n)=prod(k=1, n, 1 + y*x^k + O(x*x^n));
seq(n)=my(p=P(n)); Vec(sum(k=0, n, polcoef(p,k\2,y)*(k\2)!*polcoef(p,(k+1)\2,y)*((k+1)\2)!)) \\ Andrew Howroyd, Feb 11 2022

a(n>0) = A351016(n)/2.

G.f.: Sum_{k>=0} floor(k/2)! * ceiling(k/2)! * ([y^floor(k/2)] P(x,y)) * ([y^ceiling(k/2)] P(x,y)), where P(x,y) = Product_{k>=1} 1 + y*x^k. - Andrew Howroyd, Feb 11 2022

Terms a(21) and beyond from Andrew Howroyd, Feb 11 2022

A241902 Decimal expansion of a constant related to Carlitz compositions (A003242).

Original entry on oeis.org

1, 7, 5, 0, 2, 4, 1, 2, 9, 1, 7, 1, 8, 3, 0, 9, 0, 3, 1, 2, 4, 9, 7, 3, 8, 6, 2, 4, 6, 3, 9, 8, 1, 5, 8, 7, 8, 7, 7, 8, 2, 0, 5, 8, 1, 8, 1, 3, 8, 1, 5, 9, 0, 5, 6, 1, 3, 1, 6, 5, 8, 6, 1, 3, 1, 7, 5, 1, 9, 3, 5, 1, 6, 7, 1, 5, 2, 0, 6, 0, 5, 0, 7, 7, 7, 4, 3, 8, 8, 7, 5, 6, 5, 7, 0, 9, 2, 4, 7, 1, 4, 1, 0, 0, 1

Offset: 1

Vaclav Kotesovec, May 01 2014

			1.7502412917183090312497386246398158787782...

Vaclav Kotesovec, Table of n, a(n) for n = 1..1500
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, p. 201.
A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.

Cf. A003242, A224958, A212322, A106357, A261984, A106369.

RealDigits[r /. FindRoot[Exp[QPolyGamma[0, 1 + Pi*I/Log[r], r]] == r^(3/2)/(1-r), {r, 3/2}, WorkingPrecision -> 120], 10, 110][[1]] (* Vaclav Kotesovec, Jun 19 2023 *)

Equals lim n -> infinity A003242(n)^(1/n).

A106369 Number of circular compositions of n such that no two adjacent parts are equal.

Original entry on oeis.org

1, 1, 2, 2, 3, 6, 7, 11, 18, 29, 42, 73, 111, 183, 299, 491, 796, 1333, 2188, 3652, 6073, 10155, 16959, 28500, 47813, 80508, 135621, 228967, 386749, 654535, 1108353, 1879478, 3189495, 5418556, 9212099, 15676275, 26694509, 45493327, 77580915

Offset: 1

Christian G. Bower, Apr 29 2005

nonn

By "circular compositions" here we mean equivalence classes of compositions with parts on a circle such that two compositions are equivalent if one is a cyclic shift of the other. - Petros Hadjicostas, Oct 15 2017

			a(6) = 6 because the 6 circular compositions of 6: 6, 5+1, 4+2, 3+2+1, 3+1+2, 2+1+2+1.

Vaclav Kotesovec, Table of n, a(n) for n = 1..1000
P. Hadjicostas, Cyclic, dihedral and symmetric Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.
Petros Hadjicostas, Proof of an explicit formula for Bower's CycleBG transform
Index entries for sequences related to necklaces

Cf. A000031, A008965, A212322, A292906.

nmax = 40; Rest[CoefficientList[Series[x/(1-x) - Sum[EulerPhi[s]/s*(Log[1 - Sum[x^(s*n)/(1 + x^(s*n)), {n, 1, nmax}]] + Sum[Log[1 + x^(s*n)], {n, 1, nmax}]), {s, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Sep 06 2017, after Petros Hadjicostas *)

CycleBG transform of (1, 1, 1, 1, ...).
CycleBG transform T(A) = invMOEBIUS(invEULER(Carlitz(A)) + A(x^2) - A) + A.
Carlitz transform T(A(x)) has g.f. 1/(1 - Sum_{k>0} (-1)^(k+1)*A(x^k)).
G.f.: x/(1-x) - Sum_{s>=1} (phi(s)/s)*f(x^s), where f(x) = log(1 - Sum_{n>=1} x^n/(1 + x^n)) + Sum_{n>=1} log(1 + x^n) and phi(s)=A000010 is Euler's totient function. - Petros Hadjicostas, Sep 06 2017
Conjecture: a(n) ~ A241902^n / n. - Vaclav Kotesovec, Sep 06 2017
General formula for the CycleBG transform: T(A)(x) = A(x) - Sum_{k>=0} A(x^(2k+1)) + Sum_{k>=1} (phi(k)/k)*log(Carlitz(A)(x^k)). For a proof, see the links above. (For this sequence, A(x) = x/(1-x).) - Petros Hadjicostas, Oct 08 2017
G.f.: -Sum_{s>=1} x^(2s+1)/(1-x^(2s+1)) - Sum_{s>=1} (phi(s)/s)*g(x^s), where g(x) = log(1 + Sum_{n>=1} (-x)^n/(1 - x^n)). (This formula can be proved from the general formula for the CycleBG transform given above.) - Petros Hadjicostas, Oct 10 2017

Name clarified by Andrew Howroyd, Oct 12 2017

A293595 Triangle read by rows: T(n,k) = number of compositions of n into k parts such that no two cyclically adjacent parts are equal.

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 1, 2, 0, 0, 1, 4, 0, 0, 0, 1, 4, 6, 2, 0, 0, 1, 6, 6, 4, 0, 0, 0, 1, 6, 12, 10, 0, 0, 0, 0, 1, 8, 18, 16, 10, 2, 0, 0, 0, 1, 8, 24, 40, 20, 6, 0, 0, 0, 0, 1, 10, 30, 52, 50, 18, 0, 0, 0, 0, 0, 1, 10, 42, 84, 90, 50, 14, 2, 0, 0, 0, 0

Offset: 1

Andrew Howroyd, Oct 12 2017

Compositions of length 1 are included.

See theorem 4 in Hadjicostas reference for generating function.

			Triangle begins:
  1;
  1,  0;
  1,  2,  0;
  1,  2,  0,  0;
  1,  4,  0,  0,  0;
  1,  4,  6,  2,  0,  0;
  1,  6,  6,  4,  0,  0,  0;
  1,  6, 12, 10,  0,  0,  0,  0;
  1,  8, 18, 16, 10,  2,  0,  0,  0;
  1,  8, 24, 40, 20,  6,  0,  0,  0,  0;
  ...
Case n=6:
The included compositions are:
k=1: 6;                                => T(6,1) = 1
k=2: 15, 24, 42, 51;                   => T(6,2) = 4
k=3: 123, 132, 213, 231, 312, 321;     => T(6,3) = 6
k=4: 1212, 2121;                       => T(6,4) = 2

Andrew Howroyd, Table of n, a(n) for n = 1..1275
P. Hadjicostas, Cyclic, dihedral and symmetric Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.

Row sums are in A212322.

Cf. A106351, A106369.

max = 10; gf = Sum[x^(2*j)*y^2/(1 + x^j*y), {j, 1, max}] + Sum[x^j*y/(1 + x^j*y)^2, {j, 1, max}]/(1 - Sum[ x^j*y/(1 + x^j*y), {j, 1, max}]) + O[x]^(max+1) + O[y]^(max+1) // Normal // Expand;
T[n_, k_] := SeriesCoefficient[gf, {x, 0, n}, {y, 0, k}];
Table[T[n, k], {n, 1, max}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 19 2018 *)

gf(n,y) = {my(A=sum(j=1, n, x^(2*j)*y^2/(1+x^j*y) + O(x*x^n)),
B=sum(j=1, n, x^j*y/(1+x^j*y)^2 + O(x*x^n)),
C=sum(j=1, n, x^j*y/(1+x^j*y) + O(x*x^n)));
A + B/(1-C)}
for(n=1,10,my(p=polcoeff(gf(n,y),n));for(k=1,n,print1(polcoeff(p,k),", "));print)

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

cp's OEIS Frontend

A351018 Number of integer compositions of n with all distinct even-indexed parts and all distinct odd-indexed parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A241902 Decimal expansion of a constant related to Carlitz compositions (A003242).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A106369 Number of circular compositions of n such that no two adjacent parts are equal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A293595 Triangle read by rows: T(n,k) = number of compositions of n into k parts such that no two cyclically adjacent parts are equal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula