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 (4)

2
votes
1answer
34 views

Perfect matching for graph with two edges for every node

Consider two disjoint sets $A$ and $B$, each of size $n$. Some (undirected) edges connect nodes in $A$ with nodes in $B$. Suppose that each node (in $A$ or $B$) is adjacent to at least two edges. Is ...
1
vote
2answers
40 views

Combinations with replacement

In a factory there are 40 employees. A union of 5 people is being chosen. How many combinations are there for a union, if the union contains of 5 different roles, and each employee can hold more than ...
1
vote
3answers
68 views

Counting valid tickets

I think my question is very easy but I need to understand. The problem is, I have a ticket with 2 numbers from 1 to 10. The first number cannot be greather than the second number. How many valid ...
0
votes
3answers
32 views

Basic Combinatorics Choices Question

I'm having some trouble with the question below: I believe the student to have 9 x 8 x 7 x 6 = 3024 choices overall. However I am unsure how to calculate part (a) and (b) of the question. Any help ...
0
votes
0answers
33 views

show by using leibniz formula

There are given $ r, s,n \in\mathbb N$ and $r+s=n$. It also given $A \in M_{r,K} $, $B \in M_{r\times s,K} $ and $C \in M_{s,K} $. Let $M$ be the matrix $\begin{bmatrix}A & B\\0 & ...
0
votes
1answer
144 views

Find sum of all permutations

We call two arrays A and B with length n almost equal if for every i (1 <= i <= n) ...
5
votes
1answer
48 views

Closed form for sequence A145271

I would like to know if there is a simple formula or method of expanding the expression given by $\left[g(x) \frac{d}{dx}\right]^n g(x)$ where $n$ is a positive integer, without having to resort to ...
2
votes
1answer
227 views

Number of binary trees with N nodes

I am trying to calculate the number of trees (non isomorphic) with n nodes (total including leaves). I think that there are n! such trees, but I don't know how to prove that. I know that the number ...
0
votes
0answers
26 views

Counting question about a rectangular block

Consider the 12 face diagonals of a rectangular block. How many pairs of them are skew lines? (Two lines in space are skew if they do not intersect AND they are not parallel.) Basically I got that ...
4
votes
5answers
191 views

Non-inductive, not combinatorial proof of $\sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$

I've seen the identity $\displaystyle \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$ used here recently. I checked for proofs here ...
2
votes
3answers
34 views

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subests of A cannot all be distinct [closed]

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subsets of A cannot all be distinct. for when does this not continue to hold up ( ie instead of 12 , its ...
0
votes
0answers
6 views

densities in sumsets is the product of the desities

Suppose $A,B,X,Y$ are finite subsets of $\mathbb Z$ with $X\subset A$ and $Y\subset B$. By $A+B$ and $X+Y$ we mean $\{a+b:a\in A,b\in B\}$ and $\{x+y:x\in X,y\in Y\}$ respectively. Suppose ...
1
vote
1answer
42 views

Permutations, Combinations, and Counting

A group of 63 people are camping together. They have two 6-person tents, three 4-person tents, five 3-person tents, and three 2 person tents. 18 people will sleep outside of the tents under a tarp. ...
2
votes
1answer
49 views

How many answers can be created using the elementary arithmetic operators?

If I gave you an amount of $n$ numbers, how many anwswer will you be able to create using the elementary arithmetic operators ($+, -, \times, /$)? These are the rules: All numbers ...
0
votes
1answer
31 views

Selecting 6 people from a group of 10 people with special conditions

Sorry for a misleading or such title, but i didn't know how to make it short enough. Anyways, if we have 10 people in a group such that 8 people eat apples, 1 eats pears and one eats watermelons, ...
0
votes
1answer
45 views

Counting the arrangements of 8 people around a square table?

I am trying to solve this problem of counting the number of arrangements of 8 people around a square table, as shown in the figure below, To solve this problem you can consider arrangements obtained ...
0
votes
0answers
177 views

Distributing cards among players

Moderator Note: This is a current contest question on codechef.com. N players sit around a round table. There are $n \cdot m$ cards with unique numbers of range $1\ldots n\cdot m$. Each player ...
0
votes
0answers
2k views

Minimum moves to reach destination [closed]

Moderator Note: This is a current contest question on codechef.com. Given that a person is standing at $(0,0)$ and initially look in direction of $X$-axis. Now he can walk only at right angle to ...
0
votes
3answers
37 views

Counting Number of even and distinct digits

The Question was: The number of even four-digit decimal numbers with no digit repeated. So the first digit cannot be 0 so there are 9 ways to choose a digit. Then for the 3rd, 2nd and 1st digits ...
3
votes
0answers
36 views

an elementary problem on wreath product groups with combinatorial flavor

Embarrassingly, I got stuck in solving the following elementary exercise. Let $G=H\wr \Gamma$ be a wreath product groups, $H,\Gamma$ are countable discrete groups, when $\xi\in\oplus_{\Gamma}H$, then ...
2
votes
2answers
46 views

Alternating sum of a simple product of binomial coefficients

I would like to evaluate the following alternating sum of products of binomial coefficients: $$\sum_{k=0}^{m} (-1)^k \binom m k \binom n k .$$ I had the idea to use Pascal recursion to re-express ...
3
votes
2answers
28 views

Find value of $n$ with given conditions

The 4-digit positive number $n$'s digit sum is $20$. The sum of the first two digits is $11$, the sum of the first and the last digit as well. The first digit is the last digit $+3$. What is the ...
0
votes
3answers
50 views

If there are $N$ people on the positive $x$-axis and one man can send a message to another one only if the distance between them is $\leq k $.

The question is how to determine a function which would decide if a pair of persons can communicate with each other, where communication is possible only if the distance between two individuals are ...
0
votes
2answers
45 views

dice probabilities

please help me solve the following 2 questions. I know the answers, but there was no help on how to get them. if I paid a dollar per point (333 pays 9, 444 12, 666 18, 321 6), what's the maximum ...
2
votes
4answers
121 views

Arranging the word 'MISSISSIPPI'

"How many ways are there to arrange the letters in the word 'MISSISSIPPI' in such a way that there are no three consonants in a row?" I am thinking like this. The following are 'slots' for the ...
3
votes
1answer
30 views

Another formula for number of onto function.

Let A and B be two sets. $A=\{1,2,\dots m\}$ $B=\{1,2,\dots n\}$ We have to find the number of onto functions from A to B In the following link , the approach of the answer was applying Inclusion ...
0
votes
2answers
67 views

Show that $\binom{n}{k}< \binom{n}{k+1}$ if and only if $k < (n-1)/2$ [closed]

Show that $\binom{n}{k} < \binom{n}{k+1}$ if and only if $k < \frac{n-1}{2}$ and then use this to deduce that the maximum of $\binom{n}{k}$ for $k=0,1,\dots,n$ is $\binom{n}{\lfloor ...
2
votes
1answer
37 views

how many outcomes are there if exactly 3 boys win a medal and exactly 15 boys win shirts?

Suppose there are 60 boys and 50 girls racing. There are 5 medals awarded to the top 5 finishers and there are 35 shirts awarded to the first 35 finishers (shirts are identical but medals are not, ie ...
0
votes
0answers
12 views

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid?

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid? For a matroid, the codomain of the weight function is $[0,\infty)$, from Wikipedia ...
1
vote
1answer
47 views

Permutations of Objects on Grid

I am trying to visualize all possible permutations of 12 objects in a 7x7 grid. Firstly, I would like to find out how many there are. And secondly, how can I visualize all of them?
15
votes
2answers
917 views

any pattern here ? (revised 2)

for any positive number $k$, I have a $(k+1)*(k+1)$ matrix. I wonder if these matrices follow any "obvious" pattern. My goal is to guess the elements for matrix with $k=5$ and above (most probably in ...
1
vote
2answers
67 views

Expected number of coin tosses needed until all coins show heads

We flip $n$ fair coins every iteration of the game. Every coin that shows heads is removed from the game and we use the remaining $n-k$ coins to play the game again (where $k$ is the number of heads ...
1
vote
1answer
41 views

Meaning of the characteristic polynomial of a matroid

From wikipedia The characteristic polynomial of a matroid $M$ (which is sometimes called the chromatic polynomial,[29] although it does not count colorings), is defined to be $$ p_M(\lambda) ...
2
votes
3answers
1k views

Probability of having exactly 1 pair from drawing 5 cards

I have an exercise as follows: There is a collection of cards consisting of 52 cards (13 types and 4 colours each type). We draw 5 cards from the collection. Then what is the probability of having ...
-1
votes
2answers
32 views

Need help in confirming the answer to a combinatorics question?

I need help to confirm my answer for the following question "There is an alphabet of size 40 and this alphabet is used for forming messages in a communication system. If 10 of these alphabets can be ...
4
votes
2answers
81 views

Combinatorics: Mean and Variance of an indicator function of items arranged in a circle.

I have a problem from a homework which I've been struggling with. I normally wouldn't post homework here, but I've spent several hours trying to understand the correct way to solve this , to no avail. ...
0
votes
0answers
50 views

a special function for count

Let be $f:(\mathbb{N} \setminus \left\{0,1 \right\})^2 \rightarrow \mathbb{N}$ function that $f(a,k)=\text{total numbers of }n \in \mathbb{N} \text{ that } \frac{a^n}{n^k} \le 1$ . My question is: ...
9
votes
1answer
84 views

How many Sudoku puzzles are there with at least one solution?

A Sudoku puzzle is a 9 by 9 matrix of blanks(which we can represent as 0), and elements of the set {1,2,3,4,5,6,7,8,9}. How many Sudoku puzzles are there with at least one solution. Yes, I am even ...
1
vote
0answers
22 views

A inequality on a graph and finding the best constant

Find the smallest positive constant $c$ satisfying: For any simple graph $G=G(V,E)$, if $|E|\geq c|V|$, then $G$ contains $2$ cycles with no common vertex, and one of them contains a chord. Note: The ...
3
votes
1answer
31 views

how many ways can 1001 people win 500 identical items?

the question is stating that $1001$ people are in a race and there are $500$ objects that are identical (say the same shirts). We need to find the number of ways that the 500 shirts can be given out ...
1
vote
2answers
80 views

Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$

I'm stuck on this combinatorics question: Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$. I've ...
0
votes
0answers
73 views

Counting maximum moves

Given two arrays, each of size N denoted by A1,A2...AN and B1,B2...BN. Let us maintain two sets S1 and S2 which are empty initially. In one move ,Pick a pair of indexes (i, j) such that : ...
2
votes
1answer
379 views

Probability of finding specific set of coloured balls within larger set of random-drawn balls

In this question I was helped with calculating the probability of drawing specific set of M coloured balls from a set of N coloured balls. Now I am looking for a solution for an extended problem: ...
1
vote
1answer
44 views

Dividing n stones into x piles of size greater than q but less than r

Perhaps this is a basic question, but I'm having a hard time figuring out a general form for the solution. Consider a pile of indistinguishable stones of size n. How many ways can the pile of n ...
2
votes
1answer
111 views

Linear algebra and combinatorics. For a family with even size sets and even intersections prove that $|F| \le 2^{n/2}$

Let $F \subset P(n)$ be a family such that for all i and j $ |f_i \cap f_j|$ and $|f_i|$ are even Prove that $|F| \le 2^{n/2}$ Now I think we go by contradiction and say if $|F| \ge 2^{n/2}+1$ ...
1
vote
1answer
117 views

Number of rooted subtrees of given size in infinite d-regular tree

Currently I am reading a paper where the author states: [...] It is well-known that an infinite $D$-regular rooted tree contains precisely $\frac{1}{(D-1)u + 1} \binom{Du}{u}$ rooted subtrees of ...
-1
votes
1answer
49 views

Intermediate Counting Question

Two Americans, two Canadians, two Mexicans, and two Jamaicans are seated around a round table. People from the same country are distinguishable. In how many ways can all eight people be seated such ...
1
vote
3answers
47 views

Missing Numbers in Roulette, Dice, and Other Gambling Devices

Case 1: I roll a die N times. What is the probability that one of the 6 numbers never comes up? The probability that K of the 6 numbers never comes up? Case 2: Same idea, but with a Las Vegas ...
3
votes
0answers
46 views

What is the number of labeled caterpillars?

A caterpillar is a tree in which all the vertices are within a distance 1 of a central path. (See the Wikipedia article: Caterpillar tree, for an example and some equivalent characterizations). The ...
3
votes
1answer
42 views

Finding the amount of numbers less than another number which are multiples of a set

An Example To Illustrate Find the amount of numbers less than 30 that are multiples of the set of numbers [2,3,5] - Clearly we can find the number of multiples of a number less than another number ...