Search: seq:1,0,1,0,1,1,0,2,2,1
|
| |
|
|
A084938
|
|
Triangle read by rows: T(n,k) = Sum_{j>=0} j!*T(n-j-1, k-1) for n >= 0, k >= 0.
|
|
+30
638
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 6, 5, 3, 1, 0, 24, 16, 9, 4, 1, 0, 120, 64, 31, 14, 5, 1, 0, 720, 312, 126, 52, 20, 6, 1, 0, 5040, 1812, 606, 217, 80, 27, 7, 1, 0, 40320, 12288, 3428, 1040, 345, 116, 35, 8, 1, 0, 362880, 95616, 22572, 5768, 1661, 519, 161, 44, 9, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
COMMENTS
|
Triangle T(n,k) is [0,1,1,2,2,3,3,4,4,...] DELTA [1,0,0,0,0,0,...] = A110654 DELTA A000007.
In general, the triangle [r_0,r_1,r_2,r_3,...] DELTA [s_0,s_1,s_2,s_3,...] has generating function 1/(1-(r_0*x+s_0*x*y)/(1-(r_1*x+s_1*x*y)/(1-(r_2*x+s_2*x*y)/(1-(r_3*x+s_3*x*y)/(1-...(continued fraction). See also the Formula section below.
T(n,k) = number of permutations on [n] that (i) contain a 132 pattern only as part of a 4132 pattern and (ii) start with n+1-k. For example, for n >= 1, T(n,1) = (n-1)! counts all (n-1)! permutations on [n] that start with n: either they avoid 132 altogether or the initial entry serves as the "4" in a 4132 pattern and T(4,3) = 3 counts 2134, 2314, 2341. - David Callan, Jul 20 2005
T(n,k) is the number of permutations on [n] that (i) contain a (scattered) 342 pattern only as part of a 1342 pattern and (ii) contain 1 in position k. For example, T(4,3) counts 3214, 4213, 4312. (It does not count, say, 2314 because 231 forms an offending 342 pattern.) - David Callan, Jul 20 2005
Riordan array (1,x*g(x)) where g(x) is the g.f. of the factorials (n!). - Paul Barry, Sep 25 2008
Modulo 2, this sequence becomes A106344.
T(n,k) is the number of permutations of {1,2,...,n} having k cycles such that the elements of each cycle of the permutation form an interval. - Ran Pan, Nov 11 2016
The convolution triangle of the factorial numbers. - Peter Luschny, Oct 09 2022
|
|
|
LINKS
|
|
|
|
FORMULA
|
The operator DELTA takes two sequences r = (r_0, r_1, ...), s = (s_0, s_1, ...) and produces a triangle T(n, k), 0 <= k <= n, as follows:
Let q(k) = x*r_k + y*s_k for k >= 0; let P(n, k) (n >= 0, k >= -1) be defined recursively by P(0, k) = 1 for k >= 0; P(n, -1) = 0 for n >= 1; P(n, k) = P(n, k-1) + q(k)*P(n-1, k+1) for n >= 1, k >= 0. Then P(n, k) is a homogeneous polynomial in x and y of degree n and T(n, k) = coefficient of x^(n-k)*y^k in P(n, 0).
T(n, n) = 1.
T(m+n, m) = Sum_{k=0..n} A090238(n, k)*binomial(m, k).
G.f. for column k: Sum_{n>=0} T(k+n, k)*x^n = (Sum_{n>=0} n!*x^n )^k.
For k>0, T(n+k, k) = Sum_{a_1 + a_2 + .. + a_k = n} (a_1)!*(a_2)!*..*(a_k)!; a_i>=0, n>=0.
T(n,k) = Sum_{j>=0} A075834(j)*T(n-1,k+j-1).
Sum_{k=0..n} (-1)^k*T(n, k) = [n=0] - A052186(n-1)*[n>0]. (End)
|
|
|
EXAMPLE
|
Triangle [0,1,1,2,2,3,3,4,4,5,5,...] DELTA [1,0,0,0,0,...] begins
1;
0, 1;
0, 1, 1;
0, 2, 2, 1;
0, 6, 5, 3, 1;
0, 24, 16, 9, 4, 1;
0, 120, 64, 31, 14, 5, 1;
0, 720, 312, 126, 52, 20, 6, 1;
0, 5040, 1812, 606, 217, 80, 27, 7, 1;
0, 40320, 12288, 3428, 1040, 345, 116, 35, 8, 1;
0, 362880, 95616, 22572, 5768, 1661, 519, 161, 44, 9, 1. (End)
The production matrix is
0, 1;
0, 1, 1;
0, 1, 1, 1;
0, 2, 1, 1, 1;
0, 7, 2, 1, 1, 1;
0, 34, 7, 2, 1, 1, 1;
0, 206, 34, 7, 2, 1, 1, 1;
|
|
|
MAPLE
|
DELTA := proc(r, s, n) local T, x, y, q, P, i, j, k, t1; T := array(0..n, 0..n);
for i from 0 to n do q[i] := x*r[i+1]+y*s[i+1]; od: for k from 0 to n do P[0, k] := 1; od: for i from 0 to n do P[i, -1] := 0; od:
for i from 1 to n do for k from 0 to n do P[i, k] := sort(expand(P[i, k-1] + q[k]*P[i-1, k+1])); od: od:
for i from 0 to n do t1 := P[i, 0]; for j from 0 to i do T[i, j] := coeff(coeff(t1, x, i-j), y, j); od: lprint( seq(T[i, j], j=0..i) ); od: end;
# To produce the current triangle: s3 := n->floor((n+1)/2); s4 := n->if n = 0 then 1 else 0; fi; r := [seq(s3(i), i= 0..40)]; s := [seq(s4(i), i=0..40)]; DELTA(r, s, 20);
# Uses function PMatrix from A357368.
|
|
|
MATHEMATICA
|
a[0, 0] = 1; a[n_, k_] := a[n, k] = Sum[j! a[n - j - 1, k - 1], {j, 0, n - 1}]; Flatten[Table[a[i, j], {i, 0, 10}, {j, 0, i}]] (* T. D. Noe, Feb 22 2012 *)
DELTA[r_, s_, m_] := Module[{p, q, t, x, y}, q[k_] := x*r[[k+1]] + y*s[[k+1]]; p[0, _] = 1; p[_, -1] = 0; p[n_ /; n >= 1, k_ /; k >= 0] := p[n, k] = p[n, k-1] + q[k]*p[n-1, k+1] // Expand; t[n_, k_] := Coefficient[p[n, 0], x^(n-k)*y^k]; t[0, 0] = p[0, 0]; Table[t[n, k], {n, 0, m}, {k, 0, n}]]; DELTA[Floor[Range[10]/2], Prepend[Table[0, {10}], 1], 10] (* Jean-François Alcover, Sep 12 2013, after Philippe Deléham *)
|
|
|
PROG
|
(Sage)
def delehamdelta(R, S) :
L = min(len(R), len(S)) + 1
ring = PolynomialRing(ZZ, 'x')
x = ring.gen()
A = [Rk + x*Sk for Rk, Sk in zip(R, S)]
C = [ring(0)] + [ring(1) for i in range(L)]
for k in (1..L) :
for n in range(k-1, 0, -1) :
C[n] = C[n-1] + C[n+1]*A[n-1]
yield list(C[1])
for row in delehamdelta([(i+1)//2 for i in (0..n)], [0^i for i in (0..n)]):
print(row)
(Magma)
if k lt 0 or k gt n then return 0;
elif n eq 0 or k eq n then return 1;
elif k eq 0 then return 0;
else return (&+[Factorial(j)*T(n-j-1, k-1): j in [0..n-1]]);
end if; return T;
end function;
[T(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Nov 10 2022
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
Philippe Deléham, Jul 16 2003; corrections Dec 17 2008, Dec 20 2008, Feb 05 2009
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A106566
|
|
Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, 1, 1, 1, 1, 1, 1, 1, ... ] DELTA [1, 0, 0, 0, 0, 0, 0, 0, ... ] where DELTA is the operator defined in A084938.
|
|
+30
59
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 5, 5, 3, 1, 0, 14, 14, 9, 4, 1, 0, 42, 42, 28, 14, 5, 1, 0, 132, 132, 90, 48, 20, 6, 1, 0, 429, 429, 297, 165, 75, 27, 7, 1, 0, 1430, 1430, 1001, 572, 275, 110, 35, 8, 1, 0, 4862, 4862, 3432, 2002, 1001, 429, 154, 44, 9, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
COMMENTS
|
Catalan convolution triangle; g.f. for column k: (x*c(x))^k with c(x) g.f. for A000108 (Catalan numbers).
Riordan array (1, xc(x)), where c(x) the g.f. of A000108; inverse of Riordan array (1, x*(1-x)) (see A109466).
|
|
|
LINKS
|
L. W. Shapiro, S. Getu, W.-J. Woan and L. C. Woodson, The Riordan group, Discrete Applied Math., 34 (1991), 229-239.
|
|
|
FORMULA
|
T(n, k) = binomial(2n-k-1, n-k)*k/n for 0 <= k <= n with n > 0; T(0, 0) = 1; T(0, k) = 0 if k > 0.
T(0, 0) = 1; T(n, 0) = 0 if n > 0; T(0, k) = 0 if k > 0; for k > 0 and n > 0: T(n, k) = Sum_{j>=0} T(n-1, k-1+j).
Sum_{j>=0} T(n+j, 2j) = binomial(2n-1, n), n > 0.
Sum_{j>=0} T(n+j, 2j+1) = binomial(2n-2, n-1), n > 0.
Sum_{k>=0} (-1)^(n+k)*T(n, k) = A064310(n). T(n, k) = (-1)^(n+k)*A099039(n, k).
Sum_k=0..n} T(n, k)*x^k = A000007(n), A000108(n), A000984(n), A007854(n), A076035(n), A076036(n), A127628(n), A126694(n), A115970(n) for x = 0,1,2,3,4,5,6,7,8 respectively.
Sum_{k>=0} T(n, k)*x^(n-k) = C(x, n); C(x, n) are the generalized Catalan numbers.
Sum_{j=0..n-k} T(n+k,2*k+j) = A039599(n,k).
Sum_{j>=0} T(n,j)*binomial(j,k) = A039599(n,k).
Sum_{k=0..n} T(n,k)*(x+1)^k*x^(n-k) = A000012(n), A000984(n), A089022(n), A035610(n), A130976(n), A130977(n), A130978(n), A130979(n), A130980(n), A131521(n) for x= 0,1,2,3,4,5,6,7,8,9 respectively. - Philippe Deléham, Aug 25 2007
Sum_{k=0..n} T(n,k)*(-x)^k = A000007(n), A126983(n), A126984(n), A126982(n), A126986(n), A126987(n), A127017(n), A127016(n), A126985(n), A127053(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively. - Philippe Deléham, Oct 27 2007
G.f.: Sum_{n>=0, k>=0} T(n, k)*x^k*z^n = 1/(1 - x*z*c(z)) where c(z) the g.f. of A000108. - Michael Somos, Oct 01 2022
|
|
|
EXAMPLE
|
Triangle begins:
1;
0, 1;
0, 1, 1;
0, 2, 2, 1;
0, 5, 5, 3, 1;
0, 14, 14, 9, 4, 1;
0, 42, 42, 28, 14, 5, 1;
0, 132, 132, 90, 48, 20, 6, 1;
Production array is
0, 1,
0, 1, 1,
0, 1, 1, 1,
0, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1, 1, 1, 1, 1 (End)
|
|
|
MAPLE
|
if n = 0 then
1;
elif k < 0 or k > n then
0;
else
binomial(2*n-k-1, n-k)*k/n ;
end if;
|
|
|
MATHEMATICA
|
T[n_, k_] := Binomial[2n-k-1, n-k]*k/n; T[0, 0] = 1; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 18 2017 *)
(* The function RiordanArray is defined in A256893. *)
|
|
|
PROG
|
(Magma)
A106566:= func< n, k | n eq 0 select 1 else (k/n)*Binomial(2*n-k-1, n-k) >;
(Sage)
def A106566(n, k): return 1 if (n==0) else (k/n)*binomial(2*n-k-1, n-k)
(PARI) {T(n, k) = if( k<=0 || k>n, n==0 && k==0, binomial(2*n - k, n) * k/(2*n - k))}; /* Michael Somos, Oct 01 2022 */
|
|
|
CROSSREFS
|
Column k for k = 0, 1, 2, ..., 13: A000007, A000108, A000108, A000245, A002057, A000344, A003517, A000588, A003517, A001392, A003518, A000589, A003519, A000590
Generalized Catalan numbers C(x, n) for -11 <= x <= 10: A064333, A064332, A064331, A064330, A064329, A064328, A064327, A064326, A064325, A064311, A064310, A000012, A000108, A064062, A064063, A064087, A064088, A064089, A064090, A064091, A064092, A064093.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A258829
|
|
Number T(n,k) of permutations p of [n] such that the up-down signature of 0,p has nonnegative partial sums with a maximal value of k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
|
|
+30
19
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 5, 11, 3, 1, 0, 16, 38, 28, 4, 1, 0, 61, 263, 130, 62, 5, 1, 0, 272, 1260, 1263, 340, 129, 6, 1, 0, 1385, 10871, 8090, 4734, 819, 261, 7, 1, 0, 7936, 66576, 88101, 33855, 16066, 1890, 522, 8, 1, 0, 50521, 694599, 724189, 495371, 127538, 52022, 4260, 1040, 9, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
p = 1432 is counted by T(4,2) because the up-down signature of 0,p = 01432 is 1,1,-1,-1 with partial sums 1,2,1,0.
q = 4321 is not counted by any T(4,k) because the up-down signature of 0,q = 04321 is 1,-1,-1,-1 with partial sums 1,0,-1,-2.
T(4,1) = 5: 2143, 3142, 3241, 4132, 4231.
T(4,2) = 11: 1324, 1423, 1432, 2134, 2314, 2413, 2431, 3124, 3412, 3421, 4123.
T(4,3) = 3: 1243, 1342, 2341.
T(4,4) = 1: 1234.
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 2, 2, 1;
0, 5, 11, 3, 1;
0, 16, 38, 28, 4, 1;
0, 61, 263, 130, 62, 5, 1;
0, 272, 1260, 1263, 340, 129, 6, 1;
0, 1385, 10871, 8090, 4734, 819, 261, 7, 1;
|
|
|
MAPLE
|
b:= proc(u, o, c, k) option remember;
`if`(c<0 or c>k, 0, `if`(u+o=0, 1,
add(b(u-j, o-1+j, c+1, k), j=1..u)+
add(b(u+j-1, o-j, c-1, k), j=1..o)))
end:
A:= (n, k)-> b(n, 0$2, k):
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..12);
|
|
|
MATHEMATICA
|
b[u_, o_, c_, k_] := b[u, o, c, k] = If[c < 0 || c > k, 0, If[u + o == 0, 1, Sum[b[u - j, o - 1 + j, c + 1, k], {j, 1, u}] + Sum[b[u + j - 1, o - j, c - 1, k], {j, 1, o}]]];
A[n_, k_] := b[n, 0, 0, k];
T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k - 1]];
|
|
|
CROSSREFS
|
Columns k=0-10 give: A000007, A000111 for n>0, A259213, A316390, A316391, A316392, A316393, A316394, A316395, A316396, A316397.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A189233
|
|
Square array A(n,k), n >= 0, k >= 0, read by antidiagonals upwards, where the e.g.f. of column k is exp(k*(e^x-1)).
|
|
+30
16
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 5, 6, 3, 1, 0, 15, 22, 12, 4, 1, 0, 52, 94, 57, 20, 5, 1, 0, 203, 454, 309, 116, 30, 6, 1, 0, 877, 2430, 1866, 756, 205, 42, 7, 1, 0, 4140, 14214, 12351, 5428, 1555, 330, 56, 8, 1, 0, 21147, 89918, 88563, 42356, 12880, 2850, 497, 72, 9, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
COMMENTS
|
A(n,k) is the n-th moment of a Poisson distribution with mean = k. - Geoffrey Critzer, Dec 23 2018
|
|
|
LINKS
|
|
|
|
FORMULA
|
E.g.f. of column k: exp(k*(e^x-1)).
|
|
|
EXAMPLE
|
Square array begins:
A000012 1, 1, 1, 1, 1, 1, 1, 1, ...
A001477 0, 1, 2, 3, 4, 5, 6, 7, ...
A002378 0, 2, 6, 12, 20, 30, 42, 56, ...
A033445 0, 5, 22, 57, 116, 205, 330, 497, ...
0, 15, 94, 309, 756, 1555, 2850, 4809, ...
0, 52, 454, 1866, 5428, 12880, 26682, 50134, ...
|
|
|
MAPLE
|
expnums := proc(k, n) option remember; local j;
`if`(n = 0, 1, (1+add(binomial(n-1, j-1)*expnums(k, n-j), j = 1..n-1))*k) end:
A189233_array := (k, n) -> expnums(k, n):
seq(print(seq(A189233_array(k, n), k = 0..7)), n = 0..5);
A189233_egf := k -> exp(k*(exp(x)-1));
T := (n, k) -> n!*coeff(series(A189233_egf(k), x, n+1), x, n):
seq(lprint(seq(T(n, k), k = 0..7)), n = 0..5):
# alternative Maple program:
A:= proc(n, k) option remember; `if`(n=0, 1,
(1+add(binomial(n-1, j-1)*A(n-j, k), j=1..n-1))*k)
end:
|
|
|
MATHEMATICA
|
max = 9; Clear[col]; col[k_] := col[k] = CoefficientList[ Series[ Exp[k*(Exp[x]-1)], {x, 0, max}], x]*Range[0, max]!; a[0, _] = 1; a[n_?Positive, 0] = 0; a[n_, k_] := col[k][[n+1]]; Table[ a[n-k, k], {n, 0, max}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 26 2013 *)
Table[Table[BellB[n, k], {k, 0, 5}], {n, 0, 5}] // Grid (* Geoffrey Critzer, Dec 23 2018 *)
|
|
|
PROG
|
(Maxima)
A(n, k):=if k=0 and n=0 then 1 else if k=0 then 0 else sum(stirling2(n, i)*k^i, i, 0, n); /* Vladimir Kruchinin, Apr 12 2019 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A155161
|
|
A Fibonacci convolution triangle: Riordan array (1, x/(1 - x - x^2)). Triangle T(n,k), 0 <= k <= n, read by rows.
|
|
+30
15
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 3, 1, 0, 5, 10, 9, 4, 1, 0, 8, 20, 22, 14, 5, 1, 0, 13, 38, 51, 40, 20, 6, 1, 0, 21, 71, 111, 105, 65, 27, 7, 1, 0, 34, 130, 233, 256, 190, 98, 35, 8, 1, 0, 55, 235, 474, 594, 511, 315, 140, 44, 9, 1, 0, 89, 420, 942, 1324, 1295, 924, 490, 192, 54, 10, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n, k) given by [0,1,1,-1,0,0,0,...] DELTA [1,0,0,0,...] where DELTA is the operator defined in A084938.
a(n,k) = Sum_{i=0..n-k} M(k,i)*binomial(i,n-i-k), where M(n,k) = n(n+1)(n+2)...(n+k-1)/k!. - Emanuele Munarini, Mar 15 2011
Recurrence: a(n+2,k+1) = a(n+1,k+1) + a(n+1,k) + a(n,k+1). - Emanuele Munarini, Mar 15 2011
Sum_{k=0..n} T(n,k)*x^k = A000007(n), A000129(n) (n > 0), A052991(n), A155179(n), A155181(n), A155195(n), A155196(n), A155197(n), A155198(n), A155199(n) for x = 0,1,2,3,4,5,6,7,8,9 respectively. - Philippe Deléham, Feb 08 2012
T(n, k) = binomial(n-1, k-1)*hypergeom([-(n-k)/2, -(n-k-1)/2], [1-n], -4). - Peter Luschny, May 23 2021
|
|
|
EXAMPLE
|
Triangle begins:
[0] 1;
[1] 0, 1;
[2] 0, 1, 1;
[3] 0, 2, 2, 1;
[4] 0, 3, 5, 3, 1;
[5] 0, 5, 10, 9, 4, 1;
[6] 0, 8, 20, 22, 14, 5, 1;
[7] 0, 13, 38, 51, 40, 20, 6, 1;
[8] 0, 21, 71, 111, 105, 65, 27, 7, 1;
[9] 0, 34, 130, 233, 256, 190, 98, 35, 8, 1.
|
|
|
MAPLE
|
T := (n, k) -> binomial(n-1, k-1)*hypergeom([-(n-k)/2, -(n-k-1)/2], [1-n], -4):
seq(seq(simplify(T(n, k)), k = 0..n), n = 0..11); # Peter Luschny, May 23 2021
# Uses function PMatrix from A357368.
PMatrix(10, n -> combinat:-fibonacci(n)); # Peter Luschny, Oct 07 2022
|
|
|
MATHEMATICA
|
CoefficientList[#, y]& /@ CoefficientList[(1-x-x^2)/(1-x-x^2-x*y)+O[x]^12, x] // Flatten (* Jean-François Alcover, Mar 01 2019 *)
(* Generates the triangle without the leading '1' (rows are rearranged). *)
(* Function RiordanSquare defined in A321620. *)
RiordanSquare[x/(1 - x - x^2), 11] // Flatten (* Peter Luschny, Feb 27 2021 *)
|
|
|
PROG
|
(Maxima) M(n, k):=pochhammer(n, k)/k!;
create_list(sum(M(k, i)*binomial(i, n-i-k), i, 0, n-k), n, 0, 8, k, 0, n); /* Emanuele Munarini, Mar 15 2011 */
(Haskell)
a155161 n k = a155161_tabl !! n !! k
a155161_row n = a155161_tabl !! n
a155161_tabl = [1] : [0, 1] : f [0] [0, 1] where
f us vs = ws : f vs ws where
ws = zipWith (+) (us ++ [0, 0]) $ zipWith (+) ([0] ++ vs) (vs ++ [0])
|
|
|
CROSSREFS
|
Central terms: T(2*n,n) = A213684(n) for n > 0.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A276543
|
|
Triangle read by rows: T(n,k) = number of primitive (period n) n-bead bracelet structures using exactly k different colored beads.
|
|
+30
15
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 2, 1, 0, 5, 13, 11, 3, 1, 0, 8, 31, 33, 16, 3, 1, 0, 14, 80, 136, 85, 27, 4, 1, 0, 21, 201, 478, 434, 171, 37, 4, 1, 0, 39, 533, 1849, 2270, 1249, 338, 54, 5, 1, 0, 62, 1401, 6845, 11530, 8389, 3056, 590, 70, 5, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,8
|
|
|
COMMENTS
|
Turning over will not create a new bracelet. Permuting the colors of the beads will not change the structure.
|
|
|
REFERENCES
|
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n, k) = Sum_{d|n} mu(n/d) * A152176(d, k).
|
|
|
EXAMPLE
|
Triangle starts:
1
0 1
0 1 1
0 2 2 1
0 3 5 2 1
0 5 13 11 3 1
0 8 31 33 16 3 1
0 14 80 136 85 27 4 1
0 21 201 478 434 171 37 4 1
0 39 533 1849 2270 1249 338 54 5 1
...
|
|
|
PROG
|
Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
R(n)={Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
T(n)={my(M=(R(n)+Ach(n))/2); Mat(vectorv(n, n, sumdiv(n, d, moebius(d)*M[n/d, ])))}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A308680
|
|
Number T(n,k) of colored integer partitions of n such that all colors from a k-set are used and parts differ by size or by color; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
|
|
+30
15
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 2, 5, 3, 1, 0, 3, 8, 9, 4, 1, 0, 4, 14, 19, 14, 5, 1, 0, 5, 22, 39, 36, 20, 6, 1, 0, 6, 34, 72, 85, 60, 27, 7, 1, 0, 8, 50, 128, 180, 160, 92, 35, 8, 1, 0, 10, 73, 216, 360, 381, 273, 133, 44, 9, 1, 0, 12, 104, 354, 680, 845, 720, 434, 184, 54, 10, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
COMMENTS
|
For fixed k > 0, T(n,k) ~ exp(Pi*sqrt(k*n/3)) * k^(1/4) / (3^(1/4) * 2^((k+3)/2) * n^(3/4)). - Vaclav Kotesovec, Sep 16 2019
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = Sum_{i=0..k} (-1)^i * binomial(k,i) * A286335(n,k-i).
Sum_{k=1..n} k * T(n,k) = A325915(n).
G.f. of column k: (-1 + Product_{j>=1} (1 + x^j))^k. - Alois P. Heinz, Jan 29 2021
|
|
|
EXAMPLE
|
T(4,1) = 2: 3a1a, 4a.
T(4,2) = 5: 2a1a1b, 2b1a1b, 2a2b, 3a1b, 3b1a.
T(4,3) = 3: 2a1b1c, 2b1a1c, 2c1a1b.
T(4,4) = 1: 1a1b1c1d.
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 2, 2, 1;
0, 2, 5, 3, 1;
0, 3, 8, 9, 4, 1;
0, 4, 14, 19, 14, 5, 1;
0, 5, 22, 39, 36, 20, 6, 1;
0, 6, 34, 72, 85, 60, 27, 7, 1;
0, 8, 50, 128, 180, 160, 92, 35, 8, 1;
0, 10, 73, 216, 360, 381, 273, 133, 44, 9, 1;
...
|
|
|
MAPLE
|
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add((t->
b(t, min(t, i-1), k)*binomial(k, j))(n-i*j), j=0..min(k, n/i))))
end:
T:= (n, k)-> add(b(n$2, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..12);
# second Maple program:
b:= proc(n) option remember; `if`(n=0, 1, add(b(n-j)*add(
`if`(d::odd, d, 0), d=numtheory[divisors](j)), j=1..n)/n)
end:
T:= proc(n, k) option remember;
`if`(k=0, `if`(n=0, 1, 0), `if`(k=1, `if`(n=0, 0, b(n)),
(q-> add(T(j, q)*T(n-j, k-q), j=0..n))(iquo(k, 2))))
end:
# Uses function PMatrix from A357368.
|
|
|
MATHEMATICA
|
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Function[t, b[t, Min[t, i - 1], k]*Binomial[k, j]][n - i*j], {j, 0, Min[k, n/i]}]]];
T[n_, k_] := Sum[b[n, n, k - i]*(-1)^i*Binomial[k, i], {i, 0, k}];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 06 2019, from Maple *)
|
|
|
CROSSREFS
|
Columns k=0-10 give: A000007, A000009 (for n>0), A327380, A327381, A327382, A327383, A327384, A327385, A327386, A327387, A327388.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A107424
|
|
Triangle read by rows: T(n, k) is the number of primitive (period n) n-bead necklace structures with k different colors. Only includes structures that contain all k colors.
|
|
+30
12
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 2, 1, 0, 5, 17, 13, 3, 1, 0, 9, 43, 50, 20, 3, 1, 0, 16, 124, 220, 136, 36, 4, 1, 0, 28, 338, 866, 773, 296, 52, 4, 1, 0, 51, 941, 3435, 4280, 2303, 596, 78, 5, 1, 0, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105, 5, 1, 0, 170, 7234, 51061
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,8
|
|
|
COMMENTS
|
This classification is concerned with which beads are the same color, not with the colors themselves, so bbabcd is the same structure as aabacd. Cyclic permutations are also the same structure, e.g. abacda is also the same structure. However, order matters: the reverse of aabacd is equivalent to aabcad, which is also on the list.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
T(6, 4) = 13: {aaabcd, aabacd, aabcad, abacad, aabbcd, aabcbd, aabcdb, aacbbd, aacbdb, ababcd, abacbd, acabdb, abcabd}.
Triangle starts:
1
0 1
0 1 1
0 2 2 1
0 3 5 2 1
0 5 17 13 3 1
0 9 43 50 20 3 1
0 16 124 220 136 36 4 1
0 28 338 866 773 296 52 4 1
0 51 941 3435 4280 2303 596 78 5 1
(End)
|
|
|
MATHEMATICA
|
A[d_, n_] := A[d, n] = Which[n == 0, 1, n == 1, DivisorSum[d, x^# &], d == 1, Sum[StirlingS2[n, k] x^k, {k, 0, n}], True, Expand[A[d, 1] A[d, n-1] + D[A[d, n-1], x] x]];
B[n_, k_] := Coefficient[DivisorSum[n, EulerPhi[#] A[#, n/#]&]/n/x, x, k];
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] B[#, k]&];
|
|
|
PROG
|
(PARI) \\ here R(n) is A152175 as square matrix.
R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
T(n) = {my(M=R(n)); matrix(n, n, i, k, sumdiv(i, d, moebius(i/d)*M[d, k]))}
{ my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Jan 09 2020
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A292086
|
|
Number T(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that k is the maximum of 1 and the node outdegrees; triangle T(n,k), n>=1, 1<=k<=n, read by rows.
|
|
+30
12
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 6, 2, 1, 0, 6, 17, 7, 2, 1, 0, 11, 47, 22, 7, 2, 1, 0, 23, 133, 72, 23, 7, 2, 1, 0, 46, 380, 230, 77, 23, 7, 2, 1, 0, 98, 1096, 751, 256, 78, 23, 7, 2, 1, 0, 207, 3186, 2442, 861, 261, 78, 23, 7, 2, 1, 0, 451, 9351, 8006, 2897, 887, 262, 78, 23, 7, 2, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,8
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
: T(4,2) = 2 : T(4,3) = 2 : T(4,4) = 1 :
: : : :
: o o : o o : o :
: / \ / \ : / \ /|\ : /( )\ :
: o N o o : o N o N N : N N N N :
: / \ ( ) ( ) : /|\ ( ) : :
: o N N N N N : N N N N N : :
: ( ) : : :
: N N : : :
: : : :
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 2, 2, 1;
0, 3, 6, 2, 1;
0, 6, 17, 7, 2, 1;
0, 11, 47, 22, 7, 2, 1;
0, 23, 133, 72, 23, 7, 2, 1;
0, 46, 380, 230, 77, 23, 7, 2, 1;
...
|
|
|
MAPLE
|
b:= proc(n, i, v, k) option remember; `if`(n=0,
`if`(v=0, 1, 0), `if`(i<1 or v<1 or n<v, 0,
`if`(v=n, 1, add(binomial(A(i, k)+j-1, j)*
b(n-i*j, i-1, v-j, k), j=0..min(n/i, v)))))
end:
A:= proc(n, k) option remember; `if`(n<2, n,
add(b(n, n+1-j, j, k), j=2..min(n, k)))
end:
T:= (n, k)-> A(n, k)-`if`(k=1, 0, A(n, k-1)):
seq(seq(T(n, k), k=1..n), n=1..15);
|
|
|
MATHEMATICA
|
b[n_, i_, v_, k_] := b[n, i, v, k] = If[n == 0, If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0, If[v == n, 1, Sum[Binomial[A[i, k] + j - 1, j]*b[n - i*j, i - 1, v - j, k], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n < 2, n, Sum[b[n, n + 1 - j, j, k], {j, 2, Min[n, k]}]];
T[n_, k_] := A[n, k] - If[k == 1, 0, A[n, k - 1]];
|
|
|
CROSSREFS
|
Limit of reversed rows gives A292087.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A093729
|
|
Square table T, read by antidiagonals, where T(n,k) gives the number of n-th generation descendents of a node labeled (k) in the tree of tournament sequences.
|
|
+30
10
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 7, 7, 3, 1, 0, 41, 41, 15, 4, 1, 0, 397, 397, 123, 26, 5, 1, 0, 6377, 6377, 1656, 274, 40, 6, 1, 0, 171886, 171886, 36987, 4721, 515, 57, 7, 1, 0, 7892642, 7892642, 1391106, 134899, 10810, 867, 77, 8, 1, 0, 627340987, 627340987, 89574978, 6501536, 376175, 21456, 1351, 100, 9, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
COMMENTS
|
Column 1, of array T and antidiagonals, equals A008934, which is the number of tournament sequences.
A tournament sequence is an increasing sequence of positive integers (t_1,t_2,...) such that t_1 = 1 and t_{i+1} <= 2*t_i, where integer k>1.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(0, k)=1 for k>=0, T(n, 0)=0 for n>=1; else T(n, k) = T(n, k-1) - T(n-1, k) + T(n-1, 2*k-1) + T(n-1, 2*k) for k<=n; else T(n, k) = Sum_{j=1..n+1} (-1)^(j-1)*C(n+1, j)*T(n, k-j) for k>n (Cook-Kleber).
Column k of T equals column 0 of the matrix k-th power of triangle A097710, which satisfies the matrix recurrence: A097710(n, k) = [A097710^2](n-1, k-1) + [A097710^2](n-1, k) for n>k>=0.
Sum_{k=0..n} T(n-k, k) = A093730(n) (antidiagonal row sums).
|
|
|
EXAMPLE
|
Array begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, ...],
0, 1, 2, 3, 4, 5, 6, 7, 8, ...],
0, 2, 7, 15, 26, 40, 57, 77, 100, ...],
0, 7, 41, 123, 274, 515, 867, 1351, 1988, ...],
0, 41, 397, 1656, 4721, 10810, 21456, 38507, 64126, ...],
0, 397, 6377, 36987, 134899, 376175, 880032, .................],
0, 6377, 171886, 1391106, 6501536, ...],
0, 171886, 7892642, .....................];
Antidiagonals begin as:
1;
0, 1;
0, 1, 1;
0, 2, 2, 1;
0, 7, 7, 3, 1;
0, 41, 41, 15, 4, 1;
0, 397, 397, 123, 26, 5, 1;
0, 6377, 6377, 1656, 274, 40, 6, 1;
0, 171886, 171886, 36987, 4721, 515, 57, 7, 1;
|
|
|
MATHEMATICA
|
t[n_?Negative, _] = 0; t[0, _] = 1; t[n_, k_] /; k <= n := t[n, k] = t[n, k - 1] - t[n-1, k] + t[n - 1, 2 k - 1] + t[n - 1, 2 k]; t[n_, k_] := t[n, k] = Sum[(-1)^(j - 1)*Binomial[n + 1, j]*t[n, k - j], {j, 1, n + 1}]; Flatten[Table[t[i - k, k - 1], {i, 10}, {k, i}]] (* Jean-François Alcover, May 31 2011, after PARI prog. *)
|
|
|
PROG
|
(PARI) {T(n, k)=if(n<0, 0, if(n==0, 1, if(k==0, 0, if(k<=n, T(n, k-1)-T(n-1, k)+T(n-1, 2*k-1)+T(n-1, 2*k), sum(j=1, n+1, (-1)^(j-1)*binomial(n+1, j)*T(n, k-j))))))}
(PARI) {a(n, m) = my(A=1); for(k=1, n, A = (A - q^k * r * subst( subst(A, q, q^2), r, r^2)) / (1-q); subst(subst(A, r, q^(m-1)), q, 1)}; /* Michael Somos, Jun 19 2017 */
(SageMath)
@CachedFunction
def T(n, k):
if n<0: return 0
elif n==0: return 1
elif k==0: return 0
elif k<n+1: return T(n, k-1) - T(n-1, k) + T(n-1, 2*k-1) + T(n-1, 2*k)
else: return sum((-1)^(j-1)*binomial(n+1, j)*T(n, k-j) for j in range(1, n+2))
def A093729(n, k): return T(n-k, k)
|
|
|
CROSSREFS
|
Cf. A008934 (column k=1 of array and antidiagonals), A093730 (antidiagonal row sums).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.014 seconds
|
