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)

4
votes
4answers
70 views

Conjecture for product of binomial coefficient

Is it true that for any $n, k\in\mathbb N$ $$\frac{(kn)!}{k!(n!)^k} = \prod_{l=1}^k {{ln-1}\choose{n-1}} \quad?$$ I tested it for some small $k$ and $n$, but I don't know how to prove that it is true ...
0
votes
3answers
101 views

Given the sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for it?

Given a sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for this sequence? Is there any optimised approach? My approach: the given series is equal to summation of $\binom{n}{k}$ ...
3
votes
4answers
330 views

A consequence of Wilson's Theorem

By Wilson's Theorem we know that $$(p-1)! \equiv -1 \mod p.$$ A consequence of this is apparently $$(p-(k+1))!k! \equiv (-1)^{k+1} \mod p$$ where $0 \leq k \leq p-1$. I was told to think of it like ...
0
votes
4answers
30 views

In how many ways can we arrange $n$ A's and $n-1$ B's into $2n-1$ slots?

There are $2n-1$ slots/boxes in all and two objects say A and B; total number of A's are $n$ and total number of B's are $n-1$. (All A's are identical and all B's are identical.) In how many ways ...
0
votes
0answers
14 views

Slots Machine Matching feature 2

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 3X5 window (3 rows, 5 reels (columns)) A match gives the user some ...
-4
votes
2answers
65 views

Number of squares on a rectangular board that are neither in the 4th row nor in the 7th column

A rectangular game board is composed of identical squares arranged in a rectangular array of $r$ rows and $r+1$ columns. The $r$ rows are numbered from $1$ through $r$, and the $r+1$ columns are ...
-6
votes
0answers
107 views

Solve fibonacci equation

Given two numbers M and N we need to solve : ( ∑ ( 6 * x * y * z * Fibo[x] * Fibo[y] * Fibo[z] ) ) % M , where x + y + z = N. Here x, y, z ≥ 0 and are integers. ...
3
votes
1answer
81 views

How to prove a duality about partitions of numbers?

I found the following theorem, which I think should be correct but I do not know how to prove it: Consider the set containing sums $A=\lbrace\sum\limits_{i=-a}^a iX_i\rbrace$ where $X_i$ is a ...
0
votes
1answer
38 views

2D boolean matrix number of unique combinations without mirrored/rotated ones

Given a $n \times n$ boolean matrix, it's well known that number of all possible combinations of 0s and 1s in that matrix would be $2^{n^2}$, as there are $n^2$ places which could take exactly 2 ...
-1
votes
0answers
50 views

Counting distinct nonempty sequences

Given N and an array of length N i need to count nonempty sequence (p[1], p[1]+1), (p[2], p[2]+1), ..., (p[s], p[s]+1), where p[k]+1 ≤ p[k+1] for k = 1, 2, ..., s − 1. Here p[i] is the point number i ...
0
votes
0answers
19 views

Number of Strongly Connected Components and Property Testing.

I am working on a problem about the strong connectivity of digraphs. Given graph $\vec G$ that is $k$-$\textit far$ away from being strongly connected (i.e, the minimum number of edges that need to be ...
1
vote
1answer
46 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 ...
4
votes
1answer
35 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
189 views

Truncated alternating binomial sum

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

Combinatorics and product rule

Given arrays $A_1, A_2, A_3, ... A_n$. Each array has distinct integers. $A_1 \times A_2 \times .... \times A_n$ is the set of $n$-tuples. How many $n$-tuples have distinct entries? What is the ...
1
vote
0answers
21 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
160 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
58 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
38 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
60 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
44 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
45 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
52 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
94 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
29 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
1k 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
40 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
67 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
30 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
92 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 ...
7
votes
0answers
144 views

Prove that all light bulbs can't light off

Given a table of dimensions $2010\times2012$ where every cell has one light bulb. At the beginning the number of turned on light bulbs is bigger than $2009\times2011$.If in any part of table ...
0
votes
2answers
31 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
50 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
49 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
54 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
58 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
35 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
70 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
271 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 same ...
-1
votes
0answers
43 views

No. of Combinations Possible

I have 'n'(<=10) arrays each containing some distinct numbers (from 1 to 100). I need to pick one no. from each array such that no 2 nos. are same. I need to find the total no. of such ...
0
votes
0answers
88 views

Selecting n different numbers from m sets of numbers?

we are given M sets of numbers.Each set has numbers ranging from 1 to 100.(there can be any number of elements in a set but all elements of one set are distinct (at max 100 elements)).we need to find ...
0
votes
0answers
35 views

Real sequence satisfies a combinatoric uniform property

Does there exist a sequence of real numbers $\{a_n\}_{n\in \mathbb{Z}_{>0}}$such that, for any fixed $k\in \mathbb{Z}_{>0}$, then $a_1, \cdots, a_k$ has a bijection to ...
2
votes
2answers
41 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
51 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
55 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
140 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
77 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 ...
0
votes
1answer
65 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
26 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
277 views

Cleaning minimum tables

Moderator Note: This question is part of the Ongoing August Challenge 2014 CodeChef (problem page). This contest ends on 11 August 2014, and this question will remain locked (with current answers ...