A156289 Triangle read by rows: T(n,k) is the number of end rhyme patterns of a poem of an even number of lines (2n) with 1<=k<=n evenly rhymed sounds.
1, 1, 3, 1, 15, 15, 1, 63, 210, 105, 1, 255, 2205, 3150, 945, 1, 1023, 21120, 65835, 51975, 10395, 1, 4095, 195195, 1201200, 1891890, 945945, 135135, 1, 16383, 1777230, 20585565, 58108050, 54864810, 18918900, 2027025, 1, 65535, 16076985
Offset: 1
Examples
The triangle begins n\k|..1.....2......3......4......5......6 ========================================= .1.|..1 .2.|..1.....3 .3.|..1....15.....15 .4.|..1....63....210....105 .5.|..1...255...2205...3150....945 .6.|..1..1023..21120..65835..51975..10395 .. T(3,3) = 15. The 15 partitions of the set [6] into three even blocks are: (12)(34)(56), (12)(35)(46), (12)(36)(45), (13)(24)(56), (13)(25)(46), (13)(26)(45), (14)(23)(56), (14)(25)(36), (14)(26)(35), (15)(23)(46), (15)(24)(36), (15)(26)(34), (16)(23)(45), (16)(24)(35), (16)(25)(34). Examples of recurrence relation T(4,3) = 5*T(3,2) + 9*T(3,3) = 5*15 + 9*15 = 210; T(6,5) = 9*T(5,4) + 25*T(5,5) = 9*3150 + 25*945 = 51975. T(4,2) = 28 + 35 = 63 (M_3 multinomials A036040 for partitions of 8 with 3 even parts, namely (2,6) and (4^2)). - _Wolfdieter Lang_, May 13 2015
References
- L. Comtet, Analyse Combinatoire, Presses Univ. de France, 1970, Vol. II, pages 61-62.
- L. Comtet, Advanced Combinatorics, Reidel, 1974, pages 225-226.
Links
- Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150, flattened)
- Richard Olu Awonusika, On Jacobi polynomials P_k(alpha, beta) and coefficients c_j^L(alpha, beta) (k >= 0, L = 5,6; 1 <= j <= L; alpha, beta > -1), The Journal of Analysis (2020).
- Thomas Browning, Counting Parabolic Double Cosets in Symmetric Groups, arXiv:2010.13256 [math.CO], 2020.
- J. Riordan, Letter, Jul 06 1978
Crossrefs
Programs
-
Maple
T := proc(n,k) option remember; `if`(k = 0 and n = 0, 1, `if`(n < 0, 0, (2*k-1)*T(n-1, k-1) + k^2*T(n-1, k))) end: for n from 1 to 8 do seq(T(n,k), k=1..n) od; # Peter Luschny, Sep 04 2017
-
Mathematica
T[n_,k_] := Which[n < k, 0, n == 1, 1, True, 2/Factorial2[2 k] Sum[(-1)^(k + j) Binomial[2 k, k + j] j^(2 n), {j, 1, k}]] (* alternate computation with function triangle[] defined in A257490 *) a[n_]:=Map[Apply[Plus,#]&,triangle[n],{2}] (* Hartmut F. W. Hoft, Apr 26 2015 *)
Formula
Recursion: T(n,1)=1 for 1<=n; T(n,k)=0 for 1<=n
Generating function for the k-th column of the triangle T(i+k,k):
G(k,x) = Sum_{i>=0} T(i+k,k)*x^i = Product_{j=1..k} (2*j-1)/(1-j^2*x).
Closed form expression: T(n,k) = (2/(k!*2^k))*Sum_{j=1..k} (-1)^(k-j)*binomial(2*k,k-j)*j^(2*n).
From Peter Bala, Feb 21 2011: (Start)
GENERATING FUNCTION
E.g.f. (including a constant 1):
(1)... F(x,z) = exp(x*(cosh(z)-1))
= Sum_{n>=0} R(n,x)*z^(2*n)/(2*n)!
= 1 + x*z^2/2! + (x + 3*x^2)*z^4/4! + (x + 15*x^2 + 15*x^3)*z^6/6! + ....
ROW POLYNOMIALS
The row polynomials R(n,x) begin
... R(1,x) = x
... R(2,x) = x + 3*x^2
... R(3,x) = x + 15*x^2 + 15*x^3.
The egf F(x,z) satisfies the partial differential equation
(2)... d^2/dz^2(F) = x*F + x*(2*x+1)*F' + x^2*F'',
where ' denotes differentiation with respect to x. Hence the row polynomials satisfy the recurrence relation
(3)... R(n+1,x) = x*{R(n,x) + (2*x+1)*R'(n,x) + x*R''(n,x)}
with R(0,x) = 1. The recurrence relation for T(n,k) given above follows from this.
(4)... T(n,k) = (2*k-1)!!*A036969(n,k).
(End)
A180874 Lassalle's sequence connected with Catalan numbers and Narayana polynomials.
1, 1, 5, 56, 1092, 32670, 1387815, 79389310, 5882844968, 548129834616, 62720089624920, 8646340208462880, 1413380381699497200, 270316008395632253340, 59800308109377016336155, 15151722444639718679892150, 4359147487054262623576455600
Offset: 1
Comments
Defined by the recurrence formula in Theorem 1, page 2 of Lasalle.
From Tom Copeland, Jan 26 2016: (Start)
Let G(t) = Sum_{n>=0} t^(2n)/(n!(n+1)!) = exp(c.t) be the e.g.f. of the aerated Catalan numbers c_n of A126120.
R = x + H(D) = x + d/dD log[G(D)] = x + D - D^3/3! + 5 D^5/5! - 56 D^7/7! + ... = x + e^(r. D) generates a signed, aerated version of this entry's sequence a(n), (r.)^(2n+1) = r(2n+1) = (-1)^n a(n+1) for n>=0 and r(0) = a(0) = 0, and is, with D = d/dx, the raising operator for the Appell polynomials P(n,x) of A097610, where P(n,x) = (c. + x)^n = Sum{k=0 to n} binomial(n,k) c_k x^(n-k) with c_k = A126120(k), i.e., R P(n,x) = P(n+1,x).
d/dt log[G(t)] = e^(r.t) = e^(q.t) / e^(c.t) = Ev[c. e^(c.t)] / Ev[e^(c.t)] = e^(q.t) e^(d.t) = [Sum_{n>=0} 2n t^(2n-1)/(n!(n+1)!)] / [Sum_{n>=0} t^(2n)/(n!(n+1)!)] with Ev[..] denoting umbral evaluation, so q(n) = c(n+1) = A126120(n+1) and d(2n) = (-1)^n A238390(n) and vanishes otherwise. Then (r. + c.)^n = q(n) = Sum_{k=0..n} binomial(n,k) r(k) c(n-k) and (q. + d.)^n = r(n), relating A180874, A126120 (A000108), and A238390 through binomial convolutions.
The sequence can also be represented in terms of the Faber polynomials of A263916 as a(n) = |(2n-1)! F(2n,0,b(2),0,b(4),0,..)| = |h(2n)| where b(2n) = 1/(n!(n + 1)!) = A126120(2n)/(2n)! = A000108(n)/(2n)!, giving h(0) = 1, h(1) = 0, h(2) = 1, h(3) = 0, h(4) = -1, h(5) = 0, h(6) = 5, h(7) = 0, h(8) = -56, ..., implying, among other relations, that A000108(n/2)= A126120(n) = Bell(n,0,h(2),0,h(4),...), the Bell polynomials of A036040 which reduce to A257490 in this case.
(End)
From Colin Defant, Sep 06 2018: (Start)
a(n) is the number of pairs (rho,r), where rho is a matching on [2n] and r is an acyclic orientation of the crossing graph of rho in which the block containing 1 is the only source (see the Josuat-Verges paper or the Defant-Engen-Miller paper for definitions).
a(n) is the number of permutations of [2n-1] that have exactly 1 preimage under West's stack-sorting map.
a(n) is the number of valid hook configurations of permutations of [2n-1] that have n-1 hooks (see the paper by Defant, Engen, and Miller for definitions).
Say a binary tree is full if every vertex has either 0 or 2 children. If u is a left child in such a tree, then we can start at the sibling of u and travel down left edges until reaching a leaf v. Call v the leftmost nephew of u. A decreasing binary plane tree on [m] is a binary plane tree labeled with the elements of [m] in which every nonroot vertex has a label that is smaller than the label of its parent. a(n) is the number of full decreasing binary plane trees on [2n-1] in which every left child has a label that is larger than the label of its leftmost nephew.
(End)
Links
- G. C. Greubel, Table of n, a(n) for n = 1..250
- Colin Defant, Descents in t-Sorted Permutations, arXiv:1904.02613 [math.CO], 2019.
- Colin Defant, Michael Engen, and Jordan A. Miller, Stack-sorting, set partitions, and Lassalle's sequence, arXiv:1809.01340 [math.CO], 2018.
- Colin Defant, Catalan Intervals and Uniquely Sorted Permutations, arXiv:1904.02627 [math.CO], 2019.
- Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020. See p. 37.
- Matthieu Josuat-Verges, Cumulants of the q-semicircular law, Tutte polynomials, and heaps, arXiv:1203.3157 [math.CO], 2012.
- Michel Lassalle, Catalan numbers and a new integer sequence, arXiv:1009.4225 [math.CO], 2010-2012.
- Michel Lassalle, Two integer sequences related to Catalan numbers, Journal of Combinatorial Theory, Series A, Volume 119, Issue 4, May 2012, Pages 923-935.
- Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
Crossrefs
Programs
-
Maple
A000108 := proc(n) binomial(2*n,n)/(1+n) ; end proc: A180874 := proc(n) option remember; if n = 1 then 1; else A000108(n)+add((-1)^j*binomial(2*n-1,2*j-1)*procname(j)*A000108(n-j),j=1..n-1) ; %*(-1)^(n-1) ; end if; end proc: # R. J. Mathar, Apr 16 2011
-
Mathematica
nmax=20; a = ConstantArray[0,nmax]; a[[1]]=1; Do[a[[n]] = (-1)^(n-1)*(Binomial[2*n,n]/(n+1) + Sum[(-1)^j*Binomial[2n-1,2j-1]*a[[j]]* Binomial[2*(n-j),n-j]/(n-j+1),{j,1,n-1}]),{n,2,nmax}]; a (* Vaclav Kotesovec, Feb 28 2014 *)
Formula
a(n) = (-1)^(n-1) * (C(n)+Sum_{j=1..n-1} (-1)^j *binomial(2n-1,2j-1) * a(j) *C(n-j)), where C() = A000108(). - R. J. Mathar, Apr 17 2011, corrected by Vaclav Kotesovec, Feb 28 2014
E.g.f.: Sum_{k>=0} a(k)*x^(2*k+2)/(2*k+2)! = log(x/BesselJ(1,2*x)). - Sergei N. Gladkovskii, Dec 28 2011
a(n) ~ (n!)^2 / (sqrt(Pi) * n^(3/2) * r^n), where r = BesselJZero[1, 1]^2/16 = 0.917623165132743328576236110539381686855099186384686... - Vaclav Kotesovec, added Feb 28 2014, updated Mar 01 2014
Define E(m,n) by E(1,1) = 1, E(n,n) = 0 for n > 1, and E(m,n) = Sum_{j=1..m} Sum_{i=1..n-m-1} binomial(n-m-1,i-1) * F_j(i+j-1) * F_{m-j}(n-j-i) for 0 <= m < n, where F_m(n) = Sum_{j=m..n} E_j(n). Then a(n) = F_0(2n-1). - Colin Defant, Sep 06 2018
A260876 Number of m-shape set partitions, square array read by ascending antidiagonals, A(m,n) for m, n >= 0.
1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 4, 5, 5, 1, 1, 11, 31, 15, 7, 1, 1, 36, 365, 379, 52, 11, 1, 1, 127, 6271, 25323, 6556, 203, 15, 1, 1, 463, 129130, 3086331, 3068521, 150349, 877, 22, 1, 1, 1717, 2877421, 512251515, 3309362716, 583027547, 4373461, 4140, 30
Offset: 0
Comments
A set partition of m-shape is a partition of a set with cardinality m*n for some n >= 0 such that the sizes of the blocks are m times the parts of the integer partitions of n.
If m = 0, all possible sizes are zero. Thus the number of set partitions of 0-shape is the number of integer partitions of n (partition numbers A000041).
If m = 1, the set is {1, 2, ..., n} and the set of all possible sizes are the integer partitions of n. Thus the number of set partitions of 1-shape is the number of set partitions (Bell numbers A000110).
If m = 2, the set is {1, 2, ..., 2n} and the number of set partitions of 2-shape is the number of set partitions into even blocks A005046.
From Petros Hadjicostas, Aug 06 2019: (Start)
Irwin (1916) proved the following combinatorial result: Assume r_1, r_2, ..., r_n are positive integers and we have r_1*r_2*...*r_n objects. We divide them into r_1 classes of r_2*r_3*...*r_n objects each, then each class into r_2 subclasses of r_3*...*r_n objects each, and so on. We call each such classification, without reference to order, a "classification" par excellence. He proved that the total number of classifications is (r_1*r_2*...*r_n)!/( r1! * (r_2!)^(r_1) * (r_3!)^(r_1*r_2) * ... (r_n!)^(r_1*r_2*...*r_{n-1}) ).
Apparently, this problem appeared in Carmichael's "Theory of Numbers".
This result can definitely be used to prove some special cases of my conjecture below. (End)
Examples
[ n ] [0 1 2 3 4 5 6]
[ m ] ------------------------------------------------------
[ 0 ] [1, 1, 2, 3, 5, 7, 11] A000041
[ 1 ] [1, 1, 2, 5, 15, 52, 203] A000110
[ 2 ] [1, 1, 4, 31, 379, 6556, 150349] A005046
[ 3 ] [1, 1, 11, 365, 25323, 3068521, 583027547] A291973
[ 4 ] [1, 1, 36, 6271, 3086331, 3309362716, 6626013560301] A291975
A260878,A309725, ...
For example the number of set partitions of {1,2,...,9} with sizes in [9], [6,3] and [3,3,3] is 1, 84 and 280 respectively. Thus A(3,3) = 365.
Formatted as a triangle:
[1]
[1, 1]
[1, 1, 2]
[1, 1, 2, 3]
[1, 1, 4, 5, 5]
[1, 1, 11, 31, 15, 7]
[1, 1, 36, 365, 379, 52, 11]
[1, 1, 127, 6271, 25323, 6556, 203, 15]
.
From _Peter Luschny_, Aug 14 2019: (Start)
For example consider the case n = 4. There are five integer partitions of 4:
P = [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]. The shapes are m times the parts of the integer partitions: S(m) = [[4m], [3m, m], [2m, 2m], [2m, m, m], [m, m, m, m]].
* In the case m = 1 we look at set partitions of {1, 2, 3, 4} with sizes in [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]] which gives rise to [1, 4, 3, 6, 1] with sum 15.
* In the case m = 2 we look at set partitions of {1, 2, .., 8} with sizes in [[8], [6, 2], [4, 4], [4, 2, 2], [2, 2, 2, 2]] which gives rise to [1, 28, 35, 210, 105] with sum 379.
* In the case m = 0 we look at set partitions of {} with sizes in [[0], [0, 0], [0, 0], [0, 0, 0], [0, 0, 0, 0]] which gives rise to [1, 1, 1, 1, 1] with sum 5 (because the only partition of the empty set is the set that contains the empty set, thus from the definition T(0,4) = Sum_{S(0)} card({0}) = A000041(4) = 5).
If n runs through 0, 1, 2,... then the result is an irregular triangle in which the n-th row lists multinomials for partitions of [m*n] which have only parts which are multiples of m. These are the triangles A080575 (m = 1), A257490 (m = 2), A327003 (m = 3), A327004 (m = 4). In the case m = 0 the triangle is A000012 subdivided into rows of length A000041. See the cross references how this case integrates into the full picture.
(End)
Links
- Alois P. Heinz, Antidiagonals n = 0..54, flattened
- Frank Irwin, Solution to Problem 223 proposed by T. E. Mason in October 1914, Amer. Math. Monthly 23(9) (1916), 352-353.
Crossrefs
-----------------------------------------------------------------
[m] | multi- | sum of | main | by | comple- |
| nomials | rows | diagonal | size | mentary |
-----------------------------------------------------------------
Programs
-
Maple
A:= proc(m, n) option remember; `if`(m=0, combinat[numbpart](n), `if`(n=0, 1, add(binomial(m*n-1, m*k-1)*A(m, n-k), k=1..n))) end: seq(seq(A(d-n, n), n=0..d), d=0..10); # Alois P. Heinz, Aug 14 2019 -
Mathematica
A[m_, n_] := A[m, n] = If[m==0, PartitionsP[n], If[n==0, 1, Sum[Binomial[m n - 1, m k - 1] A[m, n - k], {k, 1, n}]]]; Table[Table[A[d - n, n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 06 2019, after Alois P. Heinz *) -
SageMath
def A260876(m, n): shapes = ([x*m for x in p] for p in Partitions(n)) return sum(SetPartitions(sum(s), s).cardinality() for s in shapes) for m in (0..4): print([A260876(m,n) for n in (0..6)])
Formula
From Petros Hadjicostas, Aug 02 2019: (Start)
A(m, 2) = 1 + (1/2) * binomial(2*m, m) for m >= 1.
A(m, 3) = 1 + binomial(3*m, m) + (3*m)!/(6 * (m!)^3) for m >= 1.
A(m, 4) = (1/4!) * multinomial(4*m, [m, m, m, m]) + (1/2) * multinomial(4*m, [2*m, m, m]) + multinomial(4*m, [m, 3*m]) + (1/2) * multinomial(4*m, [2*m, 2*m]) + 1 for m >= 1.
Conjecture: For n >= 0, let P be the set of all possible lists (a_1,...,a_n) of nonnegative integers such that a_1*1 + a_2*2 + ... + a_n*n = n. Consider terms of the form multinomial(n*m, m*[1,..., 1,2,..., 2,..., n,..., n])/(a_1! * a_2! * ... * a_n!), where in the list [1,...,1,2,...,2,...,n,...,n] the number 1 occurs a_1 times, 2 occurs a_2 times, ..., and n occurs a_n times. (Here a_n = 0 or 1.) Summing these terms over P we get A(m, n) provided m >= 1. (End)
Conjecture for a recurrence: A(m, n) = Sum_{k = 0..n-1} binomial(m*n - 1, m*k) * A(m, k) with A(m, 0) = 1 for m >= 1 and n >= 0. (Unfortunately, the recurrence does not hold for m = 0.) - Petros Hadjicostas, Aug 12 2019
A327003 Irregular triangle read by rows in which the n-th row lists multinomials for partitions of 3n which have only parts which are multiples of 3, in Hindenburg order.
1, 1, 1, 10, 1, 84, 280, 1, 220, 462, 9240, 15400, 1, 455, 5005, 50050, 210210, 1401400, 1401400, 1, 816, 18564, 185640, 24310, 4084080, 13613600, 2858856, 85765680, 285885600, 190590400, 1, 1330, 54264, 542640, 293930, 24690120, 82300400, 32332300, 135795660, 2715913200, 4526522000, 3802278480, 38022784800, 76045569600, 36212176000
Offset: 0
Comments
The Hindenburg order refers to the partition generating algorithm of C. F. Hindenburg (1779). [Knuth 7.2.1.4H]
Examples
The irregular triangle starts: [0] [1] [1] [1] [2] [1, 10] [3] [1, 84, 280] [4] [1, 220, 462, 9240, 15400] [5] [1, 455, 5005, 50050, 210210, 1401400, 1401400] [6] [1, 816, 18564, 185640, 24310, 4084080, 13613600, 2858856, 85765680, 285885600, 190590400]
Crossrefs
Programs
Formula
Row of lengths are in A000041.
A327004 Irregular triangle read by rows in which the n-th row lists multinomials for partitions of 4n which have only parts which are multiples of 4, in Hindenburg order.
1, 1, 1, 35, 1, 495, 5775, 1, 1820, 6435, 450450, 2627625, 1, 4845, 125970, 4408950, 31177575, 727476750, 2546168625, 1, 10626, 735471, 25741485, 1352078, 1338557220, 15616500900, 1577585295, 165646455975, 1932541986375, 4509264634875
Offset: 0
Comments
The Hindenburg order refers to the partition generating algorithm of C. F. Hindenburg (1779). [Knuth 7.2.1.4H]
Examples
The irregular triangle starts: [0] [1] [1] [1] [2] [1, 35] [3] [1, 495, 5775] [4] [1, 1820, 6435, 450450, 2627625] [5] [1, 4845, 125970, 4408950, 31177575, 727476750, 2546168625] [6] [1, 10626, 735471, 25741485, 1352078, 1338557220, 15616500900, 1577585295, 165646455975, 1932541986375, 4509264634875]
Crossrefs
Programs
Formula
Row of lengths are in A000041.
Comments