This tag is for basic 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 (5)

1
vote
5answers
229 views

How many permutations of {1,2,…, 9} are there that do not start or end with an even number?

How many permutations of $$1,2,..., 9$$ are there that do not start or end with an even number? This is my attempt Condition 1 [Starts with even] => $$4 * 8!$$ Condition 2 [Ends with even] => $$4 * ...
2
votes
2answers
63 views

how many ways to go from place a to place b through 9 squares

Please see the image. How many ways are there from M to N without passing through the sqaure more than once... I counted upto 6 ways...is it the right answer??
0
votes
2answers
58 views

Who can not sit in middle if $A$ is not near $B$ and $C$ is beside $D$

Five people, $A,B,C,D,E$, are sitting in a row. $A$ is not near $B$. $C$ is beside $D$. Who can NOT sit in the middle? There are $5!=120$ combinations, that much I understood. But how do I answer the ...
0
votes
1answer
42 views

Probability - using combinations (C)

of 8 equal candidates for a job, 3 are qualified accountants, 4 are graduates and 2 have neither of these qualifications. Find: a) the probability a graduate get a job b) given that the qualified ...
2
votes
0answers
27 views

Perfect Matchings in Biclique Decompositions of Multigraphs

suppose you have the $K_{2n}$ covered by a multigraph consisting of $2n-1$ bicliques, each consisting of a partition of the vertex set into two sets of equal size. Here is a picture of $K_{6}$ with 5 ...
0
votes
1answer
28 views

How many $(A,B,C,D)$ exist?

Given $|X|=n$, how many $(A,B,C,D)$ exist if $C \cap B=C \cap D= B\cap D =\varnothing$, $A \subset B$, $B \cup C \cup D =X$?
0
votes
1answer
24 views

Number of permutations, basic question

What are the number of permutations in the following simple case: John has a wardrobe with: $3$ trousers $2$ shirts $2$ pairs of socks $4$ vests $4$ pairs of gloves $5$ jackets Every morning John ...
4
votes
0answers
64 views

Tao's proof of Szemeredi-Trotter theorem on incidences

In Tao's proof of Szemeredi-Trotter theorem on Point-Line incidences , he uses a lemma which decomposes the real plane into cells. During the proof of this lemma, the final step of getting rid of the ...
0
votes
2answers
45 views

Couple of Counting (how many ways) questions.

1.If I have a group of 10 seats reserved for people, and there are n=>10 total people, how many ways are there to choose who gets the 10 seats? for ex:If there was a definite number of people lets ...
0
votes
1answer
1k views

How many different two digit positive integers can be formed From the digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

How many different two digit positive integers can be formed From the digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. (i) When repetition is not allowed (ii) When repetition is allowed.
1
vote
0answers
15 views

What is the chance a random set of length L will be repeat itself in a random set of length M, where each number has X possible values?

The numbers within each set has X possible values (so X=100 means numbers run from 0..99). Say I have a set of random numbers of length M (say M=1000). What are the chances a random set of length L ...
0
votes
2answers
129 views

Determine the number of positive integer x where x<= 9,999,999 and the sum of the digits in x equals 31.

Determine the number of positive integer x where $$x\le 9,999,999$$ and the sum of the digits in x equals 31 How do you approach this question? TEXTBOOK SOLUTION: Let x be written in base ...
1
vote
0answers
24 views

Prove that if $k^2=o(n)$, then $n(n-1)(n-2)…(n-k+1) \approx n^k$

Prove that if $k^2=o(n)$, then $n(n-1)(n-2)...(n-k+1) \approx n^k$ Do I start by dividing both sides by n^k and collecting terms, perhaps? Not sure. Not entirely sure about the relevance of ...
3
votes
0answers
52 views

News on SG values of Grundy's Game?

Is there any recent research into the Sprague-Grundy values of Grundy's game? It was calculated to $2^{35}$ integers but with no sight of recurrence. Has anyone come up with anything new to compute ...
2
votes
0answers
32 views

Covering the square with “crosses”.

The problem concerns covering the unit square with translates of a specific figure, which I will refer to as a "cross", using as few translates as possible. The difficulty seems to result from the ...
3
votes
0answers
61 views

How to calculate the number of automorphisms of this set.

Let $N = \{1,2,\dots,n\}$ and define the set of functions $$X = \{ f:N \longrightarrow N : f(i) \leq i\}$$ Similarly let $S_n$ (the usual symmetric group on $n$ elements) act on $N$ by permuting ...
-1
votes
3answers
60 views

Solve the following equation with combinatorics…

Please , can you help with this exercise with combinations , I have no idea: Find $n$ such that $\mathrm{C}^3_n=\mathrm{C}^{12}_n$.
0
votes
2answers
22 views

Probability and distinguishability.

Q. Two fair dice are rolled. What is the probability that the sum of the numbers on the top faces is 8. A. Case 1: Distinguishable dice $\Omega=\left \{(x,y) \mid 1\leq x\leq 6 \wedge 1\leq y\leq 6 ...
0
votes
1answer
64 views

Maximum score for the game

Here is a game: There is a list of distinct numbers. At any round, a player arbitrarily chooses two numbers $a, b$ from the list and generates a new number $c$ by subtracting the smaller number from ...
2
votes
1answer
64 views

$n$ balls of $2^{n}-1$ colors, order not significant, how many combinations?

An example: With $n = 3$, We draw 3 balls. There are 7 different colors (or numbers). The order of balls does not matter, so [red, green, blue] is treated as being equal to [green, red, blue]. Colors ...
-1
votes
2answers
53 views

Distributing $7$ books to $2$ persons such that each person gets at least $1$ book

In how many ways can $7$ different books be distributed to $2$ persons if each person gets at least $1$ book? I did my calculations and my answer is $126$, but the answer stated is $216$.
0
votes
2answers
3k views

How to solve this cube puzzle question? [closed]

How to solve questions which is based on one main question? (This question is asked in big IT MNC's aptitude test) A cube is colored orange on one face , pink on the opposite face , brown on one face ...
3
votes
0answers
93 views

Number of 'unique' one bit binary functions with N-bit inputs

Consider the set of binary functions that takes an N-bit input -> 1 bit output. There are 2^(2^N) elements in this set. Now potentially reduce this set by restricting to only considering functions ...
1
vote
2answers
104 views

Intuition behind combination problem

I came across this question on a GRE practice exam. I'm trying to build intuition behind how to correctly approach these types of problems: A reading list for a humanities course consists of 10 ...
2
votes
2answers
37 views

Choose groups by category of person

Sorry for the vague title, I'm not really sure what the correct terminology for this type of questions is. I have to hire 6 people: 2 programmers, 2 footballers and 2 logicians. I receive 90 ...
0
votes
2answers
64 views

Pascal's Triangle Proof

Trying to determine a formula for the sum of the entries of the $n$th row of Pascal’s triangle, for any natural number $n$. Any proof will do as I have to determine $3$ different proofs. - So far, ...
3
votes
1answer
90 views

I want to figure out how many Topologies are in the set X

I have the set $$X = \{1, 2, 3\}$$ and I want to figure out how many different topologies I can get from the set $X$ so what I have done is assumed that the empty set and the whole set are in $T$ ...
0
votes
0answers
20 views

Count all possible queues

I got this problem in an exam and I still can't figure it out. The cashier has $\$$0 to begin with. The entry fee is $\$$50 for everybody. There is a queue of the length $n$. Any person pays either ...
0
votes
1answer
38 views

Combinatorics with colored beans

I have some difficulties with the following exercise in combinations: There are $8$ beans in the box: $6$ white beans, $2$ green beans. Two players one by one pick $2$ beans; first player one ...
1
vote
1answer
80 views

How many subsets of size 22 are there?

I am working on an assignment, and am stuck on this question. Suppose we have a set $S = \{1, 2, 3, \dots, n\}$ where $n \ge 22$. Let there be an integer $r$ where $n \ge r \ge 22$. How many ...
0
votes
1answer
43 views

Number of girls in a class

There are some boys and girls in a class. Every boy is friends with exactly three girls, and every girl is friends with exactly three boys. If there are 13 boys in the class, how many girls are there? ...
0
votes
1answer
29 views

Path in a $(6\times 3)$ rectangle

In the following grid (where each movement is either $1$ step rightward or $1$ step upward) find the number of paths from $P$ to $Q$, if the path between $R$ and $S$ is deleted. (figure below) ...
0
votes
1answer
23 views

how often do you expect to bring specific values?

If you constantly throw a couple of dice, how often do you expect to bring two $1s$?And how often do you expect to bring one $1$ and one $2$?
0
votes
1answer
73 views

How many times does Urmi have to write the digit $1$? [closed]

Urmi has not done her assignment. As a result, her teacher makes him write all the numbers from $1$ to $2007$ on a piece of paper (writing each number only once). How many times does Urmi have to ...
3
votes
1answer
170 views

Catalan Numbers Staircase bijection

I need to give a bijective proof for the following problem (via R. Stanley Catalan Addendum). ($k^8$) tilings of the staircase shape $(n, n − 1, \dots , 1)$ with $n$ rectangles. For example, when $n ...
1
vote
1answer
38 views

Ways to partition a block of 9 into blocks of sizes 1, 2, and 3

How many ways are there to partition a block of 9 into blocks of sizes 1, 2, and 3? So lets say I have [XXXXXXXXX]. How many ways can I 'fill' it with [X], [XX], and [XXX] Some ways I could do it ...
11
votes
4answers
449 views

Partitioning the naturals into an infinite number of large sets

Is it possible to partition the positive integers into an infinite number of disjoint large sets ?
4
votes
3answers
183 views

How many different possibilities are there?

I was doing this cool real life puzzle game in Shanghai, China. It works like this: You and a group of friends are locked in a room together - no smartphones, no cameras - and your task is to get ...
0
votes
1answer
32 views

Probability question

N uniform spheres are to be segregated into 4 boxes labelled A,B,C,D. What is the probability of not finding a sphere in box A if : N=4 N=10 ? According to me , if they are the spheres and boxes ...
0
votes
2answers
179 views

Number of partitions of an $n$-element set into $k$ classes

A partition of a set $S$ is formed by disjoint, nonempty subsets of $S$ whose union is $S$. For example, $\{\{1,3,5\},\{2\},\{4,6\}\}$ is a partition of the set $T=\{1,2,3,4,5,6\}$ consisting of ...
1
vote
0answers
64 views

Number of times a prime divides a binomial coefficient

Let $E_{p}(n)$ denote the number of times that $p$ divides $n$. (a) show that if $n<p\leq 2n$ then $E_{p}({2n \choose n} )=1.$ (b) Show that if $\dfrac{2}{3}n<p\leq n$ then $E_{p}({2n \choose ...
4
votes
3answers
151 views

Having trouble with a combinatorics question.

I'm not so good at combinatorics, but I want to know if my answer for this question is right. Originally this question is written in spanish and it says: Se dispone de una colección de 30 pelotas ...
3
votes
1answer
98 views

$K_{1,3}$ packing in a triangulated planar graph

I am trying to show that every planar triangulated graph $G=(V,E)$ with $|V| \ge 5$ has an edge decomposition into $|V| - 2$ groups of $K_{1,3}$. In other words, that we can pack $|V| - 2$ instances ...
0
votes
1answer
59 views

Counting 3 digit numbers [closed]

How many three digit numbers xyz with ('x' and 'Z') < y can be formed a. Digits can be used only once. b. Digits can be repeated.
1
vote
3answers
113 views

Consider the smallest number in each of the $n\choose r$ subsets (of size $r$) of $S=\{1,2,\ldots,n\}$…

Consider the smallest number in each of the $n\choose r$ subsets (of size $r$) of $S=\{1,2,\ldots,n\}$.Show that the arithmetic mean of the numbers so obtained is ${n+1}\over{r+1}$. I have no idea, ...
1
vote
0answers
57 views

Intersection of subsets of additive groups

Given two subsets $A$ and $B$ of a finite additive group $Z$, how can one show that there exists an element $x$ in $Z$ such that $$1 - \frac{|A \cap (B + x)|}{|Z|} \le \left(1 - ...
0
votes
1answer
37 views

Number of 3-point lines on a NxM grid

How many collinear point triples can be chosen on a NxM grid? I have: $$ {N\choose{3}} \times M + {M\choose{3}} \times N $$ Which is far from being correct I know, since at least it does not ...
2
votes
0answers
62 views

Find the expression for the following coefficient

I've asked a similar question to this, but this one is more complicated and I'm unsure of my solution. I need to find an expression for the nth coefficient in the following ...
1
vote
1answer
20 views

Find the expression for the following coeffiecient

I need to find an expression for the following coefficient $$[x^{n}](1-5x^2)^{3m}$$ I know I need to use the binomial theorem with something like $$[x^{n}]\sum\limits_{k=0}^{3m} {3m \choose ...
3
votes
2answers
111 views

Parity of Binomial Coefficients

Do $\binom nr$ and $\binom {2n}{2r}$ always have the same parity? I can see that it's true for $r=1$ since $\binom {n}{1}=n$ and $\binom{2n}{2}=n(2n-1)$, but what about for bigget $r$?