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
49 views

Permutations through different points

I'm watching Next (2007) and I'm trying to figure out a formula. The premise of the movie is that the protagonist can look into the future for two minutes and he is able to use this to alter his ...
6
votes
1answer
55 views

Is the number of associative $n$-ary algebraic operations on a finite set with 2 cardinality always 8?

We know that if $n = 2$ then the operation is called a binary operation. $ \circ $ on set $X$ is a function $\circ : X \times X \rightarrow X$. And the number of all associative binary operation on a ...
6
votes
4answers
304 views

Truncated alternating binomial sum

It is easily checked that $\displaystyle\sum_{i\ =\ 0}^{n}\left(\, -1\,\right)^{i} \binom{n}{i} = 0$, for example by appealing to the binomial theorem. I'm trying to figure out what happens with the ...
1
vote
0answers
26 views

“Spanning” the difference set of $S$

Suppose that $S$ is a finite set of natural numbers, and $\{(x_i, y_i)\}$ is a set of tuples of numbers in $S$ with $$ \{x_i - y_i\} = S - S := \{a - b \mid a, b \in S\} $$ that is, $\{(x_i, y_i)\}$ ...
4
votes
3answers
192 views

Biggest subset of $\{1, 2 … 1000\}$ such that difference between any pair of elements $\neq 4, 7$

The problem, as stated in the title, is to find the maximal size of a subset $V$ of $S = \{1, 2, ... 1000 \}$ such that no two elements of $V$ have a difference of 4 or 7 between them, i.e. $x \in V ...
0
votes
1answer
75 views

Number theoretical Application of the Pigeonhole Principle

I'm currently working through a paper related to my bachelors thesis and I'm stuck at a point where the author mentions the following result as "a standard application of the pigeonhole principle". ...
2
votes
0answers
145 views

How to load warehouse pallets efficiently?

Assume that we would wan't to develop a warehouse management system, which picks up plastick boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height ...
3
votes
1answer
160 views

Extended Calendar Cube Question

The calendar cube puzzle is famous: using two six-sided cubes, label them such that any day of any month can be represented by positioning the cubes accordingly. The solution involves allowing the ...
2
votes
1answer
61 views

Behavior of Pascal's triangle in $n\mod m$ where $m>2$, any fractals?

If Sierpinski Triangles are found in Pascal's Triangle under modulo 2 what happens when we view Pascal's Triangle under modulo $m$ where $m>2$? Do fractals appear and if so for which numbers? ...
1
vote
4answers
50 views

Subsets of divisors

How many subsets of the set of divisors of $72$ (including the empty set) contain only composite numbers? For example, $\{8,9\}$ and $\{4,8,12\}$ are two such sets. I know $72$ is $2^3\cdot 3^2$, so ...
1
vote
1answer
60 views

How to compute the expected number of unwatched rooms?

Imagine that I have a number of rooms, r, that I want to have watched. So I install one video camera in each room and have televisions that can show what's going ...
2
votes
1answer
97 views

Combinatorics problem about listing numbers $1,2,…n$

In how many ways can the numbers $1,2,...,n$ be arranged as $a_1,a_2,...,a_n$ so that for each $i > 1$ there is a $j < i$ such that $a_j = a_i \pm 1$? For example, ...
0
votes
0answers
40 views

Slots Machine Matching feature

I'm designing a slot machine. I need to find the number of combinations that two matching icons will appear side-by-side in a $3\times 5$ window ($3$ rows, $5$ reels (columns)) A match gives the ...
3
votes
5answers
3k views

Probability of guessing a PIN-code

A friend and I recently talked about this problem: Say my friend feels a little adventurous and tells me that exactly three of four digits of his PIN-code are the same, what is the probability that I ...
1
vote
0answers
64 views

A variation of the menage problem

A combinatorics problem I am chewing on without success is: 3 couples and 40 others are to be arranged randomly in a row. What is the probability that no two couples sit together ? I have looked at ...
0
votes
1answer
75 views

Trying to find Generalization of Product rule when selections are dependent

Given these sets. $A = \{1, 2, 3, 4\}$, $B = \{3, 4, 5\}$, $C = \{1, 2, 3, 4\}$ I'm trying to apply a formula for the inclusion exclusion principle in finding the number of triplets with distinct ...
0
votes
1answer
49 views

Why is the number of binary Lyndon words of length n usually divisible by 3?

Binary Lyndon words are counted by the OEIS sequence A001037. Of the first 100 of terms in this sequence, about 80% are divisible by 3. There are hints of a pattern, but I see nothing solid. The ...
1
vote
3answers
96 views

Evaluate $\frac{\partial^2}{\partial t^2} \left[ \prod_{j=1}^k (1+t+\dots+t^{d_j -1}) \right]$ at $t=1$

I need to find a "nice" formula for the evaluation of $\frac{\partial^2}{\partial t^2} \left[ \prod_{j=1}^k (1+t+\dots+t^{d_j -1}) \right]$ at t=1, where $d_j \in \mathbb{N}$. I have already proved ...
10
votes
1answer
192 views

Prove that all light bulbs can't light off

We are given a table of dimensions $2010\times2012$ where every cell has one light bulb. At the beginning, the number of "on" light bulbs is greater than $2009\times2011$. If in any part of table ...
0
votes
2answers
41 views

Ways to select a hand of 9 cards from a deck of 36

This is a very basic self learning question, the scenario is there are 36 cards of 4 suits from 1 to 9 of each suit. One can pick a hand of 9 cards. My question is how many ways can someone pick a ...
2
votes
1answer
125 views

Minimum number of out-shuffles required to get back to the start in a pack of $2n$ cards?

So I'm stuck on this problem. If you perform a faro out-shuffle (i.e. a perfect "riffle shuffle" where the top and bottom cards stays in place) on a pack of 52 cards ($n=26$), you can get back the ...
1
vote
1answer
53 views

Count of matched items in multiple sets

I do apologize if this is a duplication. I did find a question that appears close to describing something of what I'm looking for, but I'm just not "seeing" the complete picture (maybe): Counting ...
2
votes
1answer
56 views

Verify combinatoric argumentation.

I tried to find all the numbers between 100 and 999, that consist of (pairwise) different ciphers. So the first would be 102 and the last would be 987. I think there are 9*9*8 such numbers, here's ...
0
votes
1answer
71 views

Number of ways by which we can form a n digit number such that no two digit are same in the number?

Example : 2 digit number : so all two digit number except 11 22 33 44 55 66 77 88 99...this is simple but how to generalize for a number of n digit?(Also at each place any digit from 0 to 9 can come ...
1
vote
1answer
46 views

A question involving the throw of seven dice, which of my answers is correct?

Seven dice are thrown, what is the probability that all numbers show up on the dice? My first answer uses the logic that if all numbers show up and you throw seven dice, then one number is repeated ...
1
vote
0answers
77 views

Counting number of perfect matching in bipartite graph. [duplicate]

Graph G is bipartite graph, I want to just count number of perfect matching. Is there any algorithm exist using combinatorial+graph theory, by which i cant count this. I tried by traversing the graph, ...
0
votes
1answer
303 views

Select elements from $N$ sets

$N$ sets are given which can have any number of elements from $1-100$ each. Now we need to count arrangements in which we select $1$ element from each set under the condition that we can not choose ...
2
votes
2answers
97 views

Selecting 180 days from 366: the probability of even distribution across months, or not having September among the first 30

In a draft lottery containing the 366 days of the year (including February 29). Select 180 days (draw 180 without replacement). a) What is the probability that the 180 days drawn are evenly ...
0
votes
0answers
55 views

Is this composition of $K_{4,4}$ graphs minor-closed?

Following graph is a composition of $K_{4,4}$ bipartite graphs with all the edges are of same length. How do I know whether it is minor-closed or not? The definition in the Wikipedia is as follows. ...
2
votes
1answer
65 views

Count amount of pairs $(a,b)$ from two sets $A$ and $B$ such that $a\neq b$

I have two sets $A=\{1,2,3\}$ and $B=\{2,3,4\}$ How do I count the amount of pairs $(a,b)$ where $a\in A$ and $b\in B$, such that $a\ne b$ This problem can easily be done on paper, but how can I ...
5
votes
4answers
314 views

Probability that a word contains at least 3 same consecutive letters?

Assume we have a word of length $n$ and an alphabet of length $26$ (the small letters a through z, if you want so. How likely is it that this word contains at least $k := 3$ consecutive letters of ...
2
votes
2answers
83 views

Number of ways to select numbers, each 1 from different lists without repetition

I want the numbers of ways to select numbers each 1 from different lists without allowing repetition. Eg- List 1 : 5, 100, 1 List 2 : 2 List 3 : 5, 100 List 4 : 2, 5, 100 I want to select 1 ...
1
vote
1answer
81 views

Multiple sum involving binomial factors

Let $n$ and $m$ be positive integers and let $0 \le j \le n-m-1$. Show that: \begin{align} \sum\limits_{l=m}^{n-j-1} \binom{n-l-1}{j} \binom{l}{m} \binom{n+l}{j} &=\sum\limits_{p=0}^j ...
0
votes
1answer
29 views

Chong inequalites about permutations

I read about two inequalities called Chong's inequalities. They state: $$\sum_{k=1}^N\dfrac{a_k}{a_{\pi(k)}}\ge N$$ and $$\displaystyle\prod_{k=1}^Na_k^{a_k}\ge\prod_{k=1}^N a_k^{a_{\pi(k)}}$$ I ...
0
votes
0answers
292 views

Cleaning minimum tables

John has been newly hired to clean tables at his restaurant. So whenever a customer wants a table, he must clean it. But John happens to be a lazy boy. So in the morning, when the restaurant is ...
0
votes
0answers
581 views

Count arrangment such that each person wear different tshirt

Few friends are going to a party. Each person has his own collection of T-Shirts. There are 100 different kind of T-Shirts. Each T-Shirt has a unique id between 1 and 100. No person has two T-Shirts ...
1
vote
1answer
56 views

Infinite series for recurrence

Question 1 If I define $A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!} \tag 1$ (where $a_n$ are $3\times 3$ constant matrices indexed with n), then can we re-write $\sum_{n \ge 1} a_{n-1} \frac{z^n}{n!} ...
2
votes
1answer
25 views

How many ways are there to group a sequence into maximal number of contiguous subsequences of given length?

Say we have a sequence $S_q$ of length $q$ and we want to group it into $m$ contiguous subsequences of length $n$. Apparently $$m=\left\lfloor\frac{|S_q|}{n}\right\rfloor.$$ My question is how many ...
1
vote
0answers
110 views

Number of ways to answer three questions, with four choices each, and not get all of them right

I have this question, I could not get answer to it. In an examination there are three multiple choice questions and each question has $4$ choices. Number of sequences in which a student can fail ...
1
vote
3answers
104 views

Find the number of increasing words of length $n$ formed by an alphabet of $m$ letters

Prove that the number of increasing words of length $n$ formed by an alphabet of $m$ letters is $$\binom{m+n-1}{n}$$ (A word is increasing if its letters(except repetitions) appear in ...
1
vote
1answer
73 views

Recurrence relation for Binary String Question

I have a question which has been a little stumped. I'm pretty sure I know the answer, but don't know how to prove it to be true. Here it is: "Given an infinite length random binary string, what is ...
1
vote
3answers
127 views

Birthday paradox, huge numbers

Pick x random "birthdays", say $10^9$. What are the chance of a collision, given $2^{160}$ possible "days"? I'm trying to estimate the collision rate of sha1 hashes, but the calculation is too big ...
3
votes
3answers
101 views

Probability of having 4 aces after taking turns to pick cards

I've started to learn probability and I get stuck with the following problem: My friend and I are playing a card game with 36 unique cards. There are four suits (diamonds, heart, clubs and spades), ...
7
votes
1answer
84 views

A generalization of Bell numbers to arbitrary complex arguments

For $n\in\mathbb N$, the Bell number $B_n$ is a number of ways to partition the integer range $[1,\,n]$ into pairwise disjoint non-empty subsets. E.g. $B_3=5$ because ...
2
votes
1answer
94 views

A double sum with combinatorial factors

Let $n$, $p$ and $j$ be integers. As a byproduct of some other calculations I have discovered the following identity: \begin{equation} \sum\limits_{p=0}^{j} \sum\limits_{p_1=0}^j \binom{p+p_1}{p_1} ...
0
votes
0answers
52 views

Number of unique ways to edge-label a complete graph with $k$ distinct labels.

Given $k$ distinct labels, how many unique ways to label the edges of a complete graph with $n$ nodes (nodes are not labeled). For example, to label a complete graph with 3 nodes using 4 distinct ...
1
vote
1answer
52 views

Diameter of a 2-Lift of complete bipartite graph

Give an undirected simple graph $G$ with $n$ vertices and $m$ edges, its 2-Lift is constructed as follows: Define $G_1$ to be the original graph $G$. Make a duplicate copy of $G$ and call it $G_2$. ...
0
votes
2answers
151 views

The number of functions $f: {\cal P}_n \to \{1, 2, \dots, m\}$ such that $f(A \cap B) = \min\{f(A), f(B)\}$ (Putnam 1993)

Let ${\cal P}_n$ be the set of subsets of $\{1, 2, \dots, n\}$. Let $c(n, m)$ be the number of functions $f: {\cal P}_n \to \{1, 2, \dots, m\}$ such that $f(A \cap B) = \min\{f(A), f(B)\}$. Prove that ...
0
votes
3answers
67 views

What is the minimum number of colours needed for coding 12 objects, if each may be marked with either one or two colours?

I have a word problem here which is a kind of high level to me A company that ships boxes to a total of (12) distribution centres uses colour coding to identify each centre. If either a single ...
4
votes
2answers
1k views

Outcome of rolling a fair die 6 times

I'm failing to understand how to come to the answer to this question. If you roll a fair die six times, what is the probability that the numbers recorded are $1$, $2$, $3$, $4$, $5$, and $6$ in any ...