For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
1answer
38 views

How many ways can an integer $i$ appearing in a sequence with multiplicty at least $j$, be minimal

Let us construct an integer sequence of length $n$, where the integers are chosen from $\{1, 2, ..., k\}$, with i.i.d. uniform probability $\frac{1}{k}$. I want to compute the probability ($p_{ij}$) ...
0
votes
1answer
21 views

Different sums by adding the currency.

How many different sums can be formed by the following $5$ dollar, $1$ dollar, $50$ cents, $25$ cents, $10$ cents, $3$ cents, $2$ cents, $1$ cent. As there are $8$ different things and at ...
6
votes
5answers
696 views

Given 5 integers show that you can find two whose sum or difference is divisible by 6.

I'm trying to solve this problem using the pigeon hole principle. When dividing an integer by 6 there are 6 different remainders, {0, 1, 2, 3, 4, 5}. Seeing as there are the same number of "holes" ...
2
votes
3answers
29 views

The number of times will an individual child goes to the cinema before a group is repeated.

$1.)$ A mother with $7$ children takes $3$ at a time to a cinema.She goes with every group of $3$ that she can form.How many times can she go to cinema with distinct groups of $3$ children? ...
2
votes
4answers
61 views

Random number function (counting)

I have task I can't get my head around, even with a suggested answer. You have a function the generates a random integer between $0 - 65535$. Your task is to generate random integers $125-525$ ...
2
votes
0answers
19 views

Euler Integral of a self-overlapping tube with a cusp singularity

I am studying in depth the following paper on Euler calculus applied to target enumeration: https://www.math.upenn.edu/~ghrist/preprints/eulerenumerationpart1.pdf Within this paper there is an ...
3
votes
0answers
31 views

Maximum difference between tails in absolute value

I toss a fair coin $n$ times. Some notation: $S_i=$ difference between #heads and #number of tails after the first $i$ tosses, $1\leq i\leq n$. $M_n=\max(S_1,S_2,\dots,S_n)$, ...
-8
votes
0answers
47 views

identity permutations [on hold]

I need some help with the following question : For the permuation $ π $ on n elements we define the term : $ π^k=i $ if the composition of π on it self k times is the identity permutation . (where ...
1
vote
0answers
39 views

Number of ways to put hat(s) in $5$ boxes.

If their are two kinds of hats , red and blue and at least $5$ of each kind, in how many ways can the hats be put in each in each of the $5$ different boxes. I assumed that their are $10$ hats ...
4
votes
3answers
57 views

Chart of Rounds for a Game

I need to solve the following problem for actual use. 10 people will be playing a game. They play the game 4 people at a time. Each time they play they garner points within the game. Each person ...
0
votes
0answers
32 views

Properties of Coefficients of Order Polynomials

I am working on a problem involving determining the order polynomial $\Omega_P(k)$ of a partial order $P$, which counts the number of order-preserving transformations/maps from $P$ to the $k$-chain ...
21
votes
3answers
646 views

Counting matchings, the modern way

A hundred years ago, if you had $k$ men and $k$ women and wanted to marry them all off in pairs, it was easy to see that there are exactly $k!$ ways to do that. Today, however, societal standards ...
1
vote
2answers
56 views

Find the Sum using bijection

Find the sum of $S=\displaystyle\sum_{i,j,k \ge 0, i+j+k=17} ijk$. I am looking for a solution that uses some bijection. I couldn't find any bijection. I am able to do the problem by other method by ...
3
votes
3answers
70 views

Simplifying $\sum_{i=0}^n i^k\binom{n}{2i+1}$

What is the formula for \begin{eqnarray}\sum_{i=0}^n i^k\binom{n}{2i+1}?\end{eqnarray} I tried to use the identity $$ ...
2
votes
2answers
33 views

How to prove that the subsets of $\mathbb{N}$ that don't contain arithmetic progressions of some length form closed sets of a topology?

I have exactly the same problem as this person, which I will rewrite below:Topology and Arithmetic Progressions. The reason I'm posting this is that I'm stuck at a later stage than the OP of that ...
-2
votes
0answers
63 views

the identity permutation [on hold]

for the permuation $ \pi $ on n elements we define the term : $ \pi^k=i $ if the composition of $ \pi $ on it self k times is the identity permutation . A. let $ a_n $ be the number of permutation of ...
1
vote
3answers
43 views

In how many ways can a student select six classes from three groups if they must take at least two from the first and second groups?

Question: Students at school can choose from 16 subjects to study for their Certificate. Seven of these subjects are in group I, six are in group II, and the other three are in group III. Students ...
2
votes
1answer
54 views

How to show $\binom{2n}{n} \ge \prod_{n < p \le 2n} p $?

What is the best way to show \begin{equation} \binom{2n}{n} \ge \prod_{n < p \le 2n} p \end{equation} for prime $p$. I know that $ 2^{2n} = (1+1)^{2n} \ge \binom{2n}{n}$. and \begin{equation} ...
2
votes
0answers
23 views

Submodular function, square of which is also submodular?

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ ...
4
votes
1answer
60 views

Each number in $S\subseteq \{1,\ldots,2n\}$ does not divide another one, with $|S|= n$. In how many ways?

Let $f(n)$ be the number of subsets $S\subseteq \{1,2,\ldots,2n\}$ such that $|S|=n$ and $a$ does not divide $b$ whenever $a,b \in S$ are distinct. Can we evaluate $f(n)$, at least asimptotically? ...
0
votes
0answers
26 views

Locks and Keys using permutation and combination [on hold]

This is a problem using permutations, combinations and factorial. There are four bankers in charge of a bank vault. We can not trust all of the bankers (2 of them are untrustworthy, we don't ...
1
vote
2answers
41 views

Probability that among 3 random digits two different one

I have been trying to solve the following problem: What is the probability that among 3 random digits, there appear exactly 2 different ones? The formula for no repititions is: ...
0
votes
0answers
22 views

How to enumerate (not count) combinations and permutations? [duplicate]

I’d like to ask if there is any formula or method to enumerate combinations and permutations such that if I know that there are X unique combinations/permutations, I could take a number between 1 and ...
2
votes
2answers
51 views

Two problems on combinatorics

Suppose we have a bag which has chips of four colors numbered $1$ to $13$, i.e. in total $52$ balls. Now what is the difference between these two problems. Problem-$1$- In how many ways can you ...
0
votes
0answers
40 views

What is the maximum value of $M$ when $T$ is set of $\{2,4,8,16,… 2^n\}$ and $S$ is subset of $T$ by given conditions

Qns $T$ is set of $\{2,4,8,16,... 2^n\}$ and $S$ is a subset of $T$ if the sum of no two elements of $S$ is greater than $2^n-2$. let $m$ be $M$ number of elements in $S$. what is ...
0
votes
2answers
37 views

Find the total number of selections of r things from n different things when each thing can be repeated unlimited number of times?

Find the total number of selections of r things from n different things when each thing can be repeated unlimited number of times ? I know that the formula is $$ n+r-1\choose r $$ But how do we get ...
2
votes
2answers
44 views

Is $P(n) = \frac{a n }{b}$ or $\frac{(a+1) n}{b + 1}$?

I investigated Some random data and I was a bit confused. Could be Mathematical coincidence but i'm not sure. Consider the integers $1,2,3,...,a$ Randomly Pick $b$ dinstinct element out of them. ...
1
vote
1answer
30 views

Chessboard pawns arrangement clarification

I have a 8 X 8 chessboard, and 8 identical pawns. These pawns are arranged at random. What is the probability that the pawns are arranged in such a way that each row and column have only one pawn? My ...
0
votes
0answers
34 views

Comparison of entries of a real matrix

Let $A$ be an $m$ by $n$ real matrix and let $p$, $q$ be positive integers with $p\leq n$, $q\leq m$. In $A$, mark $p$ smallest entries of each row with red color and mark $q$ smallest entries of each ...
6
votes
4answers
255 views

How to closed the sum $\displaystyle \sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$

How to closed the sum $\displaystyle S=\sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$ I'm trying divide two cases $n$ odd and $n$ even. I predict that ...
3
votes
2answers
102 views
+100

find a group of lowest N numbers so that no 2 pairs have the same bitwise or

I am trying to find the lowest group of N numbers (i.e. N=1000) so that no 2 pairs from the group have the same bit-wise or. more specific need to find a group $A = \{a_1,a_2,a_3,..,a_N\} $ such ...
1
vote
2answers
402 views

ln how manyways can we distribute $7$ apples and $6$ oranges among $4$ children so that each child gets at least one apple.

In how many ways can we distribute $7$ apples and $6$ oranges among $4$ children so that each child gets at least one apple? I think this can be solved by using permutations because the word ...
2
votes
3answers
108 views

Probability that the eventually a six on a dice will appear.

Dave rolls a fair six-sided die until a six appears for the first time. Independently, Linda rolls a fair six-sided die until a six appears for the first time. Let $ m$ and $ n$ be relatively prime ...
5
votes
2answers
66 views

Average length of a cycle in a n-permutation

What is the average length of a cycle in a permutation of $\{1,2,3,\dots ,n\}$?
2
votes
3answers
333 views

What are the basic generating functions?

What are the basic generating functions? (if there is one's). And what is the generating function of: $$1 + 2x^2 + 3x^4 + 4x^6 + \cdots $$ Thanks.
0
votes
2answers
77 views

How many pairs $(m, n)$ exist?

For certain pairs $ (m,n)$ of positive integers with $ m\ge n$ there are exactly $ 50$ distinct positive integers $ k$ such that $ |\log m - \log k| < \log n$. Find the sum of all possible ...
6
votes
3answers
93 views

Proving $\binom{n}{m}+2\binom{n-1}{m}+…+(n-m+1)\binom{m}{m} = \binom{n+2}{m+2}$

For $m,n\in\mathbb{N},\;n\geq m$, prove the following: $$ \tag{i}\binom{n}{m}+\binom{n-1}{m}+\binom{n-2}{m}+......+\binom{m}{m} = \binom{n+1}{m+1} $$ $$ ...
1
vote
0answers
26 views

Is there a good way to break down the order of the centraliser in a symmetric group?

I recently rediscovered the rather nice formula for the order of the centraliser of a permutation in the symmetric group and its realtionship with conjugacy classes. I wondered whether we could say ...
1
vote
0answers
14 views

Number of ways of contraction of N (N is even) three-index tensors?

Suppose I have N (N is even) three-index anti-symmetric tensors, I need to calculate the number of ways of total contractions. There are several constraints: The indexs of the same tensors cannot be ...
1
vote
1answer
1k views

what is maximum number of points of intersection between the diagonals of a convex octgon?

What is the maximum number of points of intersection between the diagonals of a convex octagon (8-vertex planar polygon)? Note that a polygon is said to be convex if the line segment joining any two ...
0
votes
1answer
38 views

How to solve this using set theory? [on hold]

Of the 38 people in my office, 10 like to drink chocolate, 15 are cricket fans, and 20 neither like chocolate nor like cricket. How many people like both cricket and chocolate?
1
vote
3answers
61 views

Combinatorial Proof of a Simple Identity

Consider the following identity: $\binom n r = \frac n r \binom {n-1} {r-1}$ where $n \ge r \ge 1$. It's easy to supply an algebraic proof, but I'm looking for a combinatorial proof. I tried the ...
5
votes
4answers
179 views

Make $n$ cents with $1$-cent, $2$-cent, and $3$-cent coins

I encountered the following problem in Herber Wilf's book Generatingfunctionology: Prove that, in country that has $1$-cent, $2$-cent, and $3$-cent coins only, the number of ways of changing ...
-5
votes
0answers
39 views

Non repeatable combinations [on hold]

There are 10 girls and 15 boys in class. They're preparing zumba dance for the final show. The teacher decided that boys are doing better and only boys will play 3 zumba dances. Every each of them ...
0
votes
0answers
44 views

Product of +1 and -1 with all combinations

I am looking for an algorithm or a smart way to do this in excel. I have this table. ...
-1
votes
1answer
85 views

partitions of the number n

I'm having difficult with the following question : show that the number of partitions of n into parts of size 3,5,7,9,... equals to the number of partitions of n into different parts which are not ...
-4
votes
0answers
21 views

groups of colors in a colorful cube - combinatorics [closed]

find natural number n, such that in every paint of a cube $$ 2^{[n]} $$ with the seven colors of the rainbow : a) there is 3 different groups $$ A, B , A \cap B $$ with the same color b) there is 3 ...
1
vote
2answers
30 views

Further Improvised Question: Combination of selection of pens

Following from my first improvised question here and the two excellent answers given, here's another twist to the question. What happens if the total number of pens to be selected is $15$ instead of ...
0
votes
0answers
18 views

Upper limit on Ramsey number $R(a,b)$

How could we prove that if $R(a-1,b)$ and $R(a,b-1)$ are both even then $R(a,b)$ is strictly less than $R(a-1,b)+R(a,b-1)$ or $\begin{equation} R(a,b) < R(a-1,b)+R(a,b-1) \end{equation}$
1
vote
2answers
25 views

Combinations question related to cards game

In how many ways can a player get 4-4-3-2 (4 cards from 1 suite, 4 cards from one suite, 3 cards from one suite and 2 cards from the last suite)? I calculated this way, but my answer is supposed to ...