A047999 Sierpiński's [Sierpinski's] triangle (or gasket): triangle, read by rows, formed by reading Pascal's triangle (A007318) mod 2.
1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1
Offset: 0
Examples
Triangle begins:
1,
1,1,
1,0,1,
1,1,1,1,
1,0,0,0,1,
1,1,0,0,1,1,
1,0,1,0,1,0,1,
1,1,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,1,
1,1,0,0,0,0,0,0,1,1,
1,0,1,0,0,0,0,0,1,0,1,
1,1,1,1,0,0,0,0,1,1,1,1,
1,0,0,0,1,0,0,0,1,0,0,0,1,
...
References
- Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
- Brand, Neal; Das, Sajal; Jacob, Tom. The number of nonzero entries in recursively defined tables modulo primes. Proceedings of the Twenty-first Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1990). Congr. Numer. 78 (1990), 47--59. MR1140469 (92h:05004).
- John W. Milnor and James D. Stasheff, Characteristic Classes, Princeton University Press, 1974, pp. 43-49 (sequence appears on p. 46).
- H.-O. Peitgen, H. Juergens and D. Saupe: Chaos and Fractals (Springer-Verlag 1992), p. 408.
- Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
- S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.
Links
- N. J. A. Sloane, Table of n, a(n) for n = 0..10584 [First 144 rows, flattened; first 50 rows from T. D. Noe].
- J.-P. Allouche and V. Berthe, Triangle de Pascal, complexité et automates, Bulletin of the Belgian Mathematical Society Simon Stevin 4.1 (1997): 1-24.
- J.-P. Allouche, F. v. Haeseler, H.-O. Peitgen and G. Skordev, Linear cellular automata, finite automata and Pascal's triangle, Discrete Appl. Math. 66 (1996), 1-22.
- David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.],
- J. Baer, Explore patterns in Pascal's Triangle
- Valentin Bakoev, Fast Bitwise Implementation of the Algebraic Normal Form Transform, Serdica J. of Computing 11 (2017), No 1, 45-57.
- Valentin Bakoev, Properties and links concerning M_n
- Thomas Baruchel, Flattening Karatsuba's Recursion Tree into a Single Summation, SN Computer Science (2020) Vol. 1, Article No. 48.
- Thomas Baruchel, A non-symmetric divide-and-conquer recursive formula for the convolution of polynomials and power series, arXiv:1912.00452 [math.NT], 2019.
- A. Bogomolny, Dot Patterns and Sierpinski Gasket
- Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids, English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see pp. 130-132.
- Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, 2014.
- E. Burlachenko, Fractal generalized Pascal matrices, arXiv:1612.00970 [math.NT], 2016. See p. 9.
- S. Butkevich, Pascal Triangle Applet
- David Callan, Sierpinski's triangle and the Prouhet-Thue-Morse word, arXiv:math/0610932 [math.CO], 2006.
- B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part I
- B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part II
- C. Cobeli, A. Zaharescu, A game with divisors and absolute differences of exponents, arXiv:1411.1334 [math.NT], 2014; Journal of Difference Equations and Applications, Vol. 20, #11, 2014.
- Ilya Gutkovskiy, Illustrations (triangle formed by reading Pascal's triangle mod m)
- R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.
- Brady Haran, Chaos Game, Numberphile video, YouTube (April 27, 2017).
- I. Kobayashi et al., Pascal's Triangle
- Dr. Math, Regular polygon formulas [Broken link?]
- Y. Moshe, The distribution of elements in automatic double sequences, Discr. Math., 297 (2005), 91-103.
- National Curve Bank, Sierpinski Triangles
- Hieu D. Nguyen, A Digital Binomial Theorem, arXiv:1412.3181 [math.NT], 2014.
- S. Northshield, Sums across Pascal's triangle modulo 2, Congressus Numerantium, 200, pp. 35-52, 2010.
- A. M. Reiter, Determining the dimension of fractals generated by Pascal's triangle, Fibonacci Quarterly, 31(2), 1993, pp. 112-120.
- F. Richman, Javascript for computing Pascal's triangle modulo n. Go to this page, then under "Modern Algebra and Other Things", click "Pascal's triangle modulo n".
- Vladimir Shevelev, On Stephan's conjectures concerning Pascal triangle modulo 2 and their polynomial generalization, J. of Algebra Number Theory: Advances and Appl., 7 (2012), no.1, 11-29. Also arXiv:1011.6083, 2010.
- N. J. A. Sloane, Illustration of rows 0 to 32 (encoignure style)
- N. J. A. Sloane, Illustration of rows 0 to 64 (encoignure style)
- N. J. A. Sloane, Illustration of rows 0 to 128 (encoignure style)
- N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
- Eric Weisstein's World of Mathematics, Sierpiński Sieve, Rule 60, Rule 102
- Index entries for sequences related to cellular automata
- Index entries for triangles and arrays related to Pascal's triangle
- Index entries for sequences generated by sieves
Crossrefs
Sequences based on the triangles formed by reading Pascal's triangle mod m: (this sequence) (m = 2), A083093 (m = 3), A034931 (m = 4), A095140 (m = 5), A095141 (m = 6), A095142 (m = 7), A034930(m = 8), A095143 (m = 9), A008975 (m = 10), A095144 (m = 11), A095145 (m = 12), A275198 (m = 14), A034932 (m = 16).
Cf. A007318, A054431, A001317, A008292, A083093, A034931, A034930, A008975, A034932, A166360, A249133, A064194, A227133.
From Johannes W. Meijer, Jun 05 2011: (Start)
A106344 is a skew version of this triangle.
Programs
-
Haskell
import Data.Bits (xor) a047999 :: Int -> Int -> Int a047999 n k = a047999_tabl !! n !! k a047999_row n = a047999_tabl !! n a047999_tabl = iterate (\row -> zipWith xor ([0] ++ row) (row ++ [0])) [1] -- Reinhard Zumkeller, Dec 11 2011, Oct 24 2010
-
Magma
A047999:= func< n,k | BitwiseAnd(n-k, k) eq 0 select 1 else 0 >; [A047999(n,k): k in [0..n], n in [0..15]]; // G. C. Greubel, Dec 03 2024
-
Maple
# Maple code for first M rows (here M=10) - N. J. A. Sloane, Feb 03 2016 ST:=[1,1,1]; a:=1; b:=2; M:=10; for n from 2 to M do ST:=[op(ST),1]; for i from a to b-1 do ST:=[op(ST), (ST[i+1]+ST[i+2]) mod 2 ]; od: ST:=[op(ST),1]; a:=a+n; b:=a+n; od: ST; # N. J. A. Sloane # alternative A047999 := proc(n,k) modp(binomial(n,k),2) ; end proc: seq(seq(A047999(n,k),k=0..n),n=0..12) ; # R. J. Mathar, May 06 2016
-
Mathematica
Mod[ Flatten[ NestList[ Prepend[ #, 0] + Append[ #, 0] &, {1}, 13]], 2] (* Robert G. Wilson v, May 26 2004 *) rows = 14; ca = CellularAutomaton[60, {{1}, 0}, rows-1]; Flatten[ Table[ca[[k, 1 ;; k]], {k, 1, rows}]] (* Jean-François Alcover, May 24 2012 *) Mod[#,2]&/@Flatten[Table[Binomial[n,k],{n,0,20},{k,0,n}]] (* Harvey P. Dale, Jun 26 2019 *) A047999[n_,k_]:= Boole[BitAnd[n-k,k]==0]; Table[A047999[n,k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Sep 03 2025 *) -
PARI
\\ Recurrence for Pascal's triangle mod p, here p = 2. p = 2; s=13; T=matrix(s,s); T[1,1]=1; for(n=2,s, T[n,1]=1; for(k=2,n, T[n,k] = (T[n-1,k-1] + T[n-1,k])%p )); for(n=1,s,for(k=1,n,print1(T[n,k],", "))) \\ Gerald McGarvey, Oct 10 2009
-
PARI
A011371(n)=my(s);while(n>>=1,s+=n);s T(n,k)=A011371(n)==A011371(k)+A011371(n-k) \\ Charles R Greathouse IV, Aug 09 2013
-
PARI
T(n,k)=bitand(n-k,k)==0 \\ Charles R Greathouse IV, Aug 11 2016
-
Python
def A047999_T(n,k): return int(not ~n & k) # Chai Wah Wu, Feb 09 2016
Formula
Lucas's Theorem is that T(n,k) = 1 if and only if the 1's in the binary expansion of k are a subset of the 1's in the binary expansion of n; or equivalently, k AND NOT n is zero, where AND and NOT are bitwise operators. - Chai Wah Wu, Feb 09 2016 and N. J. A. Sloane, Feb 10 2016
T(n,k) = T(n-1,k-1) XOR T(n-1,k), 0 < k < n; T(n,0) = T(n,n) = 1. - Reinhard Zumkeller, Dec 13 2009
T(n,k) = (T(n-1,k-1) + T(n-1,k)) mod 2 = |T(n-1,k-1) - T(n-1,k)|, 0 < k < n; T(n,0) = T(n,n) = 1. - Rick L. Shepherd, Feb 23 2018
From Vladimir Shevelev, Dec 31 2013: (Start)
For polynomial {s_n(x)} we have
s_0(x)=1; for n>=1, s_n(x) = Product_{i=1..A000120(n)} (x^(2^k_i) + 1),
if the binary expansion of n is n = Sum_{i=1..A000120(n)} 2^k_i;
G.f. Sum_{n>=0} s_n(x)*z^n = Product_{k>=0} (1 + (x^(2^k)+1)*z^(2^k)) (0
Let x>1, t>0 be real numbers. Then
Sum_{n>=0} 1/s_n(x)^t = Product_{k>=0} (1 + 1/(x^(2^k)+1)^t);
Sum_{n>=0} (-1)^A000120(n)/s_n(x)^t = Product_{k>=0} (1 - 1/(x^(2^k)+1)^t).
In particular, for t=1, x>1, we have
Sum_{n>=0} (-1)^A000120(n)/s_n(x) = 1 - 1/x. (End)
From Valentin Bakoev, Jul 11 2020: (Start)
(See my comment about the matrix M_n.) Denote by T(i,j) the number in the i-th row and j-th column of M_n (0 <= i, j < 2^n). When i>=j, T(i,j) is the j-th number in the i-th row of the Sierpinski's triangle. For given i and j, we denote by k the largest integer of the type k=2^m and k
T(i,0) = T(i,i) = 1, or
T(i,j) = 0 if i < j, or
T(i,j) = T(i-k,j), if j < k, or
T(i,j) = T(i-k,j-k), if j >= k.
Thus, for given i and j, T(i,j) can be computed in O(log_2(i)) steps. (End)
Extensions
Additional links from Lekraj Beedassy, Jan 22 2004
A074664 Number of algebraically independent elements of degree n in the algebra of symmetric polynomials in noncommuting variables.
1, 1, 2, 6, 22, 92, 426, 2146, 11624, 67146, 411142, 2656052, 18035178, 128318314, 954086192, 7396278762, 59659032142, 499778527628, 4341025729290, 39035256389026, 362878164902216, 3482882959111530, 34472032118214598
Offset: 1
Comments
Also the number of irreducible set partitions of size n (see A055105) {1}; {1,2}; {1,2,3}, {1,23}; ...; and also the number of set partitions of n which do not have a proper subset of parts with a union equal to a subset {1,2,...,j} with j < n (atomic set partitions, see A087903) {1}; {12}; {13,2}, {123}; ...
Also the number of non-nesting permutations on n elements (see He et al.). - Chad Brewbaker, Apr 11 2010
The Chen-Li-Wang link presents a bijection from indecomposable (= atomic) partitions to irreducible partitions. - David Callan, May 13 2014
From David Callan, Jul 21 2017: (Start)
The "non-nesting" permutations in Definition 2.2 of the He et al. reference seem to be the permutations whose inverses avoid all four of the patterns 14-23, 23-14, 32-41, and 41-32 (no nested ascents or descents), counted by 1, 2, 6, 20, 68, 240, 848, 3048, ... .
a(n) is the number of permutations of [n-1] with no nested descents, that is, permutations of [n-1] that avoid both of the dashed patterns 32-41 and 41-32. For example, for p = 823751694, the descents 82 and 75 are nested, as are the descents 75 and 94, but 82 and 94 are not because neither of the intervals [2,8] and [4,9] is contained in the other. Since 82 and 75 are nested, 8275 is a 41-32 pattern in p. (End)
Examples
G.f. = x + x^2 + 2*x^3 + 6*x^4 + 22*x^5 + 92*x^6 + 426*x^7 + 2146*x^8 + ...
m{1} = x1 + x2 + x3 + ..., so a(1) = 1.
m{1,2} = x1 x2 + x2 x1 + x2 x3 + x3 x2 + x1 x3 + ..., m{12} = x1 x1 + x2 x2 + x3 x3 + ... where m{1} m{1} = m{1,2} + m{12}, so a(2) = 2-1 = 1.
m{1,2,3} = x1 x2 x3 + x1 x2 x4 + x1 x3 x4 + ..., m{12,3} = x1 x1 x2 + x2 x2 x1 + ..., m{13,2} = x1 x2 x1 + x2 x1 x2 + ..., m{1,23} = x1 x2 x2 + x2 x1 x1 + ..., m{123} = x1 x1 x1 + x2 x2 x2 + ... and there are 3 independent relations among these 5 elements m{12} m{1} = m{123} + m{12,3}, m{1} m{12} = m{123} + m{1,23}, m{1} m{1,1} = m{1,2,3} + m{12,3} + m{13,2} so a(3) = 5-3 = 2.
References
- D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.2.1.7, Problem 26.
Links
- Vaclav Kotesovec, Table of n, a(n) for n = 1..573 (terms 1..100 from T. D. Noe)
- Vsevolod E. Adler, Set partitions and integrable hierarchies, arXiv:1510.02900 [nlin.SI], 2015.
- Marcelo Aguiar and Swapneel Mahajan, On the Hadamard product of Hopf monoids
- Jean-Luc Baril, Toufik Mansour, Armen Petrossian, Equivalence classes of permutations modulo excedances, 2014.
- Nantel Bergeron, Christophe Reutenauer, Mercedes Rosas, and Mike Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005.
- Daniel Birmajer, Juan B. Gil, Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
- David Callan, On permutations avoiding the dashed patterns 32-41 and 41-32, arXiv preprint arXiv:1405.2064 [math.CO], 2014
- William Y.C. Chen, Teresa X.S. Li, David G.L. Wang, A Bijection between Atomic Partitions and Unsplitable Partitions, Electron. J. Combin. 18 (2011), no. 1, Paper 7.
- Alice L.L. Gao, Sergey Kitaev, and Philip B. Zhang, On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
- Ignas Gasparavičius, Andrius Grigutis, and Juozas Petkelis, Picturesque convolution-like recurrences and partial sums' generation, arXiv:2507.23619 [math.NT], 2025. See p. 27.
- Meng He, J. Ian Munro, S. Srinivasa Rao, A Categorization Theorem on Suffix Arrays with Applications to Space Efficient Text Indexes, SODA 2005, Definition 2.2.
- Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
- Martin Klazar, Bell numbers, their relatives and algebraic differential equations
- Martin Klazar, Bell numbers, their relatives and algebraic differential equations, Journal of Combinatorial Theory, Series A, Volume 102, Issue 1, April 2003, pp. 63-87.
- Margarete C. Wolf, Symmetric Functions of Non-commutative Elements, Duke Math. J., 2 (1936), 626-637.
- Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.
Crossrefs
Programs
-
Maple
T := proc(n, k) option remember; local j; if k=n then 1 elif k<0 then 0 else k*T(n-1,k) + add(T(n-1,j), j=k-1..n-1) fi end: A074664 := n -> T(n, 0); seq(A074664(n), n=0..22); # Peter Luschny, May 13 2014 -
Mathematica
nmax = 23; A087903[n_, k_] := A087903[n, k] = StirlingS2[n-1, k] + Sum[ (k-d-1)*A087903[n-j-1, k-d]*StirlingS2[j, d], {d, 0, k-1}, {j, 0, n-2}]; a[n_] := Sum[ A087903[n, k], {k, 1, n-1}]; a[1] = 1; Table[a[n], {n, 1, nmax}](* Jean-François Alcover, Oct 04 2011, after Philippe Deléham *) Clear[t, n, k, i, nn, x]; coeff = ConstantArray[1, 23]; mp[m_,e_] := If[e==0, IdentityMatrix@ Length@ m, MatrixPower[m, e]]; nn = Length[coeff]; cc = Range[nn]*0 + 1; Monitor[ Do[Clear[t]; t[n_, 1] := t[n, 1] = cc[[n]]; t[n_, k_] := t[n, k] = If[n >= k, Sum[t[n - i, k - 1], {i, 1, 2 - 1}] + Sum[t[n - i, k], {i, 1, 2 - 1}], 0]; A4 = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}]; A5 = A4[[1 ;; nn - 1]]; A5 = Prepend[A5, ConstantArray[0, nn]]; cc = Total[ Table[coeff[[n]]*mp[A5, n - 1][[All, 1]], {n, 1, nn}]];, {i, 1, nn}], i]; cc (* Mats Granvik, Jul 11 2015 *)
-
PARI
{a(n) = if( n<0, 0, polcoeff( 1 - 1 / serlaplace( exp( exp( x + x * O(x^n)) - 1)), n))}; -
PARI
x='x+O('x^100); B=exp(exp(x) - 1); Vec( 1-1/serlaplace(B)) \\ Joerg Arndt, Aug 13 2015
Formula
G.f.: 1 - 1 / B(x) where B(x) = g.f. for A000110 the Bell numbers.
a(n) = Sum_{k=1..n-1} A087903(n,k). a(n+1) = Sum_{k=0..n} A086329(n,k). a(n+2) = Sum_{k=0..n} A086211(n,k). - Philippe Deléham, Jun 13 2004
G.f.: x / (1 - (x - x^2) / (1 - x - (x - 2*x^2) / (1 - 2*x - (x - 3*x^2) / ...))) (a continued fraction). - Michael Somos, Sep 22 2005
Hankel transform is A000142. - Philippe Deléham, Jun 21 2007
From Paul Barry, Nov 26 2009: (Start)
G.f.: (of 1,1,2,6,...) 1/(1-x-x^2/(1-3x-2x^2/(1-4x-3x^2/(1-5x-4x^2/(1-6x-5x^2/(1-... (continued fraction);
G.f.: (of 1,2,6,...) 1/(1-2x-2x^2/(1-3x-3x^2/(1-4x-4x^2/(1-5x-5x^2/(1-... (continued fraction). (End)
G.f.: 1/(1-x/(1-x/(1-2x/(1-x/(1-3x/(1-x/(1-4x/(1-x/(1-5x/(1-x/(1-... (continued fraction). - Paul Barry, Mar 03 2010
G.f. satisfies: A(x) = x/(1 - (1-x)*A( x/(1-x) )). - Paul D. Hanna, Aug 15 2010
a(n) = upper left term in M^(n-1), where M is the following infinite square production matrix:
1, 1, 0, 0, 0, 0, ...
1, 2, 1, 0, 0, 0, ...
1, 1, 3, 1, 0, 0, ...
1, 1, 1, 4, 1, 0, ...
1, 1, 1, 1, 5, 1, ...
1, 1, 1, 1, 1, 6, ...
...
a(n) = sum of top row terms in M^(n-2). Example: top row of M^4 = (22, 31, 28, 10, 1, 0, 0, 0, ...), where 22 = a(5) and (22 + 31 + 28 + 10 + 1) = 92 = a(6). - Gary W. Adamson, Jul 11 2011
From Sergei N. Gladkovskii, Sep 28 2012 to May 19 2013: (Start)
Continued fractions:
G.f.: (2+(x^2-4)/(U(0)-x^2+4))/x where U(k) = k*(2*k+3)*x^2 + x - 2 - (2 - x + 2*k*x)*(2 + 3*x + 2*k*x)*(k+1)*x^2/U(k+1).
G.f.: (1+U(0))/x where U(k) = +x*k - 1 + x - x^2*(k+1)/U(k+1).
G.f.: 1 + 1/x - U(0)/x where U(k) = 1 + x - x*(k+1)/(1 - x/U(k+1)).
G.f.: 1/U(0) where U(k) = 1 - x*(k+1)/(1 - x/U(k+1)).
G.f.: 1/x - ((1+x)/x)/G(0) where G(k) = 1 - 2*x*(k+1)/((2*k+1)*(2*x*k-1) - x*(2*k+1)*(2*k+3)*(2*x*k-1)/(x*(2*k+3) - 2*(k+1)*(2*x*k+x-1)/G(k+1))).
G.f.: (1 - G(0))/x where G(k) = 1 - x/(1 - x*(k + 1)/G(k+1)).
G.f.: 1/Q(0) where Q(k) = 1 + x/(x*k - 1)/Q(k+1).
G.f.: Q(0) where Q(k) = 1 + x/(1 - x + x*(k+1)/(x - 1/Q(k+1))). (End)
Extensions
Edited by Mike Zabrocki, Sep 03 2005
A122367 Dimension of 3-variable non-commutative harmonics (twisted derivative) of order n. The dimension of the space of non-commutative polynomials of degree n in 3 variables which are killed by all symmetric differential operators (where for a monomial w, d_{xi} ( xi w ) = w and d_{xi} ( xj w ) = 0 for i != j).
1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 28657, 75025, 196418, 514229, 1346269, 3524578, 9227465, 24157817, 63245986, 165580141, 433494437, 1134903170, 2971215073, 7778742049, 20365011074, 53316291173, 139583862445, 365435296162, 956722026041
Offset: 0
Comments
Essentially identical to A001519.
From Matthew Lehman, Jun 14 2008: (Start)
Number of monotonic rhythms using n time intervals of equal duration (starting with n=0).
Representationally, let 0 be an interval which is "off" (rest),
1 an interval which is "on" (beep),
1 1 two consecutive "on" intervals (beep, beep),
1 0 1 (beep, rest, beep) and
1-1 two connected consecutive "on" intervals (beeeep).
For f(3)=13:
0 0 0, 0 0 1, 0 1 0, 0 1 1, 0 1-1, 1 0 0, 1 0 1,
1 1 0, 1-1 0, 1 1 1, 1 1-1, 1-1 1, 1-1-1.
(End)
Equivalent to the number of one-dimensional graphs of n nodes, subject to the condition that a node is either 'on' or 'off' and that any two neighboring 'on' nodes can be connected. - Matthew Lehman, Nov 22 2008
Sum_{n>=0} arctan(1/a(n)) = Pi/2. - Jaume Oliver Lafont, Feb 27 2009
This is the limit sequence for certain generalized Pell numbers. - Gregory L. Simay, Oct 21 2024
Examples
a(1) = 2 because x1-x2, x1-x3 are both of degree 1 and are killed by the differential operator d_x1 + d_x2 + d_x3.
a(2) = 5 because x1*x2 - x3*x2, x1*x3 - x2*x3, x2*x1 - x3*x1, x1*x1 - x2*x1 - x2*x2 + x1*x2, x1*x1 - x3*x1 - x3*x3 + x3*x1 are all linearly independent and are killed by d_x1 + d_x2 + d_x3, d_x1 d_x1 + d_x2 d_x2 + d_x3 d_x3 and Sum_{j = 1..3} (d_xi d_xj, i).
Links
- Colin Barker, Table of n, a(n) for n = 0..1000
- Mohammad K. Azarian, Fibonacci Identities as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 38, 2012, pp. 1871-1876 (See Corollary 1 (ii)).
- Paul Barry and A. Hennessy, The Euler-Seidel Matrix, Hankel Matrices and Moment Sequences, J. Int. Seq. 13 (2010) # 10.8.2, Example 13.
- N. Bergeron, C. Reutenauer, M. Rosas, and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005; Canad. J. Math. 60 (2008), no. 2, 266-296
- C. Chevalley, Invariants of finite groups generated by reflections, Amer. J. Math. 77 (1955), 778-782.
- I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
- Tanya Khovanova, Recursive Sequences
- Ron Knott, Pi and the Fibonacci numbers. - _Jaume Oliver Lafont_, Feb 27 2009
- Diego Marques and Alain Togbé, On the sum of powers of two consecutive Fibonacci numbers, Proc. Japan Acad. Ser. A Math. Sci., Volume 86, Number 10 (2010), 174-176.
- H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory, Vol. 7, No. 5 (2011), pp. 1255-1277.
- H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences, Integers, Volume 12A (2012), The John Selfridge Memorial Volume.
- M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2 (1936), 626-637.
- Index entries for linear recurrences with constant coefficients, signature (3,-1).
Crossrefs
Programs
-
Magma
[Fibonacci(2*n+1): n in [0..40]]; // Vincenzo Librandi, Jul 04 2015
-
Maple
a:=n->if n=0 then 1; elif n=1 then 2 else 3*a(n-1)-a(n-2); fi; A122367List := proc(m) local A, P, n; A := [1,2]; P := [2]; for n from 1 to m - 2 do P := ListTools:-PartialSums([op(A), P[-1]]); A := [op(A), P[-1]] od; A end: A122367List(30); # Peter Luschny, Mar 24 2022
-
Mathematica
Table[Fibonacci[2 n + 1], {n, 0, 30}] (* Vincenzo Librandi, Jul 04 2015 *) -
PARI
Vec((1-x)/(1-3*x+x^2) + O(x^50)) \\ Michel Marcus, Jul 04 2015
Formula
G.f.: (1-q)/(1-3*q+q^2). More generally, (Sum_{d=0..n} (n!/(n-d)!*q^d)/Product_{r=1..d} (1 - r*q)) / (Sum_{d=0..n} q^d/Product_{r=1..d} (1 - r*q)) where n=3.
a(n) = 3*a(n-1) - a(n-2) with a(0) = 1, a(1) = 2.
a(n) = Fibonacci(2n+1) = A000045(2n+1). - Philippe Deléham, Feb 11 2009
a(n) = (2^(-1-n)*((3-sqrt(5))^n*(-1+sqrt(5)) + (1+sqrt(5))*(3+sqrt(5))^n)) / sqrt(5). - Colin Barker, Oct 14 2015
a(n) = Sum_{k=0..n} Sum_{i=0..n} binomial(k+i-1, k-i). - Wesley Ivan Hurt, Sep 21 2017
a(n) = A048575(n-1) for n >= 1. - Georg Fischer, Nov 02 2018
a(n) = Fibonacci(n)^2 + Fibonacci(n+1)^2. - Michel Marcus, Mar 18 2019
a(n) = Product_{k=1..n} (1 + 4*cos(2*k*Pi/(2*n+1))^2). - Seiichi Manyama, Apr 30 2021
From J. M. Bergot, May 27 2022: (Start)
a(n) = (L(n)^2 + L(n)*L(n+2))/5 - (-1)^n.
a(n) = 2*(area of a triangle with vertices at (L(n-1), L(n)), (F(n+1), F(n)), (L(n+1), L(n+2))) - 5*(-1)^n for n > 1. (End)
G.f.: (1-x)/(1-3x+x^2) = 1/(1-2x-x^2-x^3-x^4-...) - Gregory L. Simay, Oct 21 2024
E.g.f.: exp(3*x/2)*(5*cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2))/5. - Stefano Spezia, Nov 07 2024
From Peter Bala, May 04 2025: (Start)
a(n) = sqrt(2/5) * sqrt( 1 - T(2*n+1, - 3/2) ), where T(k, x) denotes the k-th Chebyshev polynomial of the first kind.
a(2*n+1/2) = sqrt(5)*a(n)^2 - 2/sqrt(5).
a(3*n+1) = 5*a(n)^3 - 3*a(n); hence a(n) divides a(3*n+1).
a(4*n+3/2) = 5^(3/2)*a(n)^4 - 4*sqrt(5)*a(n)^2 + 2/sqrt(5).
a(5*n+2) = (5^2)*a(n)^5 - 5*5*a(n)^3 + 5*a(n); hence a(n) divides a(5*n+2).
See A034807 for the unsigned coefficients [1, 2; 1, 3; 1, 4, 2; 1, 5, 5; ...].
In general, for k >= 0, a(k*n + (k-1)/2) = a(-1/2) * T(k, a(n)/a(-1/2)), where a(n) = (2^(-1-n)*((3 - sqrt(5))^n *(-1 + sqrt(5)) + (1 + sqrt(5))*(3 + sqrt(5))^n)) / sqrt(5), as given above, and a(-1/2) = 2/sqrt(5).
The aerated sequence [b(n)]n>=1 = [1, 0, 2, 0, 5, 0, 13, 0, ...] is a fourth-order linear divisibility sequence; that is, if n | m then b(n) | b(m). It is the case P1 = 0, P2 = -5, Q = 1 of the 3-parameter family of divisibility sequences found by Williams and Guy.
A112340 Triangle read by rows of numbers b_{n,k}, n>=1, 1<=k<=n such that Product_{n,k} 1/(1-q^n t^k)^{b_{n,k}} = 1 + Sum_{i,j>=1} S_{i,j} q^i t^j where S_{i,j} are entries in the table A008277 (the inverse Euler transformation of the table of Stirling numbers of the second kind).
1, 1, 0, 1, 2, 0, 1, 5, 3, 0, 1, 13, 16, 4, 0, 1, 28, 67, 34, 5, 0, 1, 60, 249, 229, 65, 6, 0, 1, 123, 853, 1265, 609, 107, 7, 0, 1, 251, 2787, 6325, 4696, 1376, 168, 8, 0, 1, 506, 8840, 29484, 31947, 14068, 2772, 244, 9, 0, 1, 1018, 27503, 131402, 199766, 124859, 36252
Offset: 1
Comments
The number of set partitions of size n length k which are 'Lyndon,' that is, since all set partitions are isomorphic to sequences of atomic set partitions (A087903), those which are smallest of all rotations of these sequences in lex order (with respect to some ordering on the atomic set partitions) are Lyndon. 1; 1, 0; 1, 2, 0; 1, 5, 3, 0; 1, 13, 16, 4, 0;
Examples
There are 6 set partitions of size 4 and length 3, {12|3|4}, {13|2|4}, {14|2|3}, {1|23|4}, {1|24|3}, {1|2|34} and the sequences the correspond to are ({12},{1},{1}), ({13|2}, {1}), ({14|2|3}), ({1},{12},{1}), ({1},{13|2}), ({1},{1},{12}). Now there are three {({12},{1},{1}), ({1},{12},{1}), ({1},{1},{12})} that are rotations of each other and ({1}, {1}, {12}) is the smallest of these, {({13|2}, {1}), ({1},{13|2})} are rotations of each other and ({1},{13|2}) is the smallest and ({14|2|3}) is atomic and all atomic s.p. are Lyndon. Hence {1|2|34}, {1|24|3}, {14|2|3} are Lyndon and a(4,3) = 3
Triangle begins:
1;
1, 0;
1, 2, 0;
1, 5, 3, 0;
1, 13, 16, 4, 0;
1, 28, 67, 34, 5, 0;
...
Links
- N. Bergeron, M. Zabrocki, The Hopf algebras of symmetric functions and quasisymmetric functions in non-commutative variables are free and cofree, arXiv:math/0509265 [math.CO], 2005.
- M. Rosas and B. Sagan, Symmetric Functions in Noncommuting Variables, Transactions of the American Mathematical Society, 358 (2006), no. 1, 215-232.
- M. C. Wolf, Symmetric functions for non-commutative elements, Duke Math. J., 2 (1936), 626-637.
Programs
-
Maple
EULERitable:=proc(tbl) local ser,out,i,j,tmp; ser:=1+add(add(q^i*t^j*tbl[i][j], j=1..nops(tbl[i])), i=1..nops(tbl)); out:=[]; for i from 1 to nops(tbl) do tmp:=coeff(ser,q,i); ser:=expand(ser*mul(add((-q^i*t^j)^k*choose(abs(coeff(tmp,t,j)),k),k=0..nops(tbl)/i), j = 1..degree(tmp,t))); ser:=subs({seq(q^j=0,j=nops(tbl)+1..degree(ser,q))},ser); out:=[op(out),[seq(abs(coeff(tmp,t,j)), j=1..degree(tmp,t))]]; end do; out; end: EULERitable([seq([seq(combinat[stirling2](n,k),k=1..n)],n=1..10)]); -
Mathematica
nmax = 11; b[n_, k_] /; k < 1 || k > n = 0; coes[m_] := Product[1/(1 - q^n t^k)^b[n, k], {n, 1, m}, {k, 1, m}] - 1 - Sum[ StirlingS2[i, j] q^i t^j, {i, 1, m}, {j, 1, m}] + O[t]^m + O[q]^m // Normal // CoefficientList[#, {t, q}]&; sol[1] = {b[1, 1] -> 1}; Do[sol[m] = Solve[Thread[(coes[m] /. sol[m - 1]) == 0]], {m, 2, nmax + 1}]; bb = Flatten[Table[sol[m], {m, 1, nmax + 1}]]; Table[b[n, k] /. bb, {n, 1, nmax}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 11 2017 *)
A122369 Dimension of 5-variable non-commutative harmonics (twisted derivative). The dimension of the space of non-commutative polynomials in 5 variables which are killed by all symmetric differential operators (where for a monomial w, d_{xi} ( xi w ) = w and d_{xi} ( xj w ) = 0 for i/=j).
1, 4, 19, 93, 459, 2273, 11274, 55964, 277924, 1380527, 6858356, 34074280, 169297743, 841173845, 4179517118, 20766807551, 103184684826, 512698227699, 2547469553647, 12657750705603, 62893284231103, 312501512711984, 1552744642741738, 7715214279423070
Offset: 0
Keywords
Examples
a(1) = 4 because x1-x2, x2-x3, x3-x4, x4-x5 are all of degree 1 and are killed by the differential operator d_x1+d_x2+d_x3+d_x4+d_x5.
References
- C. Chevalley, Invariants of finite groups generated by reflections, Amer. J. Math. 77 (1955), 778-782.
- M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2 (1936), 626-637.
Links
- N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math.CO/0502082 , Canad. J. Math. 60 (2008), no. 2, 266-296
Crossrefs
Programs
-
Maple
coeffs(convert(series((1-6*q+11*q^2-6*q^3)/(1-10*q+32*q^2-37*q^3+11*q^4),q,30),`+`)-O(q^30),q);
-
Mathematica
gf = With[{n = 5}, Sum[n!/(n-d)! q^d/Product[(1 - r q), {r, 1, d}], {d, 0, n}]/Sum[ q^d/Product[(1 - r q), {r, 1, d}], {d, 0, n}]]; CoefficientList[gf + O[q]^22, q] (* Jean-François Alcover, Nov 17 2018 *)
Formula
G.f. (1-6*q+11*q^2-6*q^3)/(1-10*q+32*q^2-37*q^3+11*q^4) more generally, sum( n!/(n-d)!*q^d/prod((1-r*q),r=1..d), d=0..n)/sum( q^d/prod((1-r*q),r=1..d), d=0..n) where n=5.
A109062 Triangle read by rows: number of atomic set compositions of size n and length k (see description in A095989) 1 <= k <= n.
1, 1, 1, 1, 4, 3, 1, 11, 23, 13, 1, 26, 112, 158, 71, 1, 57, 446, 1170, 1241, 461, 1, 120, 1593, 6880, 12871, 10912, 3447, 1, 247, 5337, 35503, 103887, 150413, 106031, 29093, 1, 502, 17190, 168982, 724148, 1589266, 1872286, 1128218, 273343, 1, 1013, 54008
Offset: 1
Comments
Also the number of free generators and primitives of the quasi-symmetric functions in non-commuting variables. - Mike Zabrocki, Aug 06 2006
Triangle given by [1,0,2,0,3,0,4,0,5,...] DELTA [1,2,2,3,3,4,4,5,5,6,6,7,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Aug 01 2007
Apparently, the alternating sums vanish for n > 1. - F. Chapoton, Sep 05 2023
Examples
Atomic set compositions a(1,1)=1: [{1}]; a(2,1)=1, a(2,2)=1: [{12}], [{2},{1}]; a(3,1)=1, a(3,2)=4, a(3,3)=3: [{123}], [{2},{13}], [{3}, {12}], [{23}, {1}], [{13},{2}], [{2},{3},{1}], [{3},{1},{2}], [{3},{2},{1}].
Triangle begins:
1;
1, 1;
1, 4, 3;
1, 11, 23, 13;
1, 26, 112, 158, 71;
...
Links
- N. Bergeron and M. Zabrocki, The Hopf algebras of symmetric functions and quasisymmetric functions in non-commutative variables are free and cofree, arXiv:math/0509265 [math.CO], 2005.
- Ming-Jian Ding and Bao-Xuan Zhu, Some results related to Hurwitz stability of combinatorial polynomials, Advances in Applied Mathematics, Volume 152, (2024), 102591. See p. 7.
Crossrefs
Programs
-
Maple
f:=(n,k)->coeff(coeff(series(1-1/(1+add(add(q^m*t^i* Stirling2(m,i)*i!,i=1..m),m=1..n)),q,n+1),q,n),t,k): seq(seq(f(n,k), k=1..n), n=1..10);
Formula
G.f.: 1-1/(1+Sum_{n>=1} Sum_{k=1..n} q^n*t^k*Stirling2(n,k)*k!).
A122368 Dimension of 4-variable non-commutative harmonics (twisted derivative). The dimension of the space of non-commutative polynomials in 4 variables which are killed by all symmetric differential operators (where for a monomial w, d_{xi} ( xi w ) = w and d_{xi} ( xj w ) = 0 for i/=j).
1, 3, 11, 42, 162, 627, 2430, 9423, 36549, 141777, 549990, 2133594, 8276985, 32109534, 124565121, 483235875, 1874657763, 7272519066, 28212902154, 109448714619, 424593725526, 1647162628047, 6389978382405, 24789187818585
Offset: 1
Keywords
Comments
Empirical: a(n) is the sum of the greatest elements over all lexicographically greatest elements in all partitions in the canonical basis of the Temperley-Lieb algebra of order n. - John M. Campbell, Oct 17 2017
Examples
a(1) = 3 because x1-x2, x2-x3, x3-x4 are all of degree 1 and are killed by the differential operator d_x1+d_x2+d_x3+d_x4
For example, the canonical basis of the Temperley-Lieb algebra of order 3 is {{{-3, 1}, {-2, -1}, {2, 3}}, {{-3, 3}, {-2, 2}, {-1, 1}}, {{-3, 3}, {-2, -1}, {1, 2}}, {{-3, -2}, {-1, 1}, {2, 3}}, {{-3, -2}, {-1, 3}, {1, 2}}}, and the lexicographically greatest elements among all partitions in this basis are {2, 3}, {-1, 1}, {1, 2}, {2, 3}, and {1, 2}, with a(3) = 3+1+2+3+2 = 11. - _John M. Campbell_, Oct 17 2017
Links
- Michael De Vlieger, Table of n, a(n) for n = 1..1699
- Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
- N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005; Canad. J. Math. 60 (2008), no. 2, 266-296.
- C. Chevalley, Invariants of finite groups generated by reflections, Amer. J. Math. 77 (1955), 778-782.
- Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
- M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2 (1936), 626-637.
- Index entries for linear recurrences with constant coefficients, signature (6,-9,3).
Crossrefs
Programs
-
Maple
coeffs(convert(series((1-3*q+2*q^2)/(1-6*q+9*q^2-3*q^3),q,30),`+`)-O(q^30),q);
-
Mathematica
LinearRecurrence[{6, -9, 3}, {1, 3, 11}, 24] (* Jean-François Alcover, Sep 22 2017 *)
Formula
O.g.f.: (1-3*q+2*q^2)/(1-6*q+9*q^2-3*q^3) more generally, sum( n!/(n-d)!*q^d/prod((1-r*q),r=1..d), d=0..n)/sum( q^d/prod((1-r*q),r=1..d), d=0..n) where n=4
A122370 Dimension of 6-variable non-commutative harmonics (twisted derivative). The dimension of the space of non-commutative polynomials in 6 variables which are killed by all symmetric differential operators (where for a monomial w, d_{xi} ( xi w ) = w and d_{xi} ( xj w ) = 0 for i/=j).
1, 5, 29, 172, 1026, 6134, 36712, 219847, 1316963, 7890594, 47282065, 283344410, 1698058817, 10176618298, 60990528210, 365532989831, 2190756912988, 13129979193808, 78692862940748, 471636719623539
Offset: 0
Keywords
Examples
a(1) = 5 because x1-x2, x2-x3, x3-x4, x4-x5, x5-x6 are all of degree 1 and are killed by the differential operator d_x1+d_x2+d_x3+d_x4+d_x5+d_x6.
References
- C. Chevalley, Invariants of finite groups generated by reflections, Amer. J. Math. 77 (1955), 778-782.
- M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2 (1936), 626-637.
Links
- N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math.CO/0502082 , Canad. J. Math. 60 (2008), no. 2, 266-296
- Index entries for linear recurrences with constant coefficients, signature (15,-81,192,-189,53)
Crossrefs
Programs
-
Maple
coeffs(convert(series((1-10*q+35*q^2-50*q^3+24*q^4)/ (1-15*q+81*q^2 -192*q^3+189*q^4 -53*q^5),q,20), `+`) -O(q^20),q)
-
Mathematica
LinearRecurrence[{15, -81, 192, -189, 53}, {1, 5, 29, 172, 1026}, 20] (* Jean-François Alcover, Sep 22 2017 *)
Formula
o.g.f. (1-10*q+35*q^2-50*q^3+24*q^4) / (1-15*q+81*q^2 -192*q^3+189*q^4 -53*q^5) more generally, sum( n!/(n-d)!*q^d/prod((1-r*q),r=1..d), d=0..n) / sum( q^d/prod((1-r*q),r=1..d), d=0..n) where n=6.
A122371 Dimension of 7-variable non-commutative harmonics (twisted derivative). The dimension of the space of non-commutative polynomials in 7 variables which are killed by all symmetric differential operators (where for a monomial w, d_{xi} ( xi w ) = w and d_{xi} ( xj w ) = 0 for i/=j).
1, 6, 41, 285, 1989, 13901, 97215, 680079, 4758408, 33297267, 233014444, 1630701426, 11412409945, 79870754268, 558989013403, 3912210491549, 27380636068267, 191631324294463, 1341190961828143, 9386756237545989
Offset: 0
Keywords
Examples
a(1) = 6 because x1-x2, x2-x3, x3-x4, x4-x5, x5-x6, x6-x7 are all of degree 1 and are killed by the differential operator d_x1+d_x2+d_x3+d_x4+d_x5+d_x6+d_x7.
References
- C. Chevalley, Invariants of finite groups generated by reflections, Amer. J. Math. 77 (1955), 778-782.
- M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2 (1936), 626-637.
Links
- N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math.CO/0502082 , Canad. J. Math. 60 (2008), no. 2, 266-296.
- Index entries for linear recurrences with constant coefficients, signature (21,-170,669,-1314,1157,-309).
Crossrefs
Programs
-
Maple
coeffs(convert(series((1-15*q+ 85*q^2-225*q^3+274*q^4-120*q^5) / (1-21*q+170*q^2-669*q^3+1314*q^4-1157*q^5+309*q^6),q,20),`+`)-O(q^20),q);
-
Mathematica
LinearRecurrence[{21, -170, 669, -1314, 1157, -309}, {1, 6, 41, 285, 1989, 13901}, 20] (* Jean-François Alcover, Sep 22 2017 *)
Formula
G.f.: (1-15*q+ 85*q^2-225*q^3+274*q^4-120*q^5) / (1-21*q+170*q^2-669*q^3 +1314*q^4-1157*q^5 +309*q^6) more generally, sum( n!/(n-d)!*q^d/prod((1-r*q),r=1..d), d=0..n)/sum( q^d/prod((1-r*q), r=1..d), d=0..n) where n=7.
A122372 Dimension of 8-variable non-commutative harmonics (twisted derivative). The dimension of the space of non-commutative polynomials in 8 variables which are killed by all symmetric differential operators (where for a monomial w, d_{xi} ( xi w ) = w and d_{xi} ( xj w ) = 0 for i/=j).
1, 7, 55, 438, 3498, 27962, 223604, 1788406, 14305102, 114429193, 915366442, 7322521512, 58577537621, 468602617723, 3748697751384, 29988696932490, 239903055854075, 1919175464438065, 15353030007717639, 122821355074655309
Offset: 0
Keywords
Examples
A122371 a(1) = 7 because x1-x2, x2-x3, x3-x4, x4-x5, x5-x6, x6-x7, x7-x8 are all of degree 1 and are killed by the differential operator d_x1+d_x2+d_x3+d_x4+d_x5+d_x6+d_x7.
Links
- N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005; Canad. J. Math. 60 (2008), no. 2, 266-296.
- C. Chevalley, Invariants of finite groups generated by reflections, Amer. J. Math. 77 (1955), 778-782.
- M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2 (1936), 626-637.
- Index entries for linear recurrences with constant coefficients, signature (28,-316,1845,-5925,10190,-8249,2119).
Crossrefs
Programs
-
Maple
coeffs(convert(series((1-21*q+175*q^2-735*q^3+1624*q^4-1764*q^5+720*q^6)/ (1-28*q+316*q^2-1845*q^3+5925*q^4-10190*q^5+8249*q^6-2119*q^7), q,20),`+`)-O(q^20),q);
-
Mathematica
n = 8; gf = Sum[n!/(n-d)! q^d/Product[(1 - r q), {r, 1, d}], {d, 0, n}]/ Sum[q^d/Product[(1 - r q), {r, 1, d}], {d, 0, n}] + O[q]^20; CoefficientList[gf, q] (* Jean-François Alcover, Dec 03 2018 *)
Formula
G.f.: (1-21*q+175*q^2-735*q^3+1624*q^4-1764*q^5+720*q^6)/ (1-28*q+316*q^2-1845*q^3+5925*q^4-10190*q^5+8249*q^6-2119*q^7) more generally, sum( n!/(n-d)!*q^d/prod((1-r*q),r=1..d), d=0..n) / sum( q^d/prod((1-r*q), r=1..d), d=0..n) where n=8.
Comments