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)

2
votes
3answers
84 views

Formula for $\sum_{i\geq 0} i{n \choose 2i}$?

So I know that $\sum_{i\geq 0}{n \choose 2i}=2^{n-1}=\sum_{i\geq 0}{n \choose 2i-1}$. However, I need formulas for $\sum_{i\geq 0}i{n \choose 2i}$ and $\sum_{i\geq 0}i{n \choose 2i-1}$. Can anyone ...
0
votes
0answers
33 views

How is the Möbius function in boolean sets?

Although the text is a little long, the text is very simple so that're familiar with the matter. I did not understand two passages in the text. Could you help me show that: $I'= I \cup M$ and only ...
1
vote
1answer
35 views

Hamming's code is perfect

How does one prove that Hamming's code is perfect (i.e. it is the 1-error correcting code that has the smallest possible size). I haven't found a complete proof using Google.
3
votes
3answers
36 views

Using 4-cent and 11-cent stamps for postage (induction)

I was wondering how many base cases are needed and when to stop (in general). For example, I have 4-cent and 11-cent stamps and I need to determine the amount of postage I can make, the cases I have ...
6
votes
2answers
215 views

Permutations of {1 .. n} where {1 .. k} are not adjacent

The Problem: So I was thinking up some simple combinatorics problems, and this one stumped me. Let N be the set of numbers $\{1 .. n\}$, or any set of cardinality $n$ Let K be the set of ...
2
votes
1answer
46 views

In how many ways can these people be arranged for a photograph?

Jessie and Casey are getting married. In how many ways can a photographer at their wedding arrange 6 people in a row from a group of 10 people, where the spouses are among these 10 people, if both ...
5
votes
5answers
88 views

How to find number of solutions of an equation?

Given $n$, how to count the number of solutions to the equation $$x + 2y + 2z = n$$ where $x, y, z, n$ are non-negative integers?
0
votes
3answers
47 views

Number of ways to select men and women to a committee?

A committee to contain $5$ members and have at least one woman. There are $7$ women and $9$ men. I think that we can fix one woman as one of the $5$ members, and randomly select the rest from a ...
0
votes
0answers
45 views

Strategy of ball math game

Found math game: http://www.emathhelp.net/math-games-and-logic-puzzles/rgbw/ What is a strategy for it? I can make 15 white balls max. Any thoughts?
0
votes
2answers
45 views

How many relatively prime 4-tuples are there?

Given a set of $n$ distinct integers $S = \{a_1,a_2,...., a_n\}$, count how many ways $4$ integers from the set $S$ can be chosen such that their GCD is equal to $1$.
0
votes
1answer
23 views

combinatorics: give an upper bound for the cardinality of a set of 100-ary sequences

Let $S$ be a $1990$-element set and let $P$ be a set of $100$-ary sequences $(a_1, a_2, ..., a_{100})$, where $a_i$'s are distinct elements of $S$. An ordered pair $(x,y)$ of elements of $S$ is said ...
0
votes
0answers
29 views

Counting balls in face centred cubic close packing

Possibly too easy for stack exchange, but... Consider a cubic close packing, or face centred cubic, arrangement of balls or radius $1$ in dimension $3$. Suppose that the origin is the centre of one ...
4
votes
2answers
43 views

Hall's marriage thereom with max-flow-min-cut

I heard that Hall's marriage theorem can be proved by the max-flow-min-cut theorem. Could you outline how that is possible? Hall's theorem says that in a bipartite graph there exists a complete ...
0
votes
0answers
37 views

Simplify $\sum_{\sum_{i=1}^{2^{n-r}}m_i\ =\ 2^{n-1}\ and\ m_i\ is\ even}\prod_{j=1}^{2^{n-r}}\binom{2^{r}}{m_j},$ where $n$ and $r$ are given.

I need to simplify the following formula: $$\sum_{\sum_{i=1}^{2^{n-r}}m_i\ =\ 2^{n-1}\ and\ m_i\ is\ even}\prod_{j=1}^{2^{n-r}}\binom{2^{r}}{m_j},$$ where $n$ and $r$ are given. I know that: when ...
1
vote
1answer
20 views

Ford-Fulkerson for irrational capacities

We know that the Ford-Fulkerson algorithm works for integer capactities but it may loop forever for irrational ones. Is there an algorithm that only alters Ford-Fulkerson slightly but works for ...
1
vote
2answers
76 views

Simplify $\sum_{i=0}^{m}(-1)^{i}\binom{n}{i}\binom{2n}{2m-2i}$

I have to simplify $\sum_{i=0}^{m}(-1)^{i}\binom{n}{i}\binom{2n}{2m-2i}$. That because when $n$ and $m$ get large (eg. $n = 2^{64}$, $m = 2^{60}$), the computation complexity is too high. Could ...
2
votes
0answers
39 views

Trying to understand the properties of a combinatorial game

Consider the following game for $n \geqslant 3$, which I will demonstrate with $n=4$: draw an $n$-gon and place the value 0 at each of the vertices, except one vertex which we circle and place the ...
1
vote
2answers
51 views

Binomial Coefficient Identity Involving Summation

Prove that $$\sum_{j=0}^n (-1)^j \binom{n+j-1}{j}\binom{N+n}{n-j} = \binom{N}{n} $$ I tried to prove this via binomial expansions of $(1-x)^N (1+x)^{-m}$, and equating the coefficients of $x$, ...
1
vote
3answers
40 views

Number of ways to partition a set with $2n$ elements

In how many ways can I partition $S = \{1,2,\cdots,2n\}$ into $n$ disjoint $2$ element subsets. Suppose if I subsets of $S$ were $S_{1},S_{2},\cdots,S_{n}$, then I can choose $S_{1}$ in $\binom{2n}{2}$...
1
vote
2answers
82 views

Standard playing card deck without jokers: Deal 13 cards. What is the probability at least 1 suit is not present?

Similar questions: What is the probability that 13 cards drawn from a standard deck has at least one card from each suit? Deal 4 cards from a deck. What is the probability that we get one card from ...
1
vote
2answers
53 views

Number of solutions in non-negative integers question (Stars and bars)

Q How many solutions are there in non-negative integers $a, b , c, d$ to the equation: $$ a + b + c + d = 79 $$ with the restrictions that $a \geq 10$, $b \leq 40$ and $20 \leq c \leq 30?$ If ...
1
vote
1answer
39 views

Number of unique combinations

I have a collection of possibly repeated items that I need to map onto another set with possibly repeated items. I need to know an efficient algo to iterate through the unique mapping combinations. ...
0
votes
2answers
77 views

Number of words with length 8 with certain restrictions

How to find number of words with length 8 such in which every letter A, B, C, D occurs exactly 2 times and exactly one pair of same letters occurs on neighbouring positions? Maybe inclusion–exclusion ...
4
votes
1answer
64 views

Splitting Line Segments and Finding Expected Value

Consider a line segment which has a length of $2n-3$. It is split into $n$ segments at random. It is guaranteed that $n\ge 3$ and $n\in \mathbb{Z}$. These smaller lines are then used as the sides of a ...
0
votes
1answer
25 views

Proof of Baranyai's theorem

Could you give me a full proof of Baranyai's theorem. I looked at a lot of sites but they seem to only give partial proofs. I read that Schrivjer proved it using the max-flow-min-cut theorem but I can'...
1
vote
2answers
62 views

10 people, 2 groups with equally summed ages

In a room there are 10 people, none of them is younger than 1 or older than 100 years. Prove that among them, one can always find two groups of people (possibly intersecting, but different) the ...
0
votes
0answers
21 views

Menger's theorem and the max-flow min-cut theorem

I read this question Proof for Menger's Theorem but it's still not clear to me how one proves Menger's theorem using the max-flow min-cut theorem. Could you explain?
1
vote
2answers
51 views

Scheduling a Round Robin tournament - 4-way games

I'm looking to schedule 16 players to play a round robin tournament with each other such that there are 4 players at each table. I'd like for each player to play with each other player exactly once ...
0
votes
0answers
43 views

Edge-matching icosahedron puzzle

Color the edges of an icosahedron with 4 colors so that all 20 triangles have a distinct set of colors. Color the edges of an icosahedron with 6 colors so that all 20 triangles have a distinct set ...
1
vote
3answers
45 views

Simplify $\sum_{i,j}\left[{n}\atop{i+j}\right]\binom{i+j}{i}$

I have to simplify $\sum_{i,j}\left[{n}\atop{i+j}\right]\binom{i+j}{i}$. I looks like we have $n$ children and we have to answer how many times we can arrange them into circles and color some of ...
0
votes
1answer
13 views

Gallai's theorem on independent edges

In a simple graph of $n$ vertices let $\alpha(G)$: the maximal number of independent vertices (no two of them have a common edge) vertices $\beta(G)$: the minimal number of covering vertices (edges ...
3
votes
1answer
55 views

how many ways to fill the room

How many ways are there to fill a $3\times10$ room with $1\times2$ tiles? I tried to solve this problem $\binom{30}{2}\times\binom{28}{2}\times\cdots$ but then I noticed that they may not be next to ...
4
votes
2answers
36 views

Stirling number equality

How to prove that $\left\{{n}\atop{k}\right\} = \sum_{i_1,\ldots,i_{n-k}}i_1\cdot i_2\dots i_{n-k} \cdot [1\le i_1\le i_2 \le \ldots \le i_{n-k}\le k]\ $ and $\left[{n}\atop{k}\right] = \sum_{i_1,\...
1
vote
1answer
34 views

Number of n-permutations with repetition

Let $a_n(k)$ be number of n-permutations with repetition on set $\{1,\dots,k\}$ in which $k$ occurs odd numbers of times. I have to find formula of $a_n(k)$ for $k > 1$. Let $b_n(k)$ be number of n-...
0
votes
0answers
96 views

Binomial-like distribution with shifting probability

Suppose a student answers a question from a teacher, his probability of getting the question right is p, for each successive answer he gets right, p is reduced by r because the teacher decides to make ...
1
vote
2answers
79 views

A combinatorics problem I can't quite understand

A pizzeria offers 777 types of pizza and 3 types of soda. Mary goes there everyday for lunch, always buying one slice of pizza and one soda. However, she never gets exactly the same thing on two ...
1
vote
1answer
41 views

Graph theory: The average degree of G is at least k

Let $G=(V,E)$ be a simple graph with at least $k+1$ vertices, Suppose that for every two vertices that are not adjacent $u,v$ : $d(u)+d(v) \ge 2k$. Prove or disprove: The average degree of G is at ...
1
vote
1answer
37 views

Probability of picking balls with same color with replacement and without replacement

This is one of our probability exercise: We have an urn with m green balls and n yellow balls. Two balls are drawn at random. What is the probability that the two balls have the same color? (...
2
votes
2answers
80 views

Find $\mathbb P (X_1 + \cdots + X_n = 6n-3)$

A fair die is tossed n times (for large n). Assume tosses are independent. What is the probability that the sum of the face showing is $6n-3$? Is there a way to do this without random variables ...
5
votes
3answers
76 views

Find $2^k$ elements from the set ${0,1,\cdots,3^k-1}$ such that none of these element is the average of two other elements of $T$.

The problem is: Consider the set $S = \{0, 1, 2, \ldots, 3^k-1\}$. Prove that one can choose $T$ to be a $2^k$-element subset of $S$ such that none of the elements of $T$ can be represented as the ...
0
votes
1answer
26 views

Find $i^{\text{th}}k-\text{combination}$ in lexicographic order

I would like to obtain the $i^{\text{th}}k-\text{combination}$ in lexicographic order. For instance, for $comb(10,5)$: $i=0: [0,1,2,3,4]$ $i=1: [0,1,2,3,5]$ $i=2: [0,1,2,3,6]$ $\dots$ $i=10: [0,1,2,...
3
votes
3answers
92 views

Number of solutions of: $3x+y=5702$

Find the number of ordered pairs $(x,y)$ satisfying $3x+y=5702$ in natural numbers restricted by: $x+y\le2003$ I don't know any method for counting number of solutions of such equations...
1
vote
1answer
43 views

Shuffles a deck of r ranks and k suits; looks for m cards of the same rank dealt in a row

This is a question that has arisen in my work. Game the First: the dice game. Suppose I have a fair die with r faces. Given some k, I roll the die r*k times; call that sequence of rolls a game. ...
0
votes
0answers
21 views

Probability of getting a “full house” by rolling dice [duplicate]

In poker, full house means getting three cards with the same rank, and another two cards with the same rank (not the same as other three cards). I can understand how to use combination to solve this ...
1
vote
4answers
121 views

What is the probability that a person wearing a blue t-shirt will sit next to one wearing red?

9 people sit in a row linearly. 2 dressed in Red, 3 blue and 4 in yellow. What is the probability that a person in blue will sit next to a person in red? Why? RRBBBYYYY this sequence from what I ...
-1
votes
2answers
60 views

Billy has 5 books and 6 novels, in how many way can he pack 5 books so that at least 2 are novels?

So you'd work out in how many ways he can take 5 books with him $11 \choose 5$ Then what? :/
0
votes
1answer
40 views

What is the probability that at least 2 people in class have the same birthday?

The title states the full question I was provided with. Am I able to just assume the class contains more than 12 students? If so, would we just do: (n choose 2?); where n = number of students in ...
0
votes
1answer
27 views

How many six digit integers contain zero exactly twice.

I can't seem to figure this out. We're provided with the answer (65610) but no matter what I do , I can't seem to find the mathematically. My idea was to let A = the number of six digit integers = $9*...
2
votes
1answer
48 views

What is the Probability came from the same machine

Machine A produced 65 of the day’s output of Product X and machine B produced the other 55. If three products are selected with replacement at random from the day’s output, the probability that, My ...
5
votes
2answers
81 views

Inclusion–exclusion: Matrices

Let $A$ be an $n\times n$ matrix that contains all the numbers $1,2,\ldots,n^2$ (each one appears one time). Count the number of $n \times n$ matrices $B$ that contain all the numbers $1,2,\ldots,n^2$ ...