All Questions
68
questions
2
votes
1
answer
3k
views
Count arrays with each array elements pairwise coprime
Given two integers $N$ and $M$ , How to find out number of arrays A of size N, such that :
Each of the element in array, $1 ≤ A[i] ≤ M$
For each pair i, j ($1 ≤ i < j ≤ N$)
$GCD(A[i], A[j]) = 1$...
1
vote
1
answer
310
views
number of possible subsets formed with odd count of odd numbers = $2^{n_{odd}-1} \cdot 2^{ n_{even}}$
Let $n_{odd}$ represents the number of odd numbers in the set $S$ and $n_{even}$ denote the number of even numbers. The total number of possible subsets formed with odd count of odd numbers $=2^{n_{...
1
vote
0
answers
64
views
Counting the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$, where $i < j$ and number of inversions is $k$.
How can I prove the following:
$d^{ij}(m,k) > d^{ji}(m,k)$ for all $k < \frac{1}{2}\binom{m}{2},$
where $d^{ij}(m,k)$ denotes the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$ ...
0
votes
1
answer
934
views
How many ways to line up n objects with distinct heights
Over winter break, I have been working on a few programming questions and I came across this one, which has me a bit stumped:
As you ponder sneaky strategies for assisting with the great rabbit ...
0
votes
1
answer
167
views
Can't get a correct signature of Entringer number
I am stuck with understanding Entringer numbers which:
E(n,k) are the number of permutations of {1,2,...,n+1}, starting with
k+1, which, after initially falling, alternately fall then rise.
...
2
votes
1
answer
1k
views
Positioning a number into ordered summands
I have a question that
"In how many ways can we position $6$ into ordered summands. As for example we can write $3$ as $(1,1,1),(1,2), (2,1)$ i.e $3$ ways. Is there any formula or any trick besides ...
8
votes
2
answers
697
views
How many numbers of length N(N is the number of digits) are possible
Given $N \le 10^9$, determine how many numbers of length $N$ are possible with the following constraint: the adjacent digits of the number should have an absolute difference of $1$.
For eg, for $N = ...
2
votes
2
answers
118
views
Count good sets with given conditions
We need to find the numbers of good sets in a sequence. The good set is:
A good set is a sequence of $P$ positive integers which satisfies the following 2 condition :
If an integer $L$ appears in a ...
2
votes
1
answer
143
views
Count permutations with given cost and divisbilty
I am given $N$ . We need to count such permutations of $N$ numbers with each element between $0$ to $9$ which satisfy following conditions :
Cost of permutation is less than or equal to given $M$. ...
3
votes
0
answers
129
views
Number of $n$-permutations for which ${\tau}^k = id$
I am curious about the formula(any closed form) for the number of $n$-permutations $\tau$ such that ${\tau}^{n-1} = id$. How about for the case ${\tau}^n = id$ ?
2
votes
1
answer
211
views
Select k no.s from 1 to N with replacement to have a set with at least one co-prime pair
Given $1$ to $N$ numbers. You have to make array of $k$ no.s using those no.s, where repetition of same no. is also allowed, such that at least one pair in that chosen array is co-prime. Find no. of ...
2
votes
1
answer
147
views
Numbers which are writable as a sum of permutation pairs
We say that $N$ is writable as a sum of permutation pair $\{a,b\}$ if $a+b=N$, $a\neq b$ and $a$ and $b$ are permutations of each other (e.g. $321 = 156 + 165 = 147 + 174 = ... $).
Looking at 3-digit ...
0
votes
1
answer
104
views
Count ways to sit men women in row of size K
Suppose we are given N men and M women.They are to sit in a row of size K such that no two women sit next to each other.What are the number of ways.
Like if suppose their are 3 men and 2 women and ...
2
votes
1
answer
128
views
Expected Value of this function
Let’s consider a random permutation p1, p2, …, pN of numbers 1, 2, …, N and Function F is calculated as F=(X[2]+…+X[N-1])^K, where
...
1
vote
1
answer
92
views
What is the maximum number of iterations before a sequence is repeated
$A = \{a,b,c,d,e\}$
$B = \{f,g,h\}$
$C = \{i,j\}$
$D = \{0,1,2,3,4,5,6\}$
Suppose a four-tuple is constructed by extracting one element from each set at each successive iteration. The stipulation ...