A059438 -id:A059438 - cp's OEIS frontend

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

N. J. A. Sloane

Restored the alternative spelling of Sierpinski to facilitate searching for this triangle using regular-expression matching commands in ASCII. - N. J. A. Sloane, Jan 18 2016
Also triangle giving successive states of cellular automaton generated by "Rule 60" and "Rule 102". - Hans Havermann, May 26 2002
Also triangle formed by reading triangle of Eulerian numbers (A008292) mod 2. - Philippe Deléham, Oct 02 2003
Self-inverse when regarded as an infinite lower triangular matrix over GF(2).
Start with [1], repeatedly apply the map 0 -> [00/00], 1 -> [10/11] [Allouche and Berthe]
Also triangle formed by reading triangles A011117, A028338, A039757, A059438, A085881, A086646, A086872, A087903, A104219 mod 2. - Philippe Deléham, Jun 18 2005
J. H. Conway writes (in Math Forum): at least the first 31 rows give odd-sided constructible polygons (sides 1, 3, 5, 15, 17, ... see A001317). The 1's form a Sierpiński sieve. - M. Dauchez (mdzzdm(AT)yahoo.fr), Sep 19 2005
When regarded as an infinite lower triangular matrix, its inverse is a (-1,0,1)-matrix with zeros undisturbed and the nonzero entries in every column form the Prouhet-Thue-Morse sequence (1,-1,-1,1,-1,1,1,-1,...) A010060 (up to relabeling). - David Callan, Oct 27 2006
Triangle read by rows: antidiagonals of an array formed by successive iterates of running sums mod 2, beginning with (1, 1, 1, ...). - Gary W. Adamson, Jul 10 2008
T(n,k) = A057427(A143333(n,k)). - Reinhard Zumkeller, Oct 24 2010
The triangle sums, see A180662 for their definitions, link Sierpiński’s triangle A047999 with seven sequences, see the crossrefs. The Kn1y(n) and Kn2y(n), y >= 1, triangle sums lead to the Sierpiński-Stern triangle A191372. - Johannes W. Meijer, Jun 05 2011
Used to compute the total Steifel-Whitney cohomology class of the Real Projective space. This was an essential component of the proof that there are no product operations without zero divisors on R^n for n not equal to 1, 2, 4 or 8 (real numbers, complex numbers, quaternions, Cayley numbers), proved by Bott and Milnor. - Marcus Jaiclin, Feb 07 2012
T(n,k) = A134636(n,k) mod 2. - Reinhard Zumkeller, Nov 23 2012
T(n,k) = 1 - A219463(n,k), 0 <= k <= n. - Reinhard Zumkeller, Nov 30 2012
From Vladimir Shevelev, Dec 31 2013: (Start)
Also table of coefficients of polynomials s_n(x) of degree n which are defined by formula s_n(x) = Sum_{i=0..n} (binomial(n,i) mod 2)*x^k. These polynomials we naturally call Sierpiński's polynomials. They also are defined by the recursion: s_0(x)=1, s_(2*n+1)(x) = (x+1)*s_n(x^2), n>=0, and s_(2*n)(x) = s_n(x^2), n>=1.
Note that: s_n(1)  = A001316(n),
           s_n(2)  = A001317(n),
           s_n(3)  = A100307(n),
           s_n(4)  = A001317(2*n),
           s_n(5)  = A100308(n),
           s_n(6)  = A100309(n),
           s_n(7)  = A100310(n),
           s_n(8)  = A100311(n),
           s_n(9)  = A100307(2*n),
           s_n(10) = A006943(n),
           s_n(16) = A001317(4*n),
           s_n(25) = A100308(2*n), etc.
The equality s_n(10) = A006943(n) means that sequence A047999 is obtained from A006943 by the separation by commas of the digits of its terms. (End)
Comment from N. J. A. Sloane, Jan 18 2016: (Start)
Take a diamond-shaped region with edge length n from the top of the triangle, and rotate it by 45 degrees to get a square S_n. Here is S_6:
  [1, 1, 1, 1, 1, 1]
  [1, 0, 1, 0, 1, 0]
  [1, 1, 0, 0, 1, 1]
  [1, 0, 0, 0, 1, 0]
  [1, 1, 1, 1, 0, 0]
  [1, 0, 1, 0, 0, 0].
Then (i) S_n contains no square (parallel to the axes) with all four corners equal to 1 (cf. A227133); (ii) S_n can be constructed by using the greedy algorithm with the constraint that there is no square with that property; and (iii) S_n contains A064194(n) 1's. Thus A064194(n) is a lower bound on A227133(n). (End)
See A123098 for a multiplicative encoding of the rows, i.e., product of the primes selected by nonzero terms; e.g., 1 0 1 => 2^1 * 3^0 * 5^1. - M. F. Hasler, Sep 18 2016
From Valentin Bakoev, Jul 11 2020: (Start)
The Sierpinski's triangle with 2^n rows is a part of a lower triangular matrix M_n of dimension 2^n X 2^n. M_n is a block matrix defined recursively: M_1= [1, 0], [1, 1], and for n>1, M_n = [M_(n-1), O_(n-1)], [M_(n-1), M_(n-1)], where M_(n-1) is a block matrix of the same type, but of dimension 2^(n-1) X 2^(n-1), and O_(n-1) is the zero matrix of dimension 2^(n-1) X 2^(n-1). Here is how M_1, M_2 and M_3 look like:
1 0     1 0 0 0      1 0 0 0 0 0 0 0
1 1     1 1 0 0      1 1 0 0 0 0 0 0   - It is seen the self-similarity of the
        1 0 1 0      1 0 1 0 0 0 0 0     matrices M_1, M_2, ..., M_n, ...,
        1 1 1 1      1 1 1 1 0 0 0 0     analogously to the Sierpinski's fractal.
                     1 0 0 0 1 0 0 0
                     1 1 0 0 1 1 0 0
                     1 0 1 0 1 0 1 0
                     1 1 1 1 1 1 1 1
M_n can also be defined as M_n = M_1 X M_(n-1) where X denotes the Kronecker product. M_n is an important matrix in coding theory, cryptography, Boolean algebra, monotone Boolean functions, etc. It is a transformation matrix used in computing the algebraic normal form of Boolean functions. Some properties and links concerning M_n can be seen in LINKS. (End)
Sierpinski's gasket has fractal (Hausdorff) dimension log(A000217(2))/log(2) = log(3)/log(2) = 1.58496... (and cf. A020857). This gasket is the first of a family of gaskets formed by taking the Pascal triangle (A007318) mod j, j >= 2 (see CROSSREFS). For prime j, the dimension of the gasket is log(A000217(j))/log(j) = log(j(j + 1)/2)/log(j) (see Reiter and Bondarenko references). - Richard L. Ollerton, Dec 14 2021

			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,
  ...

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.

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

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).
Other versions: A090971, A038183.
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.
Triangle sums (see the comments): A001316 (Row1; Related to Row2), A002487 (Related to Kn11, Kn12, Kn13, Kn21, Kn22, Kn23), A007306 (Kn3, Kn4), A060632 (Fi1, Fi2), A120562 (Ca1, Ca2), A112970 (Gi1, Gi2), A127830 (Ze3, Ze4). (End)

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

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 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

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 *)

\\ 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

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

T(n,k)=bitand(n-k,k)==0 \\ Charles R Greathouse IV, Aug 11 2016

def A047999_T(n,k):
    return int(not ~n & k) # Chai Wah Wu, Feb 09 2016

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
Sum_{k>=0} T(n, k) = A001316(n) = 2^A000120(n).
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)) (0Let 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 kT(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)

Additional links from Lekraj Beedassy, Jan 22 2004

A003319 Number of connected permutations of [1..n] (those not fixing [1..j] for 0 < j < n). Also called indecomposable permutations, or irreducible permutations.

Original entry on oeis.org

1, 1, 1, 3, 13, 71, 461, 3447, 29093, 273343, 2829325, 31998903, 392743957, 5201061455, 73943424413, 1123596277863, 18176728317413, 311951144828863, 5661698774848621, 108355864447215063, 2181096921557783605, 46066653228356851631, 1018705098450570562877

Offset: 0

N. J. A. Sloane

Also the number of permutations with no global descents, as introduced by Aguiar and Sottile [Corollaries 6.3, 6.4 and Remark 6.5].
Also the dimensions of the homogeneous components of the space of primitive elements of the Malvenuto-Reutenauer Hopf algebra of permutations. This result, due to Poirier and Reutenauer [Theoreme 2.1] is stated in this form in the work of Aguiar and Sottile [Corollary 6.3] and also in the work of Duchamp, Hivert and Thibon [Section 3.3].
Related to number of subgroups of index n-1 in free group of rank 2 (i.e., maximal number of subgroups of index n-1 in any 2-generator group). See Problem 5.13(b) in Stanley's Enumerative Combinatorics, Vol. 2.
Also the left border of triangle A144107, with row sums = n!. - Gary W. Adamson, Sep 11 2008
Hankel transform is A059332. Hankel transform of aerated sequence is A137704(n+1). - Paul Barry, Oct 07 2008
For every n, a(n+1) is also the moment of order n for the probability density function rho(x) = exp(x)/(Ei(1,-x)*(Ei(1,-x) + 2*I*Pi)) on the interval 0..infinity, with Ei the exponential-integral function. - Groux Roland, Jan 16 2009
Also (apparently), a(n+1) is the number of rooted hypermaps with n darts on a surface of any genus (see Walsh 2012). - N. J. A. Sloane, Aug 01 2012
Also recurrent sequence A233824 (for n > 0) in Panaitopol's formula for pi(x), the number of primes <= x. - Jonathan Sondow, Dec 19 2013
Also the number of mobiles (cyclic rooted trees) with an arrow from each internal vertex to a descendant of that vertex. - Brad R. Jones, Sep 12 2014
Up to sign, Möbius numbers of the shard intersection orders of type A, see Theorem 1.3 in Reading reference. - F. Chapoton, Apr 29 2015
Also, a(n) is the number of distinct leaf matrices of complete non-ambiguous trees of size n. - Daniel Chen, Oct 23 2022

			G.f. = 1 + x + x^2 + 3*x^3 + 13*x^4 + 71*x^5 + 461*x^6 + 3447*x^7 + 29093*x^8 + ...
From _Peter Luschny_, Aug 03 2022: (Start)
A permutation p in [n] (where n >= 0) is reducible if there exists an i in 1..n-1 such that for all j in the range 1..i and all k in the range i+1..n it is true that p(j) < p(k). (Note that a range a..b includes a and b.) If such an i exists we say that i splits the permutation at i.
Examples:
* () is not reducible since there is no index i which splits (). (=> a(0) = 1)
* (1) is not reducible since there is no index i which splits (1). (=> a(1) = 1)
* (1, 2) is reducible since index 1 splits (1, 2) as p(1) < p(2).
* (2, 1) is not reducible since at the only potential splitting point i = 1 we have p(1) > p(2). (=> a(2) = 1)
* For n = 3 we have (1, 2, 3), (1, 3, 2), and (2, 1, 3) are reducible and (2, 3, 1), (3, 1, 2), and (3, 2, 1) are irreducible. (End)

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 25, Example 20.
E. W. Bowen, Letter to N. J. A. Sloane, Aug 27 1976.
L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 84 (#25), 262 (#14) and 295 (#16).
P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 23, N_{n,2}.
I. M. Gessel and R. P. Stanley, Algebraic Enumeration, chapter 21 in Handbook of Combinatorics, Vol. 2, edited by R. L. Graham et al., The MIT Press, Mass, 1995.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 22.
H. P. Robinson, Letter to N. J. A. Sloane, Nov 19 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 1, Ex. 128; Vol. 2, 1999, see Problem 5.13(b).

Seiichi Manyama, Table of n, a(n) for n = 0..449 (first 102 terms from T. D. Noe)
Marcelo Aguiar and Frank Sottile, Structure of the Malvenuto-Reutenauer Hopf algebra of permutations, arXiv:math/0203282 [math.CO], 2002-2005.
Marcelo Aguiar and Aaron Lauve, Convolution Powers of the Identity, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, pp.1053-1064, 2013, DMTCS Proceedings. .
M. Aguiar and A. Lauve, Antipode and Convolution Powers of the Identity in Graded Connected Hopf Algebras, FPSAC 2013 Paris, France DMTCS Proc. AS, 2013, 1083-1094.
M. Aguiar and A. Lauve, The characteristic polynomial of the Adams operators on graded connected Hopf algebras, 2014.
Marcelo Aguiar and Swapneel Mahajan, On the Hadamard product of Hopf monoids, 2013.
Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See p. 10.
Joerg Arndt, Generating Random Permutations, PhD thesis, Australian National University, Canberra, Australia, (2010).
Joerg Arndt, Matters Computational (The Fxtbook), p. 281
Roland Bacher and Christophe Reutenauer, Number of right ideals and a q-analogue of indecomposable permutations, arXiv preprint arXiv:1511.00426 [math.CO], 2015.
Paul Barry, A note on number triangles that are almost their own production matrix, arXiv:1804.06801 [math.CO], 2018.
Julien Berestycki, Eric Brunet and Zhan Shi, How many evolutionary histories only increase fitness?, arXiv preprint arXiv:1304.0246 [math.PR], 2013.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
E. W. Bowen and N. J. A. Sloane, Correspondence, 1976.
Glenn Bruda, Asymptotic expansions for the reciprocal Hardy-Littlewood logarithmic integrals, arXiv:2412.19866 [math.CO], 2024. See pages 1, 7.
David Callan, Counting Stabilized-Interval-Free Permutations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.1.8.
Peter Cameron's Blog, The symmetric group, 11, Posted 09/04/2011.
Mahir Bilen Can, Luke Nelson, and Kevin Treat, A Catalanization Map on the Symmetric Group, Enum. Comb. Appl. (2022) Vol. 2, No. 4, #S4PP7.
Daniel Chen and Sebastian Ohlig, Associated Permutations of Complete Non-Ambiguous Trees and Zubieta's Conjecture, arXiv:2210.11117 [math.CO], 2022.
Fan Chung and R. L. Graham, Primitive juggling sequences, Am. Math. Monthly 115 (3) (2008) 185-194.
L. Comtet, Sur les coefficients de l'inverse de la série formelle Sum n! t^n, Comptes Rend. Acad. Sci. Paris, A 275 (1972), 569-572.
L. Comtet, Series inversions, C. R. Acad. Sc. Paris, t. 275 (25 septembre 1972), 569-572. (Annotated scanned copy)
Xinle Dai, Jordan Long, and Karen Yeats, Subdivergence-free gluings of trees, arXiv:2106.07494 [math.CO], 2021.
M. A. Deryagina and A. D. Mednykh, On the enumeration of circular maps with given number of edges, Siberian Mathematical Journal, 54, No. 6, 2013, 624-639.
Stoyan Dimitrov, Sorting by shuffling methods and a queue, arXiv:2103.04332 [math.CO], 2021.
J. D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969) 199-205.
John D. Dixon, Asymptotics of Generating the Symmetric and Alternating Groups, Electronic Journal of Combinatorics, vol 11(2), R56.
G. Duchamp, F. Hivert, and J.-Y. Thibon, Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras, arXiv:math/0105065 [math.CO], 2001.
G. A. Edgar, Transseries for beginners, arXiv:0801.4877 [math.RA], 2008-2009.
Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, Catalan-Spitzer permutations, arXiv:2310.06288 [math.CO], 2023. See p. 19.
Jesse Elliott, Asymptotic expansions of the prime counting function, arXiv:1809.06633 [math.NT], 2018.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 90.
A. L. L. Gao, S. Kitaev, and P. B. Zhang. On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
I. M. Gessel and R. P. Stanley Algebraic Enumeration (See pages 7-8 for generating function.)
R. K. Guy, Letter to N. J. A. Sloane, Mar 1974
P. Hegarty and A. Martinsson, On the existence of accessible paths in various models of fitness landscapes, arXiv preprint arXiv:1210.4798 [math.PR], 2012. - From _N. J. A. Sloane_, Jan 01 2013
V. Jelínek and P. Valtr, Splittings and Ramsey Properties of Permutation Classes, arXiv preprint arXiv:1307.0027 [math.CO], 2013.
B. R. Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
A. King, Generating indecomposable permutations, Discrete Math., 306 (2006), 508-518.
Y. Koh and S. Ree, Connected permutation graphs, Discrete Math. 307 (2007), 2628-2635.
M. K. Krotter, I. C. Christov, J. M. Ottino and R. M. Lueptow, Cutting and Shuffling a Line Segment: Mixing by Interval Exchange Transformations, arXiv preprint arXiv:1208.2052 [physics.flu-dyn], 2012. - From _N. J. A. Sloane_, Dec 25 2012
Ajay Kumar and Chanchal Kumar, Monomial ideals induced by permutations avoiding patterns, 2018.
Chanchal Kumar and Amit Roy, Integer Sequences and Monomial Ideals, arXiv:2003.10098 [math.CO], 2020.
Steven Linton, James Propp, Tom Roby, and Julian West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, arXiv:1103.4936 [math.CO], 2011.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318. see p. 292.
Richard J. Martin and Michael J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica: 35:3 (2015), 309-315.
Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions (2008); arXiv:0806.3682 [math.CO]. Discrete Math. 310 (2010), no. 24, 3584-3606.
P. Ossona de Mendez and P. Rosenstiehl, Transitivity and connectivity of permutations, Combinatorica, 24 (No. 3, 2004), 487-501.
L. Panaitopol, A formula for pi(x) applied to a result of Koninck-Ivić, Nieuw Arch. Wisk. 5/1 55-56 (2000).
Vincent Pilaud, Brick polytopes, lattice quotients, and Hopf algebras, arXiv:1505.07665 [math.CO], 2015.
S. Poirier and C. Reutenauer, Algèbres Hopf de tableaux, Ann. Sci. Math. Quebec 19 (95), no. 1, 79-90.
N. Reading Noncrossing partitions and the shard intersection order. J. Algebraic Combin. 33 (2011), no. 4. arXiv preprint arXiv:0909.3288, [math.CO], 2009.
Herman P. Robinson, Letter to N. J. A. Sloane, Nov 19 1973.
R. P. Stanley, The Descent Set and Connectivity Set of a Permutation, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.8.
Timothy R. Walsh, Space-efficient generation of nonisomorphic maps and hypermaps, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.3.
Marcel Wienöbst, Max Bannach, and Maciej Liśkiewicz, Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications, arXiv:2205.02654 [cs.LG], 2022.
Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 7.

See A167894 for another version.
Bisections give A272656, A272657.
Row sums of A111184 and A089949.
Leading diagonal of A059438. A diagonal of A263484.
Cf. A051296, A084938, A074664, A113869, A144107.
Cf. A260503, A259472, A261214, A261239, A261253, A261254.
Cf. A090238, A000698, A356291 (reducible permutations).
Column k=0 of A370380 and A370381 (without pair of initial terms and with different offset).

INVERTi([seq(n!,n=1..20)]);
A003319 := proc(n) option remember; n! - add((n-j)!*A003319(j), j=1..n-1) end;
[seq(A003319(n), n=0..50)]; # N. J. A. Sloane, Dec 28 2011
series(2 - 1/hypergeom([1,1], [], x), x=0,50); # Mark van Hoeij, Apr 18 2013

a[n_] := a[n] = n! - Sum[k!*a[n-k], {k, 1, n-1}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Oct 11 2011, after given formula *)
CoefficientList[Assuming[Element[x,Reals],Series[2-E^(1/x)* x/ExpIntegralEi[1/x],{x,0,20}]],x] (* Vaclav Kotesovec, Mar 07 2014 *)
a[ n_] := If[ n < 2, 1, a[n] = (n - 2) a[n - 1] + Sum[ a[k] a[n - k], {k, n - 1}]]; (* Michael Somos, Feb 23 2015 *)
Table[SeriesCoefficient[1 + x/(1 + ContinuedFractionK[-Floor[(k + 2)/2]*x, 1, {k, 1, n}]), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Sep 29 2017 *)

{a(n) = my(A); if( n<1, 1, A = vector(n); A[1] = 1; for( k=2, n, A[k] = (k - 2) * A[k-1] + sum( j=1, k-1, A[j] * A[k-j])); A[n])}; /* Michael Somos, Jul 24 2011 */

{if(n<1,1,a(n)=local(A=x);for(i=1,n,A=x-x*A+A^2+x^2*A' +x*O(x^n));polcoeff(A,n))} /* Paul D. Hanna, Jul 30 2011 */

def A003319_list(len):
    R, C = [1], [1] + [0] * (len - 1)
    for n in range(1, len):
        for k in range(n, 0, -1):
            C[k] = C[k - 1] * k
        C[0] = -sum(C[k] for k in range(1, n + 1))
        R.append(-C[0])
    return R
print(A003319_list(21))  # Peter Luschny, Feb 19 2016

G.f.: 2 - 1/Sum_{k>=0} k!*x^k.
Also a(n) = n! - Sum_{k=1..n-1} k!*a(n-k) [Bowen, 1976].
Also coefficients in the divergent series expansion log Sum_{n>=0} n!*x^n = Sum_{n>=1} a(n+1)*x^n/n [Bowen, 1976].
a(n) = (-1)^(n-1) * det {| 1! 2! ... n! | 1 1! ... (n-1)! | 0 1 1! ... (n-2)! | ... | 0 ... 0 1 1! |}.
INVERTi transform of factorial numbers, A000142 starting from n=1. - Antti Karttunen, May 30 2003
Gives the row sums of the triangle [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] DELTA [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...] where DELTA is the operator defined in A084938; this triangle A089949. - Philippe Deléham, Dec 30 2003
a(n+1) = Sum_{k=0..n} A089949(n,k). - Philippe Deléham, Oct 16 2006
L.g.f.: Sum_{n>=1} a(n)*x^n/n = log( Sum_{n>=0} n!*x^n ). - Paul D. Hanna, Sep 19 2007
G.f.: 1+x/(1-x/(1-2*x/(1-2*x/(1-3*x/(1-3*x/(1-4*x/(1-4*x/(1-...)))))))) (continued fraction). - Paul Barry, Oct 07 2008
a(n) = -Sum_{i=0..n} (-1)^i*A090238(n, i) for n > 0. - Peter Luschny, Mar 13 2009
From Gary W. Adamson, Jul 14 2011: (Start)
a(n) = upper left term in M^(n-1), M = triangle A128175 as an infinite square production matrix (deleting the first "1"); as follows:
   1,  1,  0,  0,  0,  0, ...
   2,  2,  1,  0,  0,  0, ...
   4,  4,  3,  1,  0,  0, ...
   8,  8,  7,  4,  1,  0, ...
  16, 16, 15, 11,  5,  1, ...
  ... (End)
O.g.f. satisfies: A(x) = x - x*A(x) + A(x)^2 + x^2*A'(x). - Paul D. Hanna, Jul 30 2011
From Sergei N. Gladkovskii, Jun 24 2012: (Start)
Let A(x) be the g.f.; then
A(x) = 1/Q(0), where Q(k) = x + 1 + x*k - (k+2)*x/Q(k+1).
A(x) = (1-1/U(0))/x, when U(k) = 1 + x*(2*k+1)/(1 - 2*x*(k+1)/(2*x*(k+1) + 1/U(k+1))). (End)
From Sergei N. Gladkovskii, Aug 03 2013: (Start)
Continued fractions:
G.f.: 1 - G(0)/2, where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+2) - 1 + x*(2*k+2)/G(k+1))).
G.f.: (x/2)*G(0), where G(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1/2) + 1/G(k+1))).
G.f.: x*G(0), where G(k) = 1 - x*(k+1)/(x - 1/G(k+1)).
G.f.: 1 - 1/G(0), where G(k) = 1 - x*(k+1)/(x*(k+1) - 1/(1 - x*(k+1)/(x*(k+1) - 1/G(k+1)))).
G.f.: x*W(0), where W(k) = 1 - x*(k+1)/(x*(k+1) - 1/(1 - x*(k+2)/(x*(k+2) - 1/W(k+1)))).
(End)
a(n) = A233824(n-1) if n > 0. (Proof. Set b(n) = A233824(n), so that b(n) = n*n! - Sum_{k=1..n-1} k!*b(n-k). To get a(n+1) = b(n) for n >= 0, induct on n, use (n+1)! = n*n! + n!, and replace k with k+1 in the sum.) - Jonathan Sondow, Dec 19 2013
a(n) ~ n! * (1 - 2/n - 1/n^2 - 5/n^3 - 32/n^4 - 253/n^5 - 2381/n^6 - 25912/n^7 - 319339/n^8 - 4388949/n^9 - 66495386/n^10), for coefficients see A260503. - Vaclav Kotesovec, Jul 27 2015
For n>0, a(n) = (A059439(n) - A259472(n))/2. - Vaclav Kotesovec, Aug 03 2015
From Peter Bala, May 23 2017: (Start)
G.f.: 1 + x/(1 + x - 2*x/(1 + 2*x - 3*x/(1 + 3*x - 4*x/(1 + 4*x - ...)))). Cf. A000698.
G.f.: 1/(1 - x/(1 + x - x/(1 - 2*x/(1 - 2*x/(1 - 3*x/(1 - 3*x/(1 - 4*x/(1 - 4*x/(1 - ...))))))))). (End)
Conjecture: a(n) = A370380(n-2, 0) = A370381(n-2, 0) for n > 1 with a(0) = a(1) = 1. - Mikhail Kurkov, Apr 26 2024

More terms from Michael Somos, Jan 26 2000
Additional comments from Marcelo Aguiar (maguiar(AT)math.tamu.edu), Mar 28 2002
Added a(0)=0 (some of the formulas may now need adjusting). - N. J. A. Sloane, Sep 12 2012
Edited and set a(0) = 1 by Peter Luschny, Aug 03 2022

A109062 Triangle read by rows: number of atomic set compositions of size n and length k (see description in A095989) 1 <= k <= n.

Original entry on oeis.org

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

Mike Zabrocki, Aug 24 2005

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

			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;
  ...

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.

Row sums are equal to A095989, a(n,n) = A003319, a(n,2) = A000295.

Cf. A095989, A059438, A074664, A087903, A008277, A019538.

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);

G.f.: 1-1/(1+Sum_{n>=1} Sum_{k=1..n} q^n*t^k*Stirling2(n,k)*k!).

A136128 Number of components in all permutations of [1,2,...,n].

Original entry on oeis.org

1, 3, 10, 40, 192, 1092, 7248, 55296, 478080, 4625280, 49524480, 581368320, 7422589440, 102372076800, 1516402944000, 24004657152000, 404347023360000, 7220327288832000, 136227009945600000, 2707657158721536000, 56546150835879936000, 1237826569587277824000

Offset: 1

Emeric Deutsch, Jan 21 2008

nonn

			a(3) = 10 because the permutations of [1,2,3], with components separated by /, are 1/2/3, 1/32, 21/3, 231, 312 and 321.

Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 262 (#14).

Alois P. Heinz, Table of n, a(n) for n = 1..450
Yujia Kang, Thomas Selig, Guanyi Yang, Yanting Zhang, and Haoyue Zhu, On friendship and cyclic parking functions, arXiv:2310.06560 [math.CO], 2023-2024. See p. 13.
Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 5.

Cf. A003149, A059371, A059438.

seq(add(factorial(i)*factorial(n-i),i=0..n-1),n=1..20);
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n,
      (a(n-1)+(n-1)!)*(n+1)/2)
    end:
seq(a(n), n=1..23);  # Alois P. Heinz, Jun 13 2019

nn=20; p=Sum[n!x^n,{n,0,nn}]; Drop[CoefficientList[Series[p(p-1), {x,0,nn}], x], 1] (* Geoffrey Critzer, Apr 20 2012 *)
Table[(n + 1)! Re[-LerchPhi[2, 1, n + 1]], {n, 1, 20}]  (* Peter Luschny, Jan 04 2018 *)

a(n) = 2*sum(k=0, (n+1)\2, (4^k-1)*abs(stirling(n+1, 2*k, 1))*bernfrac(2*k)); \\ Seiichi Manyama, Oct 05 2022

a(n) = my(A = 1, B = 1); for(k=1, n, B *= k; A = (n-k+1)*A + B); A-B \\ Mikhail Kurkov, Aug 09 2025

def aList(n) -> list[int]:
    f, al, A = 1, 1, [1]
    for i in range(2, n + 1):
        f, al = f * i, (al + f) * (i + 1) >> 1
        A.append(al)
    return A
print(aList(22))  # Peter Luschny, Aug 09 2025

a(n) = A003149(n) - n!.
a(n) = A059371(n) + n! (n>=2).
a(n) = Sum_{k=1..n} k*A059438(n,k).
a(n) = Sum_{i=0..n-1} i!*(n-i)!.
a(n) = (n+1)!*(1 + Sum_{j=1..n-1} 2^j/(j+1))/2^n.
a(n) = (n+1)*a(n-1)/2 + (n-1)!*(n+1)/2, a(1)=1.
G.f.: f(f-1), where f(x) = Sum_{j>=0} j!*x^j.
a(n) = (n + 1)!*Re(-LerchPhi(2, 1, n + 1)). - Peter Luschny, Jan 04 2018
D-finite with recurrence: 2*a(n) +(-3*n+1)*a(n-1) +(n^2-3*n+4)*a(n-2) +(n-1)*(n-2)*a(n-3)=0. - R. J. Mathar, Jul 26 2022
a(n) = 2 * Sum_{k=0..floor((n+1)/2)} (4^k-1) * |Stirling1(n+1,2*k)| * Bernoulli(2*k). - Seiichi Manyama, Oct 05 2022
E.g.f.: x/((2-x)*(1-x)) - 2*log(1-x)/((2-x)^2). - Vladimir Kruchinin, Nov 16 2022

A263484 Triangle read by rows: T(n,k) (n>=1, 0<=k

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 7, 13, 1, 4, 12, 32, 71, 1, 5, 18, 58, 177, 461, 1, 6, 25, 92, 327, 1142, 3447, 1, 7, 33, 135, 531, 2109, 8411, 29093, 1, 8, 42, 188, 800, 3440, 15366, 69692, 273343, 1, 9, 52, 252, 1146, 5226, 24892, 125316, 642581, 2829325

Offset: 1

Christian Stump, Oct 19 2015

Row sums give A000142, n >= 1.
From Allan C. Wechsler, Jun 14 2019 (Start):
Suppose we are permuting the numbers from 1 through 5. For example, consider the permutation (1,2,3,4,5) -> (3,1,2,5,4). Notice that there is exactly one point where we can cut this permutation into two consecutive pieces in such a way that no item is permuted from one piece to the other, namely (3,1,2 | 5,4). This "cut" has the property that all the indices to its left are less than all the indices to its right. There are no other such cut-points: (3,1 | 2,5,4) doesn't work, for example, because 3 > 2.
Stanley defines the "connectivity set" as the set of positions at which you can make such a cut. In this case, the connectivity set is {3}.
In the present sequence, T(n,k) is the number of permutations of n elements with k cut points. (End)
Essentially the same triangle as [1, 0, 0, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 2, 2, 3, 3, 4, 4, 5, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 18 2020

			Triangle begins:
  1,
  1, 1,
  1, 2,  3,
  1, 3,  7, 13,
  1, 4, 12, 32,  71,
  1, 5, 18, 58, 177, 461,
  ...
Triangle [1, 0, 0, 0, 0, ...] DELTA [0, 1, 2, 2, 3, 3, ...]:
  1;
  1, 0;
  1, 1,  0;
  1, 2,  3,  0;
  1, 3,  7, 13,  0;
  1, 4, 12, 32, 71, 0;
... - _Philippe Deléham_, Feb 18 2020

Alois P. Heinz, Rows n = 0..150, flattened
FindStat - Combinatorial Statistic Finder, The cardinality of the complement of the connectivity set.
Mathematics Stack Exchange, Discussion of this sequence, June 2019.
Richard P. Stanley, The Descent Set and Connectivity Set of a Permutation, arXiv:math/0507224 [math.CO], 2005.

Cf. A000142.
T(n,n-1) gives A003319.
A version with reflected rows is A059438, A085771.
T(2n,n) gives A308650.

rows = 11;
(* DELTA is defined in A084938 *)
Most /@ DELTA[Table[Boole[n == 1], {n, rows}], Join[{0, 1}, LinearRecurrence[{1, 1, -1}, {2, 2, 3}, rows]], rows] // Flatten (* Jean-François Alcover, Feb 18 2020, after Philippe Deléham *)

# cf. FindStat link
def statistic(x):
     return len(set(x.reduced_word()))
for n in [1..6]:
    for pi in Permutations(n):
        print(pi, "=>", statistic(pi))

More terms from Fred Lunnon and Christian Stump

Name changed by Georg Fischer as proposed by Allan C. Wechsler, Jun 13 2019

Showing 1-10 of 17 results. Next

The main diagonal equals A075834 shift 1 place left; subsequent diagonals of this triangle are self-convolutions of the main diagonal. A075834 has the property that the n-th term of the n-th self-convolution of A075834 equals n!. The first (n+1) terms of the binomial transform of the n-th row forms the n-th row of triangle A059438 transposed, which has row sums equal to the factorials. A059438 is also formed from the self-convolutions of its main diagonal (A003319).

The partition transform (also called De Moivre polynomials by Cormac O'Sullivan) is defined in the program section as a Sage script.

The triangle represents a refinement of the number of irreducible permutations, A003319. Together with the refinement of the number of reducible permutations A356265 the triangle sums to the refinement of the factorial numbers given in A357079.

cp's OEIS Frontend

A059439 A diagonal of A059438.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

Formula

Extensions

A085771 Triangle read by rows. T(n, k) = A059438(n, k) for 1 <= k <= n, and T(n, 0) = n^0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

SageMath

Formula

A059440 A diagonal of A059438.

Views

Author

Keywords

References

Links

Formula

Extensions

A091063 Triangle, read by rows, such that the initial terms of the binomial transform of the n-th row forms the n-th row of triangle A059438 transposed (permutations of [1..n] with k components).

Views

Author

Keywords

Comments

Examples

Crossrefs

A357078 Triangle read by rows. The partition transform of A355488, which are the alternating row sums of the number of permutations of [n] with k components (A059438).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

A047999 Sierpiński's [Sierpinski's] triangle (or gasket): triangle, read by rows, formed by reading Pascal's triangle (A007318) mod 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A003319 Number of connected permutations of [1..n] (those not fixing [1..j] for 0 < j < n). Also called indecomposable permutations, or irreducible permutations.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs