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)

0
votes
0answers
34 views

Find number of distinct arrays [duplicate]

We are given an array $[a_1,a_2,\dots,a_n]$ Define an operation : select any one element of array and multiply by $-1$ We apply this operation $x$ times. How many distinct arrays we can get after ...
4
votes
3answers
65 views

Prove that there is $[e ~(b-1) ~(b-1)!]$ natural numbers with no repeating digits in base $b$

For example, in base $2$ we have exactly $2$ of them (not counting zero): $$1,~10$$ In base $3$ we have $10$ (if I'm correct): $$1,2,10,12,20,21,102,120,201,210$$ By observation of these simple ...
2
votes
4answers
59 views

Probability of being dealt four-of-a-kind in a set of $5$ cards?

You are dealt a hand of five cards from a standard deck of playing cards. Find the probability of being dealt a hand consisting of four-of-a-kind. If possible, please provide a hint first before ...
2
votes
5answers
102 views

Sum of combinatorics sequence $\binom{n}{1} + \binom{n}{3} +\cdots+ \binom{n}{n-1}$

I need to find sum like $$\binom{n}{1} + \binom{n}{3} +\cdots+ \binom{n}{n-1},\qquad \text{ for even } n$$ Example: Find the sum of $$\binom{20}{1} + \binom{20}{3} +\cdots+ \binom{20}{19}=\ ?$$
2
votes
0answers
58 views

Counting divisions of an $n \times n$ grid [duplicate]

I'm looking for an efficient way to count the number of ways $D_n$ to divide an $n \times n$ grid into four (possibly empty) regions: top left, top right, bottom left and bottom right, such that no ...
2
votes
2answers
20 views

Bound on chromatic numbers of union of graphs

If I have a vertex-set $V$ and two graphs $G, H$ on $V$, it is easy to show that the chromatic number $\chi (G \cup H) \leq \chi (G) \chi (H)$. My question now is, whether $\chi (G \cup H) \leq \chi (...
1
vote
1answer
126 views

Generating ordered combination of numbers [closed]

I can form numbers with only 0,2,4,6,8. The sequence is as follows 0,2,4,6,8,20,22,24,26,28,40,42,..... How to generate an ordered sequence of numbers from combinations of 0,2,4,6,8.
3
votes
2answers
107 views

Two partitions of $\{ 1, 2, 3, 4, 5, 6, 7, 8, 9\}$

I recently stumbled upon the following problem, and I have no idea how to proceed. Let $S=\{1, 2, 3, 4, 5, 6, 7, 8, 9 \}.$ Let $P_1, P_2$ be partitions of $S$. For $x \in S$, let $\pi_1(x)$ be the ...
1
vote
1answer
30 views

Invariants/monovariants: numbers on a board

The numbers from $1$ through $2008$ are written on a blackboard. Every second, Dr. Math erases four numbers of the form $a, b, c, a+b+c$, and replaces them with the numbers $a+b, b+c, c+a$. Prove ...
0
votes
1answer
34 views

Question based on $n$ sided regular polygon.

Given $n$ sided regular polygon $(a)$ Total number of $\triangle$ formed in which none of the sides are the sides of that polygon $(b)\; $Total number of equilateral $\triangle$ formed in ...
5
votes
2answers
88 views

Determine $\frac{f''(\frac{1}{2})}{f'(\frac{1}{2})}$ if $f(x) = \sum_{k=0}^{1000} \ {2015 \choose k}\ x^k(1-x)^{2015-k}$

Problem : Determine $\frac{f''(\frac{1}{2})}{f'(\frac{1}{2})}$ if $f(x) = \sum_{k=0}^{1000} \ {2015 \choose k}\ x^k(1-x)^{2015-k}$ Trying to simply brute force the problem, yields the following ...
5
votes
2answers
75 views

What are permutable equivalence relations intuitively?

What are permutable equivalence relations, and what are they used for? What is the idea behind them? Could someone give me an example and a counterexample for finite sets? I have encountered the ...
3
votes
1answer
30 views

Distribution such that the total number of balls of any five consecutive boxes is always the same.

Consider one the distribution of balls in boxes numbered from 1 to 2016. Assume that the distribution is such that the total number of balls of any five consecutive boxes is always the same. In the ...
0
votes
0answers
18 views

Enumerating (some) combinations of elements subject to a constraint

Consider this variant of the knapsack problem: I own an outdoor goods store, and hikers come from miles around because of my amazing variety of products for sale. There are 4 popular hikes in the ...
2
votes
2answers
52 views

Combinatorics: Probability of Finding a Particular Set from a Random Source

I have a problem that I want to solve involving marking neurons in a brain; however, for simplicity I have decided to frame the question in the form of ice cream flavors. A nice piece of background is ...
1
vote
0answers
99 views

Finding total number of multi-sets

I am provided with a multi-set, let's say S with elements as [num1, num2, num3] and these elements are integers (both negative as well as non negative). As this is a multi-set, elements in the multi-...
2
votes
1answer
28 views

creating a balanced gray code with digits of different parity

I have some code that generates all combinations from something like this: [the or a] and [angry or mad or furious] and [cat or feline] to this: ...
4
votes
1answer
47 views

Directing graph such that any outdegree would be at most 2

Let $G=(V,E)$ graph. Suppose that for every subgraph $G'=(V',E') , G' \subset G, |E'| \le 2|V'|$. Show it's possible to direct G such that any outdegree would be at most 2. I tried proving it by ...
1
vote
1answer
48 views

Probability of Selecting Jars

I have 20 jars, and 15 jars have 2 balls each while 5 jars have 1 ball each. If, from the 35 balls, I select 30 at random, what's the probability that I have sampled x (15, 16, etc.) number of jars (...
3
votes
3answers
194 views

combinatoric sum (generating functions)

Given the generating functions: $f(x) = (1-x)^r = \Sigma_{i=0}^\infty a_i x^i$ $g(x) = \frac{1}{(1-x)^{r+1}} = \Sigma_{i=0}^\infty b_i x^i$ $h(x) = f(x) \cdot g(x) = \frac{1}{1-x}$ The factor of $...
1
vote
3answers
51 views

For how many weeks can I group my students?

I thought of an interesting question that I don't know how to solve. I imagine there are numeric results out there somewhere, but I don't know if this question has a formal name; if anyone could link ...
0
votes
1answer
23 views

Colexiographic ordering problem

I have two vectors, $(b_1,\cdots,b_k)$ and $(ms_1,\cdots,ms_{2^k})$. Let $\overline{b_l} = (1-b_l)$ be the falsity term of $b_l$. As an example consider $k=3$, then the ordering I require is: $m_1 = ...
3
votes
2answers
36 views

$3$ digits numbers in which digits are repeated.

Total number of $3$ digit number which can be formed by using the digits $1,2,3,4,3,2,1$ $\bf{My\; Try::}$ Total no. of $3$ digits numbers in which exactly $2$ digits are identical, are $112,113,...
6
votes
1answer
59 views

Orthogonal combinatoric sum

I have verified this identity in Matlab: $$ \sum_{k=m}^n~(-)^{n+k}\frac{2k+1}{n+k+1}\binom{n}{k}\binom{n+k}{k}^{-1}\binom{k}{m}\binom{k+m}{m}=\delta_{nm} $$ Where $n, m$ are positive integers. It was ...
1
vote
0answers
26 views

Is there a probabilistic proof of Erdős-Szekeres theorem?

I was talking about the Erdős-Szekeres theorem, which states that in a sequence with $mn+1$ terms, there either exists a monotonically increasing subsequence with length $m+1$ or a monotonically ...
1
vote
1answer
334 views

Ramsey number $R(n,n) > (n-1)^2$

I got an home work assignment, prove that: $R(n,n) > (n-1)^2$ Note that I saw on Wikipedia that for subgraph of $K_n$ with k vertices, $R(k,k) > 2^{k/2}$. I tried to work with that, but ...
4
votes
1answer
104 views

number of labeled trees with n vertices

How many labeled trees with $n$ vertices exist such that their degree is $1$ or $3$? I succeeded to get a range but not a particular answer. EDIT the range I found: $$\frac{n-2}{2^n}\lt\text{ ...
0
votes
3answers
38 views

Combinations of $6$ labeled balls in $4$ labeled boxes with an “extra” condition

I'm not good at maths and my school days happened a long time ago. I'm wondering how many combinations of $6$ labeled balls in $4$ labeled buckets can be. Also (if you can answer it thus it's not ...
0
votes
1answer
35 views

no of ways of dividing 2n people into 2 groups [closed]

Find the ways to divide 2n people into two groups each of n people such that two people are always in different groups.
1
vote
1answer
37 views

Prove : Each distinct $R_{k,e}$ can appear maximum $\sqrt b \leq n^{3}$ times.

Notation: $H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...
1
vote
1answer
43 views

Inclusion-Exclusion principle and finite product identity

On this page, there is a proof that uses the inclusion-exclusion principle to provide a formula for the value of Euler's totient function. I would be grateful if someone could explain the reasoning ...
0
votes
2answers
17 views

Compute the $3$-Combinations for a $4$-digits set

Consider we have $4$ digits. We want to compute the $3$ digit combinations of these $4$ digits ($1-2-3-4$). From the formula, we have: $$\frac{n!}{k!(n-k)!} = \frac{4!}{3!1!} = 4$$ but when I try ...
0
votes
2answers
40 views

Amount of possible passwords 8 characters long, with at least 1 number, no more than 3 repeating letters

What is the number of possible passwords that are 8 characters long, with at least 1 number, and no more than 3 repeating letters? How would you go about calculating this? Examples of invalid ...
1
vote
1answer
28 views

colorings with exactly $k$ color changes

There are $n$ distinct/distinguishable beads arranged in a circle. Let's color each bead either black or white with probability $1/2$ independently. What is the probability that there are exactly $k$ ...
2
votes
2answers
242 views

Having trouble with a combinatorial problem.

The problem is as follows: 10 teams divided into 2 groups 5 teams each are participating in a competition. The order of groups and teams doesn't matter. In how many ways can the teams be aranged. My ...
2
votes
1answer
29 views

Lexicographic index of strings with repeated characters

As the title says, I need to find a way (or a function, specifically) to convert a string, let's say $AABACCAB$, to it's lexicographic number among its permutations. The number of different words ...
2
votes
2answers
39 views

Number of possible routes through n countries and 2n cities, with restrictions

Someone is planning a round-the-world trip that involves visiting $2n$ cities, with two cities from each of $n$ different countries. He can choose a city to start and end the journey in, with ...
2
votes
0answers
33 views

Number of linear orderings of a set to have balanced frequencies of triple orders

Let $S$ be a set of $n$ elements and let $Q = (s_1, s_2, \ldots, s_n)$ be an ordering of $S$. We write $s_i <_Q s_j$ when $s_i$ appears before $s_j$ in $Q$. I want to construct a set (or possibly ...
2
votes
3answers
35 views

Number of permutations in $S_{30}$ with $\pi(2)<\pi(3)$

I am trying to find the number of permutations in $S_{30}$ with $\pi(2)<\pi(3)$. I worked out the answer as: $28!\times (1+2+\cdots+29)$. My reasoning is: suppose $\pi(2) = 1$ then there are $29$ ...
1
vote
2answers
48 views

All the 7-digit numbers containing each of the digits 1, 2, 3, 4, 5, 6, 7 exactly once, and not divisible by 5

All the 7-digit numbers containing each of the digits 1, 2, 3, 4, 5, 6, 7 exactly once, and not divisible by 5, are arranged in the increasing order. Find the 2000-th number in this list. My try: ...
3
votes
1answer
46 views

Prove existence of a triangle with least angle $\leq 30$ degrees

Problem: Let $A$ be a set of $6$ points in a plane such that no $3$ are collinear. Show that there exist 3 points in $A$ which form a triangle having an interior angle not $30$ degrees. I am supposed ...
0
votes
1answer
34 views

Permutations of n distinct objects in r groups, given that some objects may not be able to go into some groups?

For example, let's say there are groups A, B and C and objects 1, 2 and 3. Objects 1 and 2 can go in groups A, B and C, but object 3 is only allowed in groups A and B. How many different ways can the ...
0
votes
0answers
270 views

seating at two round tables

We have $n$ people sitting in two round tables like the picture. We randomly change the place of the people we decide two of them and change their places. We can only change the place of the ...
5
votes
2answers
35 views

At least how many students like all the activities?

I used Venn diagrams to solve the problem. It took me quite a while to find out the answer, and the answer is different from answer sheet. What is an easy way to solve the problem without getting lost ...
2
votes
0answers
39 views

Coloring (W-L Method)

I am trying to read An Optimal Lower Bound on the Number of Variables for Graph Identification. On page 3 (4th paragraph), it is written- It might color vertices and edges implicitly by using $k$-...
3
votes
0answers
99 views

Using Group Theory to Solve this IMO problem

A few weeks ago, I found a fascinating solution to a USAMO combinatorics problem that used group theory. Look at the 2nd solution on this link to view it. I think there might be a way to use group ...
5
votes
1answer
61 views

Find all whole number solutions of the following equation

While training for a math olympiad(university level) I stumbled upon the following problem. Find all $n, k \in \mathbb{N}$ such that $${ n \choose 0 } + {n \choose 1}+{n \choose 2} + {n \choose 3} = ...
0
votes
0answers
29 views

Combinatorics of classifying objects.

Given a multiset of $n$ primes (with product of multiset less than $2^{n\log n}$) how many ways can we assemble them into $k$ composite number of equal size? I am looking for asymptotics.
1
vote
0answers
24 views

Lower bound of DNF terms count for some symmetric boolean function

Consider boolean function $s_n^{[r,\,n - r]}\colon \{0,1\}^n\rightarrow\{0,1\}$ defined as follows: $$ s_n^{[r,\,n - r]}(x_1, ..., x_n) = 1 \iff |\{x_i: x_i = 1\}| \in [r,\,n - r] $$ (in other words,...
3
votes
3answers
139 views

Problem solving a word problem using a generating function

How many ways are there to hand out 24 cookies to 3 children so that they each get an even number, and they each get at least 2 and no more than 10? Use generating functions. So the first couple ...