A071201 -id:A071201

Search: a071201 -id:a071201

Displaying 1-5 of 5 results found.

page 1

A070914

Array read by antidiagonals giving number of paths up and left from (0,0) to (n,kn) where x/y <= k for all intermediate points.

+10
19

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 5, 1, 1, 1, 4, 12, 14, 1, 1, 1, 5, 22, 55, 42, 1, 1, 1, 6, 35, 140, 273, 132, 1, 1, 1, 7, 51, 285, 969, 1428, 429, 1, 1, 1, 8, 70, 506, 2530, 7084, 7752, 1430, 1, 1, 1, 9, 92, 819, 5481, 23751, 53820, 43263, 4862, 1, 1, 1, 10, 117, 1240

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,9

COMMENTS

Also related to dissections of polygons and enumeration of trees.

Number of dissections of a polygon into n (k+2)-gons by nonintersecting diagonals. All dissections are counted separately. See A295260 for nonequivalent solutions up to rotation and reflection. - Andrew Howroyd, Nov 20 2017

Number of rooted polyominoes composed of n (k+2)-gonal cells of the hyperbolic (Euclidean for k=0) regular tiling with Schläfli symbol {k+2,oo}. A rooted polyomino has one external edge identified, and chiral pairs are counted as two. For k>0, a stereographic projection of the {k+2,oo} tiling on the Poincaré disk can be obtained via the Christensson link. - Robert A. Russell, Jan 27 2024

LINKS

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

Malin Christensson, Make hyperbolic tilings of images, web page, 2019.

Peter Hilton and Jean Pedersen, Catalan Numbers, Their Generalization, and Their Uses, The Mathematical Intelligencer, March 1991, Volume 13, Issue 2, pp. 64-75.

V. E. Hoggatt, Jr. and M. Bicknell, Catalan and related sequences arising from inverses of Pascal's triangle matrices, Fib. Quart., 14 (1976), 395-405.

FORMULA

T(n, k) = binomial(n*(k+1), n)/(n*k+1) = A071201(n, k*n) = A071201(n, k*n+1) = A071202(n, k*n+1) = A062993(n+k-1, k-1).

If P(k,x) = Sum_{n>=0} T(n,k)*x^n is the g.f. of column k (k>=0), then P(k,x) = exp(1/(k+1)*(Sum_{j>0} (1/j)*binomial((k+1)*j,j)*x^j)). - Werner Schulte, Oct 13 2015

EXAMPLE

Rows start:

===========================================================

n\k| 0 1 2 3 4 5 6

---|-------------------------------------------------------

0 | 1, 1, 1, 1, 1, 1, 1 ...

1 | 1, 1, 1, 1, 1, 1, 1 ...

2 | 1, 2, 3, 4, 5, 6, 7 ...

3 | 1, 5, 12, 22, 35, 51, 70 ...

4 | 1, 14, 55, 140, 285, 506, 819 ...

5 | 1, 42, 273, 969, 2530, 5481, 10472 ...

6 | 1, 132, 1428, 7084, 23751, 62832, 141778 ...

7 | 1, 429, 7752, 53820, 231880, 749398, 1997688 ...

8 | 1, 1430, 43263, 420732, 2330445, 9203634, 28989675 ...

...

MAPLE

A:= (n, k)-> binomial((k+1)*n, n)/(k*n+1):

seq(seq(A(n, d-n), n=0..d), d=0..12); # Alois P. Heinz, Mar 25 2015

MATHEMATICA

T[n_, k_] = Binomial[n(k+1), n]/(k*n+1); Flatten[Table[T[n-k, k], {n, 0, 9}, {k, n, 0, -1}]] (* Jean-François Alcover, Apr 08 2016 *)

PROG

(PARI) T(n, k) = binomial(n*(k+1), n)/(n*k+1); \\ Andrew Howroyd, Nov 20 2017

CROSSREFS

Rows include A000012 (twice), A000027, A000326.

Columns include A000012, A000108 (Catalan), A001764, A002293, A002294, A002295, A002296, A007556, A062994, A059968.

Reflected version of A062993 (which is the main entry).

Cf. A295260.

Polyominoes: A295224 (oriented), A295260 (unoriented).

KEYWORD

nonn,tabl

AUTHOR

Henry Bottomley, May 20 2002

STATUS

approved

A091144

a(n) = binomial(n^2, n)/(1+(n-1)*n).

+10
5

1, 1, 2, 12, 140, 2530, 62832, 1997688, 77652024, 3573805950, 190223180840, 11502251937176, 779092434772236, 58448142042957576, 4811642166029230560, 431306008583779517040, 41820546066482630185200

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

Diagonal of array T(n,k) = binomial(kn,n)/(1+(k-1)n).

Number of paths up and left from (0,0) to (n^2-n,n) where x/y <= n-1 for all intermediate points. - Henry Bottomley, Dec 25 2003

Empirical: In the ring of symmetric functions over the fraction field Q(q, t), letting s(1^n) denote the Schur function indexed by (1^n), a(n) is equal to the coefficient of s(n) in nabla^(n)s(1^n) with q=t=1, where nabla denotes the "nabla operator" on symmetric functions, and s(n) denotes the Schur function indexed by the integer partition (n) of n. - John M. Campbell, Apr 06 2018

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..200

D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344.

FORMULA

From Henry Bottomley, Dec 25 2003: (Start)

a(n) = A014062(n)/A002061(n);

a(n) = A062993(n-2, n);

a(n) = A070914(n, n-1);

a(n) = A071201(n, n^2-n);

a(n) = A071201(n, n^2-n+1);

a(n) = A071202(n, n^2-n+1). (End)

MAPLE

A091144 := proc(n)

binomial(n^2, n)/(1+n*(n-1)) ;

end proc: # R. J. Mathar, Feb 14 2015

MATHEMATICA

Table[Binomial[n^2, n] / (n (n - 1) + 1), {n, 0, 20}] (* Vincenzo Librandi, Apr 07 2018 *)

PROG

(PARI) a(n) = binomial(n^2, n)/(n*(n-1)+1); \\ Altug Alkan, Apr 06 2018

(Magma) [Binomial(n^2, n)/(1+(n-1)*n): n in [0..20]]; // Vincenzo Librandi, Apr 07 2018

(GAP) List([0..20], n->Binomial(n^2, n)/(1+(n-1)*n)); # Muniru A Asiru, Apr 08 2018

CROSSREFS

Cf. A002061, A014062, A062993, A070914, A071201, A071202.

KEYWORD

nonn,easy

AUTHOR

Paul Barry, Dec 22 2003

STATUS

approved

A071202

Array read by antidiagonals giving number of paths up and left from (0,0) to (n,k) where x/y<n/k (except at start and finish).

+10
3

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 2, 1, 1, 3, 5, 5, 3, 1, 1, 3, 7, 5, 7, 3, 1, 1, 4, 7, 14, 14, 7, 4, 1, 1, 4, 12, 19, 14, 19, 12, 4, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 5, 15, 30, 66, 42, 66, 30, 15, 5, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 1, 6, 26, 67, 143, 202, 132

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,8

LINKS

Table of n, a(n) for n=1..85.

FORMULA

Some identities: a(n, k)=a(k, n); a(n, m*n)=a(n, m*n-1); a(n, n)=A000108(n-1); if n and k are coprime then a(n, k)=A071201(n, k)

KEYWORD

nonn,tabl

AUTHOR

Henry Bottomley, May 16 2002

STATUS

approved

A260419

Square array T(n,m) read by antidiagonals, T(n,m) is the number of (m,n)-parking functions.

+10
2

1, 1, 1, 1, 3, 1, 1, 3, 4, 1, 1, 5, 16, 11, 1, 1, 5, 16, 27, 16, 1, 1, 7, 25, 125, 81, 42, 1, 1, 7, 49, 125, 256, 378, 64, 1, 1, 9, 49, 243, 1296, 1184, 729, 163, 1, 1, 9, 64, 343, 1296, 3125, 4096, 2187, 256, 1, 1, 11, 100, 729, 2401, 16807, 15625, 27213, 9529, 638, 1

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

T(n,2) appears to be A027306(n).

LINKS

Alois P. Heinz, Antidiagonals n = 1..141, flattened

Jean-Christophe Aval, François Bergeron, Interlaced rectangular parking functions, arXiv:1503.03991 [math.CO], 2015.

FORMULA

T(n,m) = m^(n-1), if m and n are coprime (see Lemma in Aval & Bergeron link).

EXAMPLE

Table starts (see Table 1 in Aval & Bergeron link):

n/m 1 2 3 4 5

------------------------------

1 |1, 1, 1, 1, 1, ...

2 |1, 3, 3, 5, 5, ...

3 |1, 4, 16, 16, 25, ...

4 |1, 11, 27, 125, 125, ...

5 |1, 16, 81, 256, 1296, ...

6 |...

CROSSREFS

Cf. A071201.

KEYWORD

nonn,tabl

AUTHOR

Michel Marcus, Jul 25 2015

EXTENSIONS

More terms from Alois P. Heinz, Nov 30 2015

STATUS

approved

A298072

Number of binary strings of length n that are "prefix heavy", meaning that the fraction of "1" bits in any nonempty prefix is at least as great as the fraction of "1" bits in the entire string.

+10
2

1, 2, 3, 4, 6, 8, 15, 20, 40, 64, 126, 188, 434, 632, 1391, 2428, 4826, 7712, 17744, 27596, 62468, 106934, 220288, 364724, 834200, 1384470, 2954760, 5187588, 11085712, 18512792, 42379925, 69273668, 152600856, 268881898, 570336966, 1023023000, 2205306276

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

If each "1" is interpreted as a unit step to the north and each "0" is interpreted as a unit step to the east, then a prefix heavy string is any string for which the path taken as the bits of the string are examined from left to right has the property that the path does not go southeast of the line segment connecting the start of the path to the end of the path.

Every Dyck word, that is, every balanced string of parentheses, with "(" identified as "1" and ")" identified as "0", is prefix heavy because the fraction of "1" bits in the entire string is necessarily 0.5 and each prefix of nonzero length has at least half of its positions with a "1" bit. That is, each prefix has at least as many "(" characters as it has ")" characters.

Provably, a(n) is even if n is odd because there is a one-to-one relationship between a prefix heavy string with fewer than n/2 "1" bits and its reverse complement with more than n/2 "1" bits.

Provably, a(n) is odd if and only if n+2 is an integer power of 2. That is, a(n) is odd if and only if there are strings with exactly n/2 "1" bits (n is even) and there are an odd number of them that are prefix heavy (A000108(n/2) is odd).

LINKS

Lee A. Newberg, R code and Table of n, a(n) for n = 0..1024

FORMULA

a(n) = 2 + Sum_{k=1..n-1} A071201(n-k,k) for n>0.

a(2n) >= A000108(n) because Dyck words are prefix heavy.

EXAMPLE

For n=2, the a(2)=3 prefix heavy strings of length 2 are 00, 10, and 11, because each prefix of nonzero length is constituted of at least 0%, 50%, or 100% "1" bits, respectively.

For n=6, the a(6)=15 prefix heavy strings of length 6 are 000000, 100000, 100100, 101000, 101010, 101100, 110000, 110010, 110100, 110110, 111000, 111010, 111100, 111110, and 111111.

CROSSREFS

Cf. A000108, A071201.

KEYWORD

nonn

AUTHOR

Lee A. Newberg, Jan 11 2018

EXTENSIONS

a(28)-a(36) from Alois P. Heinz, Jan 11 2018

STATUS

approved

page 1

Search completed in 0.009 seconds