cp's OEIS Frontend

Number of compositions of n+1 containing exactly one 1. - Emeric Deutsch, Mar 08 2002

Number of permutations with one fixed point avoiding 231 and 321.

A singleton is a run of length 1. - Michael Somos, Nov 29 2014

Second column of A105422. - Michael Somos, Nov 29 2014

Number of weak compositions of n with one 0 and no 1's. Example: Combine one 0 with the compositions of 5 without 1 to get a(5) = 8 weak compositions: 0,5; 5,0; 0,2,3; 0,3,2; 2,0,3; 3,0,2; 2,3,0; 3,2,0. - Gregory L. Simay, Mar 21 2018

Column 2 of A105422.

Row n has 1+floor(n/2) terms. Row sums yield the factorials (A000142). Sum(k*T(n,k),k>0)=n!/2 for n>=2. - Emeric Deutsch, Feb 17 2006

The array T(n,k) is the number of unmarked circular binary words (necklaces) of length n having exactly k occurrences of 00 (n >= 0 and 0 <= k <= n). Let V(n,k) be the number of marked circular binary words of length n with exactly k occurrences of the pattern 00 provided wrapping around the circle is allowed when n=1. More precisely, when n=1, we allow the string to wrap around itself on the circle to form a circular string of length 2. It turns out that V(n,k) = A119458(n,k). The properties of the array V(n,k) were studied by Carlitz and Scoville (1977).

Both for this array and for array V(n,k) = A119458(n,k) we have T(n=1, k=0) = T(n=1, k=1) = V(n=1, k=0) = V(n=1, k=1) = 1, which means in both arrays we (indirectly) assume that the string 0 has one occurrence of the pattern 00 (if allowed to wrap around itself on the circle only once), while the string 1 has zero occurrences of the pattern 00.

It makes sense to define T(n,k) = 0 = V(n,k) when k > n. Using the theory in Flajolet and Soria (1991), Flajolet and Sedgewick (2009), and Hadjicostas and Zhang (2018), we can prove that the g.f. of the numbers T(n,k) is F(z,t) = Sum_{n >= 0, k >= 0} T(n,k)*z^n*t^k = 1 - Sum_{d>=1} (phi(d)/d)*log(1-A(z^d,t^d)) while the g.f. of the numbers V(n,k) is K(z,t) = 1 - z*(d(1-A(z,t))/dz)/(1-A(z,t)), where A(z,t) = z*(t+1) + z^2*(1-t). (The latter g.f. was proved in Carlitz and Scoville (1977).)

We can also prove that T(n,k) = (1/n)*Sum_{d|gcd(n,k)} phi(d)*V(n/d, k/d) for n>=1 and 0 <= k <= n.

For k=0, we get that T(n, k=0) = A000358(n) and V(n, k=0) = A000204(n) and for n >= 1. To get univariate g.f.'s of the sequences (T(n,k): n >= 1) and (V(n, k): n >= 1) when k >= 1, we have to differentiate the previous two g.f.'s k times with respect to t, set t=0, and divide by k!. (Obviously, the log now disappears from the g.f. of T(n,k).)

For k=1, we get T(n, k=1) = A212804(n-1) = A006490(n)/n and V(n, k=1) = A006490(n) for n >= 1.

For k=2, we get T(n, k=2) = (1/n)*(V(n,2) + I(2|n)*V(n/2,1)) for n >= 1, where I(2|n) = 1 if 2|n, and 0 otherwise. Also, V(n, k=2) = A006491(n-1) for n >= 1 (with A006491(0) := 0).

For k=3, we get T(n, k=3) = (1/n)*(V(n,3) + 2*I(3|n)*V(n/3, 1)) for n >= 1. Also,

V(n, k=3) = A006492(n-2) for n >=1 (with A006492(m) = 0 for m = 1, 2). To get the g.f. for (T(n,k=3): n >= 0), we differentiate F(z,t) three times w.r.t. t, set t=0, and divide by 3! = 6. We get: 2*z^3*(1-z^3)/(3*(1-z^3-z^6)) + z^3*(1-z)^3/(3*(1-z-z^2)^3) = z^3 + 0*z^4 + z^5 + z^6 + 3*z^7 + 5*z^8 + 11*z^9 + 19*z^10 + 36*z^11 + 67*z^12 + 122*z^13 + 222*z^14 + ...

For 0 <= k <= n, T(n,k) - I(k=0) is the number of cyclic compositions of n with exactly k ones, where I(k=0) is 1 if k=0, and 0 otherwise. This can be proved using MacMahon's bijection between binary necklaces of length n and (unmarked) cyclic compositions of n. (We exclude the binary necklace consisting only of 1's, and that is why we need the term I(k=0).)

Given a binary necklace of 0's and 1's with length n (with at least one 0), starting with a 0 and going clockwise, let b_1 be the number of 1's until before the next zero plus one (for the initial 0); starting with the next zero, let b_2 be the number of 1's plus one (for the 2nd 0); continue this process until you reach the last 0 (say the m-th 0), and denote by b_m the number of 1's plus one before the first 0. Then b_1 + b_2 + ... + b_m is a cyclic composition of n. The process can be reversed (since b_1, b_2, ..., b_m >= 1). The only necklace that cannot be obtained from a cyclic composition is the one having all 1's, which we exclude. In the above process, b_i = 1 if and only if the i-th 0 in the above process is followed by 0 (to the right of it on the circle). Hence, for 0 <= k <= n, T(n,k) - I(k=0) is the number of cyclic compositions of n with exactly k ones.

Note that array A105422(n,k) is the linear version of this array: A105422(n,k) is the number of (linear) compositions of n having exactly k parts equal to 1. The denominator of the bivariate g.f. of array A105422(n,k) is indeed 1 - A(z,t), where A(z,t) = z*(t+1) + z^2*(1-t) (see above), and this is no coincidence.

More generally, the g.f. for the number of compositions such that part m occurs with even multiplicity is (1-x)/(1-2*x)*(1-2*x+x^m-x^(m+1))/(1-2*x+2*x^m-2*x^(m+1)). - Vladeta Jovovic, Sep 01 2007

From Gus Wiseman, Oct 05 2022: (Start)

Conjecture: Also the number of integer compositions of 2n + 1 with the same length as reverse-alternating sum. Here, the reverse-alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^i y_i. For example, the a(4) = 20 compositions are:

(135) (234) (333) (432) (531)

(11115) (21114) (31113) (41112) (51111)

(11214) (21213) (31212) (41211)

(11313) (21312) (31311)

(11412) (21411)

(11511)

This is the odd-indexed version of A357182, and the corresponding unordered count (partitions) is A357488.

(End)

Sum of entries in row n = 2^{n-1} = A011782(n) (n>=1).

Sum(kT(n,k), k>=0) = (3n+5)*2^{n-4} = A106472(n-1) (n>=3).