A003441 -id:A003441 - cp's OEIS frontend

A295222 Array read by antidiagonals: T(n,k) is the number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals rooted at a cell up to rotation (k >= 3).

1, 1, 1, 1, 1, 3, 1, 1, 5, 10, 1, 1, 6, 22, 30, 1, 1, 8, 40, 116, 99, 1, 1, 9, 64, 285, 612, 335, 1, 1, 11, 92, 578, 2126, 3399, 1144, 1, 1, 12, 126, 1015, 5481, 16380, 19228, 3978, 1, 1, 14, 166, 1641, 11781, 54132, 129456, 111041, 14000

Offset: 1

Andrew Howroyd, Nov 17 2017

The polygon prior to dissection will have n*(k-2)+2 sides.

In the Harary, Palmer and Read reference these are the sequences called F.

			Array begins:
  ===========================================================
  n\k|     3      4       5        6         7          8
  ---|-------------------------------------------------------
   1 |     1      1       1        1         1          1 ...
   2 |     1      1       1        1         1          1 ...
   3 |     3      5       6        8         9         11 ...
   4 |    10     22      40       64        92        126 ...
   5 |    30    116     285      578      1015       1641 ...
   6 |    99    612    2126     5481     11781      22386 ...
   7 |   335   3399   16380    54132    141778     317860 ...
   8 |  1144  19228  129456   548340   1753074    4638348 ...
   9 |  3978 111041 1043460  5672645  22137570   69159400 ...
  10 | 14000 650325 8544965 59653210 284291205 1048927880 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
Wikipedia, Fuss-Catalan number

Columns k=3..5 are A003441, A005033, A005037.

Cf. A033282, A070914, A295224, A295259, A295260.

u[n_, k_, r_] := r*Binomial[(k - 1)*n + r, n]/((k - 1)*n + r);
T[n_, k_] := DivisorSum[GCD[n-1, k], EulerPhi[#]*u[(n-1)/#, k, k/#]&]/k;
Table[T[n - k + 3, k], {n, 1, 10}, {k, n + 2, 3, -1}] // Flatten (* Jean-François Alcover, Nov 21 2017, after Andrew Howroyd *)

\\ here u is Fuss-Catalan sequence with p = k+1.
u(n,k,r)={r*binomial((k - 1)*n + r, n)/((k - 1)*n + r)}
T(n,k)=sumdiv(gcd(n-1,k), d, eulerphi(d)*u((n-1)/d, k, k/d))/k;
for(n=1, 10, for(k=3, 8, print1(T(n, k), ", ")); print);

from sympy import binomial, gcd, totient, divisors
def u(n, k, r): return r*binomial((k - 1)*n + r, n)//((k - 1)*n + r)
def T(n, k): return sum([totient(d)*u((n - 1)//d, k, k//d) for d in divisors(gcd(n - 1, k))])//k
for n in range(1, 11): print([T(n, k) for k in range(3, 9)]) # Indranil Ghosh, Dec 13 2017, after PARI

T(n,k) = Sum_{d|gcd(n-1,k)} phi(d)*u((n-1)/d, k, k/d)/k where u(n,k,r) = r*binomial((k - 1)*n + r, n)/((k - 1)*n + r).

T(n,k) ~ n*A070914(n,k-2)/(n*(k-2)+2) for fixed k.

A050181 T(2n+3, n), array T as in A051168; a count of Lyndon words.

Original entry on oeis.org

0, 1, 3, 9, 30, 99, 333, 1144, 3978, 13995, 49742, 178296, 643842, 2340135, 8554275, 31429026, 115997970, 429874830, 1598952366, 5967382200, 22338765540, 83859016527, 315614844558, 1190680751376, 4501802223090, 17055399281284

Offset: 0

Clark Kimberling

nonn

Index entries for sequences related to Lyndon words

Cf. A003441.

A diagonal of the square array described in A051168.

A050181 := proc(n)
    A051168(2*n+3,n) ;
end proc: # R. J. Mathar, Jul 20 2016

a[n_] := (1/(2n+3)) Sum[MoebiusMu[d] Binomial[(2n+3)/d, n/d], {d, Divisors[ GCD[n, 3]]}];
a /@ Range[0, 25] (* Jean-François Alcover, Sep 17 2019, from PARI *)

a(n) = (1/(2*n+3))*sumdiv(gcd(n,3), d, moebius(d)*binomial((2*n+3)/d, n/d)); \\ Michel Marcus, Nov 18 2017

Conjecture: -(n-1)*(n+3)*(n+2)*a(n) + 2*(3*n-4)*(n+2)*(n+1)*a(n-1) - 4*n*(n+1)*(2*n-5)*a(n-2) + 2*(n-1)*(n+2)*(2*n-3)*a(n-3) - 4*(2*n-5)*(3*n-4)*(n+1)*a(n-4) + 8*n*(2*n-5)*(2*n-7)*a(n-5) = 0. - R. J. Mathar, Jul 20 2016
From Petros Hadjicostas, Nov 16 2017: (Start)
a(n) = (1/(2*n+3))*Sum_{d|gcd(n,3)} mu(d)*binomial((2*n+3)/d, n/d). (This is a special case of A. Howroyd's formula for double array A051168.)
a(n) = (1/(2*n+3))*(binomial(2*n+3, n) - binomial((2*n/3)+1, n/3)) if 3|n; = (1/(2*n+3))*binomial(2*n+3, n) otherwise.
Using the above formulae, one can verify R. J. Mathar's conjecture above.
(End)

A132892 Square array T(m,n) read by antidiagonals; T(m,n) is the number of equivalence classes in the set of sequences of n nonnegative integers that sum to m, generated by the equivalence relation defined in the following manner: we write a sequence in the form a[1]0a[2]0...0a[p], where each a[i] is a (possibly empty) sequence of positive integers; two sequences in this form, a[1]0a[2]0...0a[p] and b[1]0b[2]0...0b[q] are said to be equivalent if p=q and b[1],b[2],...,b[q] is a cyclic permutation of a[1],a[2],...a[p].

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 5, 3, 1, 1, 5, 9, 7, 4, 1, 1, 6, 13, 14, 10, 4, 1, 1, 7, 19, 25, 22, 12, 5, 1, 1, 8, 25, 41, 42, 30, 15, 5, 1, 1, 9, 33, 63, 79, 66, 43, 19, 6, 1, 1, 10, 41, 92, 131, 132, 99, 55, 22, 6, 1, 1, 11, 51, 129, 213, 245, 217, 143, 73, 26, 7, 1, 1, 12, 61, 175, 325, 428, 429, 335, 201, 91, 31, 7, 1

Offset: 1

Emeric Deutsch and Ira M. Gessel, Oct 02 2007

T(n,n) = A000108(n) (the Catalan numbers; see R. P. Stanley, Catalan addendum, problem starting "Equivalence classes of the equivalence relation ..."). T(m,m+1) = A007595(m+1); T(m,m+2) = A003441(m+1); T(m,m+3) = A003444(m+3); T(n+2,n) = A001453(n+1) (Catalan numbers - 1); T(m,1)=1; T(m,2)=m; T(m,3) = A080827(m) = A099392(m+1); T(m,4) = A004006(m).

			T(2,4) = 3 because we have {2000, 0200, 0020, 0002}, {1100, 0110, 0011} and {1010, 0101, 1001}.
T(4,2) = 4 because we have {40, 04}, {31}, {13} and {22}.
The square array starts:
  1....1.....1.....1......1.....1.....1...
  1....2.....3.....3......4.....4.....5...
  1....3.....5.....7.....10....12....15...
  1....4.....9....14.....22....30....43...
  1....5....13....25.....42....66....99...

Alois P. Heinz, antidiagonals n = 1..200, flattened
Emeric Deutsch and Ira Gessel, Equivalence Classes and Cyclic Arrangements:Problem 10525, Amer. Math. Monthly, 105, No. 8, 1998, 774-775 (published solution by D. Beckwith).
R. P. Stanley, Catalan addendum. See the interpretation (www, "Vertices of height n-1 of the tree T ...").

Cf. A000108, A007595, A003441, A003444, A001453, A080827, A099392, A004006.

with(numtheory): T:=proc(m,n) local r, div, N: r:=igcd(m,n+1): div:=divisors(r): N:=nops(div): (sum(phi(div[j])*(binomial((m+n+1)/div[j]-1,(n+1)/div[j]-1) -binomial(m/div[j]-1,(n+1)/div[j]-1)),j=1..N))/(n+1) end proc: for m to 12 do seq(T(m, n),n=1..12) end do; # yields the upper left 12 by 12 block of the infinite matrix T(m,n)
# second Maple program:
T:= proc(m, n) uses numtheory; (C-> add(phi(d)*(C((m+n+1)/d-1, (n+1)/d-1)
      -C(m/d-1, (n+1)/d-1))/(n+1), d=divisors(igcd(m, n+1))))(binomial)
    end:
seq(seq(T(1+d-n, n), n=1..d), d=1..14);  # Alois P. Heinz, Jan 28 2025

T[m_, n_] := Module[{r, div, N}, r = GCD[m, n + 1]; div = Divisors[r]; N = Length[div]; (Sum[EulerPhi[div[[j]]]*(Binomial[(m + n + 1)/div[[j]] - 1, (n + 1)/div[[j]] - 1] - Binomial[m/div[[j]] - 1, (n + 1)/div[[j]] - 1]), {j, 1, N}])/(n + 1)];
Table[T[m - n + 1, n], {m, 1, 13}, {n, 1, m}] // Flatten (* Jean-François Alcover, Sep 01 2024, after Maple program *)

T(m,n) = Sum_{d | gcd(m,n+1)} phi(d)*(C((m+n+1)/d-1, (n+1)/d-1) - C(m/d-1, (n+1)/d-1))/(n+1). [corrected by Jason Yuen, Jan 28 2025]

cp's OEIS Frontend

A295222 Array read by antidiagonals: T(n,k) is the number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals rooted at a cell up to rotation (k >= 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A050181 T(2n+3, n), array T as in A051168; a count of Lyndon words.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula