proposed

approved

editing

proposed

Cf. A000005, A007557, A307967, A307994, A308083, A319133.

allocated for Ilya Gutkovskiy

G.f. A(x) satisfies: A(x) = x + x^2 + x^3 + x^4 * (1 + Sum_{i>=1} Sum_{j>=1} A(x^(i*j))).

1, 1, 1, 1, 1, 3, 3, 6, 3, 11, 5, 15, 8, 19, 7, 36, 10, 31, 15, 60, 12, 56, 17, 97, 24, 72, 19, 170, 29, 94, 32, 229, 31, 156, 34, 334, 47, 182, 46, 471, 49, 218, 68, 658, 51, 314, 70, 797, 84, 354, 72, 1173, 93, 437, 98, 1353, 95, 576, 114, 1792, 131, 640, 116, 2243, 133

1,6

Shifts 4 places left when inverse Moebius transform applied twice.

a(1) = ... = a(4) = 1; a(n+4) = Sum_{d|n} tau(n/d)*a(d), where tau = number of divisors (A000005).

a[n_] := a[n] = Sum[DivisorSigma[0, (n - 4)/d] a[d], {d, Divisors[n - 4]}]; a[1] = a[2] = a[3] = a[4] = 1; Table[a[n], {n, 1, 65}]

Cf. A000005, A007557, A307994, A319133.

allocated

nonn

Ilya Gutkovskiy, May 11 2019

approved

editing

allocated for Ilya Gutkovskiy

recycled

allocated

reviewed

approved

proposed

reviewed

editing

proposed

Number of copies of S_k(0) in S_n for Type 4 adjacencies.

120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1

1,1

The current values are for n=15, k=1..15 for Type 4 adjacency.

Consider permutations over the alphabet {0,1,2,3,...,n-1}.

Let a permutation be A[1..n]. If A[i]+1 = A[i+1] then an adjacency of Type 1 exists.

Type 2 adjacency: In addition to Type 1 if A[n]=n-1 there is an adjacency (that A[n] forms with an imaginary A[n+1] that is presumed to be n).

Type 3 adjacency: In addition to Type 1 if A[1]=0 there is an adjacency (that A[1] forms with an imaginary A[0] that is presumed to be -1).

Type 4 adjacency: Union of Type 1, Type 2 and Type 3.

S_n(k) denotes the subset of S_n with exactly k adjacencies. A permutation \alpha in S_n(k) \emph{reduces} to a permutation in S_(n-k) that is a set of all permutations with n-k symbols without any adjacencies.

A permutation with no adjacencies is irreducibe or reduced. Otherwise, it is reducibe. A permutation \alpha in S_n(k) reduces to \beta in S_{n-k}(0) if \beta is obtained by eliminating all adjacencies in \alpha. For example, (3, 4, 1, 2, 0) in S_5 reduces to an irreducible permutation (2, 1, 0) in S_3. We consider all permutations in their reduced form. A block is the sub-list consisting of maximal number of consecutive adjacencies. In the above permutation we have 2 blocks: 3,4 and 1,2.

The process of eliminating adjacencies: Replace a block of adjacencies with its first symbol and reduce the value of all symbols greater than the last symbol by the number of adjacencies in the block. That is when 3,4 is processed then we obtain (3,1, 2, 0). Note that there are no symbols with value greater than 4. Likewise when 1,2 is further processed then we obtain (2, 1, 0). here when 1,2 is replaced with 1 then 3 is reduced by 1.

The cardinalities of S_n(k) under Type 2 and Type 3 are identical due to symmetry. We showed that a symmetric group with n symbols is a union of integral copies of S_k(0) for all k.

The number of copies of S_k(0) in S_n (k <= n) under Type 4 adjacencies

For n=15 through 20 we obtain the following rows:

120,560,1820,4368,8008,11440,12870,11440,8008,4368,1820,560,120,16,1

136,680,2380,6188,12376,19448,24310,24310,19448,12376,6188,2380,680,136,17,1

153,816,3060,8568,18564,31824,43758,48620,43758,31824,18564,8568,3060,816,153,18,1

137,969,3876,11628,27132,50388,75582,92378,92378,75582,50388,27132,11628,3876,969,171,19,1

156,834,4845,15504,38760,77520,125970,167960,184756,167960,125970,77520,38760,15504,4845,1140,190,20,1,

208,990,4047,20349,54264,116280,203490,293930,352716,352716,293930,203490,116280,54264,20349,5985,1330,210,21,1

B. Chitturi and Krishnaveni KS. (2016). Adjacencies in Permutations. arXiv preprint arXiv:1601.04469.

B. Chitturi. Computing cardinalities of subsets of $S_n$ with $k$ adjacencies, JCMCC, accepted: 2018.

a(n) = binomial(n-1, k-1) + 2* (Sum_{i=1..n-k} binomial(n-i-1, k-1)) + Sum_{i=1..n-k-1} Sum_{j=1..n-k-i} binomial (n-i-j-1, k-1).

(C++)

//Code: Please look at the third equation for Type 4.

#include<bits/stdc++.h>

#define ll long long

#define pb push_back

#define all(v) v.begin(), v.end()

#define mp make_pair

#define ff first

#define ss second

#define MAXN 1000005

using namespace std;

ll fact[21], f1[21][21], f2[21][21];

ll fun(ll n, ll r){

if(n==r||n==0||r==0)

return 1;

ll ans=fact[n];

ans/=fact[r];

ans/=fact[n-r];

return ans;

}

ll fun1(ll n, ll k){

if(f1[n][k]!=-1)

return f1[n][k];

ll ans=0;

for(int i=1; i<=n-k; i++){

ans+=fun(n-i-1, k-1);

}

return f1[n][k]=ans;

}

ll fun2(ll n, ll k){

if(f2[n][k]!=-1)

return f2[n][k];

ll ans=0;

for(ll i=1; i<=n-k-1; i++){

for(ll j=1; j<=n-k-i; j++){

//cout<<"qq"<<i<<" "<<j<<endl;

ans+=fun(n-i-j-1, k-1);

}

}

return f2[n][k]=ans;

}

ll ee(ll n, ll k){

ll ans=0;

ans+=fun(n-1, k-1);

ans+=2*fun1(n, k);

ans+=fun2(n, k);

return ans;

}

int main(){

ios::sync_with_stdio(false);

cin.tie(0);

ll ff=1;

fact[0]=1;

for(ll i=1; i<16; i++){

ff*=i;

fact[i]=ff;

}

memset(f1, -1, sizeof(f1));

memset(f2, -1, sizeof(f2));

for(int i=1; i<=15; i++){

for(int j=1; j<=i; j++){

cout<<fun(i-1, j-1)<<"\t"; // 1st Equation

//cout<<fun1(i, j)<<"\t"; // 2nd Equation

//cout<<ee(i, j)<<"\t"; // 3rd Equation

}

cout<<endl;

}

return 0;

}

nonn,changed

recycled

Bhadrachalam Chitturi, May 08 2019

proposed

editing

editing

proposed